Some complexity results and an efficient algorithm for quay crane scheduling problem

This paper investigates the quay crane scheduling problem (QCSP) at container ports, subject to arbitrary precedence constraint among vessel container tasks. Differing from classic machine scheduling problems, noncrossing constraint for quay cranes must be satisfied. This is because quay cranes work in parallel and they travel on a same rail (along the berth), to perform container unloading and loading tasks for vessels. Precedence relation in an arbitrary form is rarely investigated in the literature, however, it may be originated from reefers or dangerous cargo which requires high priority of processing, and yard stacking plan. We present the computational complexity for several problem variations. In particular, we show the QCSP, even without precedence constraint, is strongly NP-hard. This complexity result improves the state-of-the-art, in which the same problem is shown to be NP-hard in the ordinary sense. Besides, we also prove that for two parallel quay cranes, if the processing times of container tasks are ones and twos, then this scheduling problem is NP-hard. This result implies that the QCSP with arbitrary precedence constraint is very difficult to solve. A genetic algorithm is proposed to obtain near-optimal solutions. Computational experiments demonstrate the efficiency.