Solving the spatial scheduling problem: a two-stage approach

Abstract

The spatial scheduling problem that arises in hull block assembly shops occurs when scheduling and spatial allocation of the blocks must be considered simultaneously. We present a two-stage approach to this type of problem. The first stage aims to reduce the number of blocks. The second stage optimises the scheduling and spatial allocation of blocks using nonlinear mixed integer programming (NMIP) methods. The procedure proposed in this paper uses an agglomeration algorithm (AA) for the blocks. This procedure is based on the space–time coupling mechanism. The AA is a three-dimensional classification used to cluster blocks linked closely in time and space into virtual blocks. Extensive computational results from real cases are presented to demonstrate the effectiveness of the proposed approach, demonstrating a significant improvement over results obtained from existing methods.

Keywords:

• spatial scheduling; agglomeration algorithm; shipbuilding

Acknowledgements

This work was supported by the Natural Science Foundation of China funded by the Chinese Government (No. 70872076).