Space and time allocation in a shipyard assembly hall

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 com-
putational experiments with this heuristic demonstrate that excellent results can be found
within minutes on a workstation, and that the heuristic outperforms a standard constraint
programming approach. We also describe some additional real-life constraints arising in
the industrial application and show how these constraints can be conveniently integrated
in the model.