Spatial scheduling for irregularly shaped blocks in shipbuilding

• Published in: Computers & industrial engineering 2021-02, Vol.152, p.106985, Article 106985
• Main Authors: Ge, Yan, Wang, Aimin
• Format: Article
• Language: English
• Subjects: Block priority; Block spatial scheduling; Blocks layout rule; Shipbuilding; Standard-angle-fill strategy
• ISSN: 0360-8352; 1879-0550
• DOI: 10.1016/j.cie.2020.106985

•Optimise the layout of irregular shaped blocks in shipbuilding.•A model to maximise the utilisation of the workplace and minimise total delay.•A Block priority classification strategy to reduce delays.•A novel layout rule for the arrangement of blocks to reduce space waste.•Based on an ancient Chinese puzzle game, the tangram. 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.