A project scheduling problem with spatial resource constraints and a corresponding guided local search algorithm

Spatial area is a nonlinear resource encountered in many industries. Using the block assembly process in a shipbuilding company as a case study, we propose a project scheduling problem with spatial resource constraints (2D-RCPSP). Due to the two-dimensional properties of spatial resources, the 2D-RCPSP is more difficult to solve than the well-known NP-hard resource constrained project scheduling problem (RCPSP). For the 2D-RCPSP, we develop a sophisticated guided local search algorithm (GLS). The GLS incorporates penalty terms into the cost function and uses it, instead of the original objective function, to guide the search to the promising regions in search space. Furthermore, rapid improvement strategies are investigated in order to increase the efficiency of the local search. To test our GLS for the 2D-RCPSP, we have designed three classes of problem instances, two of which are adapted from the commonly referenced benchmark instance library PSPLIB for RCPSP, whereas the other is derived from real shipyard production data. Three types of tests, each for one class of instances, are implemented. The computational results on these instances as well as the tuning for key parameter in the GLS are presented.