Heuristic Algorithm for the Facilities Layout Problem

摘要

This paper presents a heuristic algorithm for solving the facilities layout problem. The basic approach is the combination of a constructive method with exchange procedures, used repetitively. The constructive heuristic uses alternate costs, obtained in the process of computing the Gilmore-Lawler bounds, as the criterion for choosing the next assignment. Different partial solutions, to be used as starting points for multiple application of the constructive procedure, are obtained by development of a restricted breadth-first branch and bound tree. Computational results show that the method compares favourably with two competing procedures from the literature in finding solutions within 0.40% of the best known solutions for well known problems. Computing times are reasonable for problems with as many as 36 facilities. We also present a new best known solution for one version of the Steinberg problem, found in the process of experimentation. Keywords: Workplace layout, Problem solving, Health care facilities, Office buildings, Control systems, Production engineering, Backboard wiring. (KR)