A column generation method for quay crane scheduling problem

Quay Crane Scheduling Problem (QCSP) is very important for operation scheduling on a container terminal. This problem can be seen as a parallel machines job-shop scheduling problem with dynamic setup time. The objective is to minimize the turnaround time of the container vessel. This paper used a column generation method to attack the problem. Since the objective function of minimizing the makespan is not a linear function, linear transformation is introduced. Randomly generated route set is used as the initial columns. With the help of label setting algorithm good quality elementary shortest path is obtained as new column. Branch and pricing method is used to close the integer gap and get final solution. Numerical experiments demonstrated that this method has a satisfying performance.