LOCATING SETS OF IDENTICAL MACHINES IN A LINEAR LAYOUT

The assignment of M unique machines to M locations with the objective of minimizing the total machine-to-machine material transportation cos t in a flow line may be formulated as a quadratic assignment problem ( QAP). Instead of having M unique machines, if an application involves one or more sets of identical machines, the location problem becomes a tertiary assignment problem (TAP). Solving a large problem of this ki nd is extremely difficult because of its combinatorial nature. When ma chine-to-machine flow is fixed, the TAP may be specialized to a QAP fo r which the unique machine problem is a special case. Obtaining an opt imum solution to this problem when M is large is also computationally intractable. However, this problem may be solved by identifying sets o f identical machines which may be partitioned into individual, ''uniqu e'' machines. Properties of a special type of matrix called the amoebi c matrix are used in the partitioned problems to provide approximate s olutions, which are relabeled to prescribe a solution to the original problem. Results are demonstrated along with suggestions for further r esearch.