AN IMPROVED HEURISTIC FOR A MACHINE LAYOUT DESIGN PROBLEM

The problem of the location of machines in a production plant is of pr actical importance in modern manufacturing environments. A new procedu re, referred to as edge-interchange, for replacing edges of the maxima l planar graph is presented. Cases of this operation are discussed. Th is procedure is then used to develop a graph theoretic improvement pro cess for solving a machine layout problem. The method can be employed to improve solutions for an initial maximal planar graph generated fro m construction heuristics. A computational experiment is reported for benchmark test problems of different sizes and compared with the exist ing heuristic. The proposed algorithm performs well in terms of soluti on quality and computational time.