A quadra-directional decomposition heuristic for a two-dimensional, non-equidistant machine-cell location problem

After the development of numerous cell formation techniques, machine-cell location (MCL) problems have been the focus of many researchers in cellular manufacturing systems. With the cost cutting strategy, locating machines within the cell itself has not only been the major concern of management, but also the location of cells with respect to each other on a spatial coordinate system to minimize the transportation cost or job movement costs. For lack of being able to solve a large problem optimally, a number of heuristics have been developed for one-dimensional machine and MCL problems. The problem still exists for locating machine-cells on spatial coordinates, which has been addressed in this research. The location coordinates have been decomposed into four movements, backward, forward, upward and downward; and the MCL problem is formulated as a linear combination of these four decomposed (partitioned) objective functions subject to other boundary conditions. A quadra-directional decomposition heuristic (QDDH) is developed to find a sub-optimal solution to the MCL problem. The decomposition procedure for four objective functions is presented and the performance of the heuristic is tested on a set of well-known data. Empirical tests show that the solution procedure produces efficient, good quality solutions for different sizes of the problem instances. (c) 2005 Elsevier Ltd. All rights reserved.