| Author Name | Affiliation | | Guanglei Jiao | Department of Industrial Engineering and Management, Shanghai Jiao Tong University, Shanghai 200240, China | | Zuhua Jiang | Department of Industrial Engineering and Management, Shanghai Jiao Tong University, Shanghai 200240, China | | Jianmin Niu | Shanghai Ship Technology Research Institute, Shanghai 200032, China | | Wenjuan Yu | Shanghai Ship Technology Research Institute, Shanghai 200032, China |
|
| Abstract: |
| 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. |
| Key words: ship painting personnel scheduling multi-skilled workers scatter search task constraints |
| DOI：10.11916/j.issn.1005-9113.23006 |
| Clc Number:U692.4+3 |
| Fund: |
|
| Descriptions in Chinese: |
| 一种适用于船舶分段涂装多技能人员排班问题的改进式分散搜索算法 焦光磊1，蒋祖华1，牛建民2，禹文娟2 （1.上海交通大学 工业工程与管理系，上海 200240； 2. 上海船舶工艺研究所， 上海 200032） 摘要：本文主要研究船舶分段涂装多技能人员排班的优化方法，考虑喷涂面积、喷涂区域难度、工人多技能和工人效率的影响进行预算工时分析，以最小化项目完工时间为目标建立数学模型。该模型考虑了船舶分段涂装生产中的任务优先度、油漆调配、喷涂看泵与邻避关系等约束，在基础上提出一种改进式分散搜索(ISS)算法，ISS算法通过混合近似动态规划算法来提高搜索效率，同时以路径重连和任务序列组合两种解组合方法来增强搜索广度与深度。数值实验结果表明，ISS算法在小规模算例上与求解器相比，具有显著求解效率优势；相比于传统分散搜索算法与遗传算法，能稳定提高求解质量。经生产实例的算例验证，ISS算法可以有效缩短任务总完工时长，适用于船厂实际涂装生产中的排班问题。 关键词：船舶涂装；人员排班；多技能工人；分散搜索；任务约束 |
