Models and algorithms for the facility layout problem with emphasis on supporting just-in-time

In this dissertation, we develop new algorithms to solve two different versions of the Facility Layout Problem (FLP). In the first version, the departments are rectangular and their corners are continuous decision variables. The input/output location of each department is assumed to be located at its centroid and the location of a single shipping and receiving (s/r) area is specified in advance. The problem is a variant of one first formulated by Montreuil (1990). We present an algorithm based on a Lagrangian relaxation to solve this problem, and discuss the advantages and disadvantages of this approach. We also present an algorithm based on Benders' Decomposition, which takes better advantage of the structure of our problem and provide computational results.; The second version of the problem is a generalization to consider decentralized shipping and receiving. That is, multiple s/r areas are allowed along the perimeter of the facility and each department can be serviced by the closest s/r area. Our work on this extension was motivated by Just-In-Time systems which require that frequent trips be made with small move quantities. In such circumstances, the use of decentralized s/r areas can significantly decrease material handling costs. For a given set of s/r areas, the internal layout should also be adapted to better exploit decentralized receiving by placing departments with high external flows closer to the s/r areas. Because the designs of the s/r areas and the internal layout are interrelated, one should solve both aspects simultaneously. We extend the FLP formulation to model this new problem with decentralized shipping/receiving (FLPDR). We then extend the solution procedures based on Benders' Decomposition for the FLP to solve the FLPDR and report computational results.; This research presents the first optimization-based approach to solve the recent and realistic formulation of the FLP first proposed by Montreuil (1990). The computational results show that our algorithm which is based on Benders' Decomposition performs well. The concept of decentralized receiving in the context of the FLP is also introduced and discussed for the first time in this thesis; this generalization of the problem is reflected in the formulation of the FLPDR. A solution procedure is also proposed for the FLPDR and computational results are reported.