We considers a scheduling problem arising in a shipyard sub-assembly process. Given sets of multiple gantry robots and welding lines, we need to assign a gantry robot to each welding line and determine the starting time and welding directions of each welding line while collisions between adjacent gantry robots should not occur.
To solve this problem, we propose a heuristic algorithm which is based on a decomposition of the problem into three subproblems : clustering, routing and determination of welding starting time. The first phase of the algorithm assigns each welding line to a gantry. The second phase decides the welding sequence for each gantry robot without collision between adjacent gantry robots. The third phase improves the welding sequence acquired in the second phase with branch and bound method.
Computational results show that the proposed algorithm can solve practically-sized problems within a reasonable time and the quality of the solution is acceptable.
