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

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.