A heuristic for assigning facilities to locations to minimize WIP travel distance in a linear facility

Many manufacturing systems require an assignment of machines to locations along a straight track, so as to optimize material flow. This paper uses a cut approach to the corresponding quadratic assignment problem, and derives a heuristic which generates a good solution. In addition, a modified lower bound to the assignment problem is also developed, which is always better than the classical lower bound. Results showing the performance of the heuristic are demonstrated, along with a comparison of the modified and classical lower bound. In almost all the test problems, the solution generated by the heuristic was either optimal or better than any solution obtained by other methods. Extension of the heuristic to more general cases also is considered.