A graph-theoretic heuristic for designing loop-layout manufacturing systems

In flexible manufacturing systems, the type of materials handling system strongly influence the machine layout. For layouts where the machines are arranged in a loop and the material handling system is uni-directional, a measure of congestion for a part is the number of times the part traverses the loop before its processing is completed. This paper investigates the problem of determining a machine layout for uni-directional loop networks which minimizes the maximum number of loop traversals for a family of parts. Based on graph-theoretic arguments, a heuristic is developed which constructs a layout from a solution to the linear-programming relaxation of the problem. Preliminary computational results are also presented.