Scheduling Ship Hull Assembly Using Lagrangian Relaxation Method

A new Lagrangian Relaxation approach is developed for the scheduling problem of ship hull assembly in a shipyard. It appears to be the first attempt to schedule parallel machines with arbitrary precedence constraints of tasks, capacity constraints of machines (defined in assembly fat-model) and the situation that some tasks must occupy multiple machines simultaneously. The objective is to minimize the weighted total completion time. A mathematical formulation of the problem is presented firstly. Then the task precedence constraints rather than crane machine capacity constraints are relaxed by Lagrangian relaxation method and the subgradient method is used to solve the Lagrangian dual problem. Finally the results are modified by some heuristic operation. This approach can get a lower bound and a feasible solution. A practical example of container vessel that includes 65 blocks is solved by the proposed approach, and the results show that the Lagrangian relaxation method is able to solve industrial-dimensioned problems within reasonable time and accuracy.