A two-stage composite heuristic for dual cycling quay crane scheduling problem

In this paper, hatch constrained quay crane scheduling problem is considered to minimize makespan with dual cycling, which can improve efficiency of operations and utilization of quay cranes. By analyzing precedence relationships intra- and inter- hatches, the problem is decomposed into two embedded sub-problems, each of which can be formulated as a 2-machine flow shop scheduling problem. A composite heuristic is introduced for stacks scheduling in a hatch by integrating the Johnson rule with a developed gap-shifting strategy. A better model is constructed for inter-hatches than existing ones, in which overlapped processing time is shorten and effectiveness can be improved by a reconstructive Johnson rule. Experimental results show that the proposed composite algorithm outperforms the existing hybrid heuristic.