Directional decomposition heuristic for a linear machine-cell location problem

A machine-cell itself can be treated as a machine, and the location of such a cell in a linear line configuration reflects an analogy to the machine location problem. Thus, the problem addressed here is a one-dimensional equidistant machine-cell location problem that considers jobs with sequenced-operations, and the number of machine-cells equals the number of locations that are equally spaced in a linear layout. It is always desirable to achieve a cell assignment that minimizes the total inter-cell flows and, thus, the total inter-cell flow costs. This assignment problem can be formulated as a quadratic assignment problem the optimal solution to which is usually prohibitive since it is a non-deterministically polynomial hard problem, and a heuristic procedure is justifiably called for in this research. Many of the investigations involved in seeking an improved location assignment in heuristics are repeated from one search to another. Each branch of the search requires re-computation of all inter-cell flows, though only some of them have been changed from the previous one. Such a search mechanism requires considerable computation time, thus making the algorithm inefficient. This problem can be overcome by directionally decomposing the inter-cell flows and incrementally computing them. Based on the directional decomposition of these flows, a directional search is implemented in the heuristic in order to reduce the repetitiveness occurring in the traditional search. Both the partitioning procedure and the directional decomposition heuristic proposed here are demonstrated through examples, and the performance measures indicate the superiority of the heuristic over the existing methods.