Article ID: | iaor20106147 |
Volume: | 179 |
Issue: | 1 |
Start Page Number: | 57 |
End Page Number: | 76 |
Publication Date: | Sep 2010 |
Journal: | Annals of Operations Research |
Authors: | Crama Yves, Bay Maud, Langer Yves, Rigo Philippe |
Keywords: | manufacturing industries, heuristics |
We present a space and time allocation problem that arises in assembly halls producing large building blocks (namely, a shipyard which assembles prefabricated keel elements). The building blocks are very large, and, once a block is placed in the hall, it cannot be moved until all assembly operations on this block are complete. Each block must be processed during a predetermined time window. The objective is to maximize the number of building blocks produced in the hall. The problem is modeled as a 3-dimensional bin packing problem (3D-BPP) and is handled by a Guided Local Search heuristic initially developed for the 3D-BPP. Our computational experiments with this heuristic demonstrate that excellent results can be found within minutes on a workstation. We also describe some additional real-life constraints arising in the industrial application, and we show how these constraints can be conveniently and flexibly integrated in the solution procedure.