OPTIMAL AND HEURISTIC PROCEDURES FOR ROW LAYOUT PROBLEMS IN AUTOMATEDMANUFACTURING SYSTEMS

In many automated manufacturing environments, particularly flowlines a nd flexible manufacturing systems (FMSs), machines are arranged along a straight material handling track with a material handling device mov ing jobs from one machine to aother. These layouts are referred to as row machine layouts. In this paper we study the Row Layout Problem (RL P) under the design objective of minimizing the total backtracking dis tance of the material handling device, which is a NP-complete problem. We propose the use of a dynamic programming algorithm for its solutio n. Special cases of the problem, usually encountered in flexible manuf acturing cells and which can be solved with polynomial procedures, are also discussed For the equidistant case (i.e., successive candidate l ocations are in equal distances), we formulate the problem as an integ er linear program. The use of standard mathematical programming codes can efficiently solve this formulation. Two effective heuristic proced ures, which explore simple ideas based on local optimality conditions, are also presented. Extensive computational results demonstrate the e ffectiveness of such heuristics.