ABSTRACT
The problem of the location of machines in a production plant is of practical importance in
modem manufacturing environments. A new procedure, referred to as edge-interchange, for
replacing edges of the maximal planar graph is presented. Cases of this operation are discussed.
This procedure is then used to develop a graph theoretic improvement process for solving a
machine layout problem. The method can be employed to improve solutions for an initial
maximal planar graph generated from construction heuristics. A computational experiment
is reported for benchmark test problems of different sizes and compared with the
existing heuristic. The proposed algorithm performs well in terms of solution quality and
computational time.