The amoebic matrix and one-dimensional machine location problems /
| Main Author: | |
|---|---|
| Other Authors: | , |
| Format: | Thesis Book |
| Language: | English |
| Published: |
1989.
|
| Subjects: | |
| Online Access: | Link to OAKTrust copy |
| Abstract: | This dissertation develops heuristics for locating machines in a one-dimensional layout. The problem is to assign M machines to M locations along a track, which is served by a material handling transporter, to minimize the distance travelled by a given set of jobs. Depending upon the locations of machines, a job may require either upstream or downstream transport between successive operations. Four related scenarios of the location problem--unique machines with unidirectional (backtracking) flow, sets of identical machines with unidirectional flow, unique machines with bi-directional flow and sets of identical machines with bi-directional flow--are studied. In applications involving several sets of identical machines, the location problem is a tertiary assignment problem (TAP). When flow from one set of machines to another is assigned to specific machines, the problem reduces to a unique machine assignment problem and the TAP specializes to a quadratic assignment problem (QAP). Obtaining an optimum solution to this problem when M is large is computationally intractable, since it is NP-hard. Problems in which the unidirectional (backtracking) movement of the job is minimized are studied first. It is observed that a distance matrix, formed from an assignment of machines to locations, and the geometry of the (assumed) equally-spaced locations available along the line, possesses a unique internal structure described as amoebic properties. Based on these amoebic properties, a construction heuristic and an improvement heuristic are devised to solve the backtracking problem. These heuristics are subsequently modified to deal with bi-directional flow problems. In problems involving sets of identical machines, the sets are partitioned into individual, 'unique' machines to form a surrogate problem. The solution to this unique machine problem is then relabeled to prescribe a solution to the original, unidirectional (or bi-directional) problem. Solution quality and computational time are characterized through both analysis of complexity and experimental testing. Empirical results indicate that the proposed heuristics perform well in comparison with existing ones. In fact, it is shown that solutions prescribed by the heuristics approach optimal values as the workload in the system increases. A simulation study, which was pursued to investigate the robustness of heuristic solutions, indicates that they lead to efficient system operations, reducing makespan, improving average machine utilization, and enhancing the throughput rate. |
|---|---|
| Item Description: | Typescript (photocopy). Vita. "Major subject: Industrial engineering." |
| Physical Description: | xii, 333 leaves : illustrations ; 29 cm |
| Bibliography: | Includes bibliographical references. |