Spatial scheduling for irregularly shaped blocks in shipbuilding

This study explores the block spatial scheduling problem in shipbuilding, in which a series of blocks needs to be arranged in a workplace. Each block is irregularly shaped and has a known delivery time. As such, to reduce delay, the workplace should be fully utilised. To maximise the utilisation rate of the workplace and minimise the total delay for all blocks, a mixed integer programming model is created. Further, a block layout rule based on standard-angle filling is proposed, in which each block is simplified to a small extent, compared with simplifying blocks into rectangles, by ensuring all angles are multiples of 15°. Therefore, the space waste caused by block simplification is reduced, and blocks can be closely fit, similar to rectangles. The proposed model is solved by a block-priority-based genetic algorithm, in which block priority is considered in the coding rule, the crossover, and the mutation operators; this not only reduces the solution space but also avoids large block delay at the source. The proposed model and algorithm are tested using six real data cases of a shipyard in China. The significant advantage of the proposed algorithm is proven by comparing it to other algorithms in the literature.