Improved Scatter Search Algorithm for Multi-skilled Personnel Scheduling of Ship Block Painting  

作　　者：Guanglei Jiao Zuhua Jiang Jianmin Niu Wenjuan Yu 

机构地区：[1]Department of Industrial Engineering and Management,Shanghai Jiao Tong University,Shanghai 200240,China [2]Shanghai Ship Technology Research Institute,Shanghai 200032,China

出　　处：《Journal of Harbin Institute of Technology(New Series)》2024年第1期1-15,共15页哈尔滨工业大学学报（英文版）

基　　金：Sponsored by the Ministry of Industry and Information Technology of China(Grant No.MIIT[2019]359)。

摘　　要：This paper focuses on the optimization method for multi-skilled painting personnel scheduling.The budget working time analysis is carried out considering the influence of operating area,difficulty of spraying area,multi-skilled workers,and worker’s efficiency,then a mathematical model is established to minimize the completion time. The constraints of task priority,paint preparation,pump management,and neighbor avoidance in the ship block painting production are considered. Based on this model,an improved scatter search(ISS)algorithm is designed,and the hybrid approximate dynamic programming(ADP)algorithm is used to improve search efficiency. In addition,the two solution combination methods of path-relinking and task sequence combination are used to enhance the search breadth and depth. The numerical experimental results show that ISS has a significant advantage in solving efficiency compared with the solver in small scale instances;Compared with the scatter search algorithm and genetic algorithm,ISS can stably improve the solution quality. Verified by the production example,ISS effectively shortens the total completion time of the production,which is suitable for scheduling problems in the actual painting production of the shipyard.

关 键 词：ship painting personnel scheduling multi⁃skilled workers scatter search task constraints 

分 类 号：U692.43[交通运输工程—港口、海岸及近海工程]