Accepted Manuscript

Approximate the scheduling of quay cranes with non-crossing

constraints

An Zhang, Wenshuai Zhang, Yong Chen, Guangting Chen,

Xufeng Chen

PII: S0377-2217(16)30854-2
DOI: 10.1016/j.ejor.2016.10.021
Reference: EOR 14044

To appear in: European Journal of Operational Research

Received date: 31 May 2016

Revised date: 2 October 2016
Accepted date: 13 October 2016

Please cite this article as: An Zhang, Wenshuai Zhang, Yong Chen, Guangting Chen, Xufeng Chen,
Approximate the scheduling of quay cranes with non-crossing constraints, European Journal of Oper-
ational Research (2016), doi: 10.1016/j.ejor.2016.10.021

This is a PDF file of an unedited manuscript that has been accepted for publication. As a service
to our customers we are providing this early version of the manuscript. The manuscript will undergo
copyediting, typesetting, and review of the resulting proof before it is published in its final form. Please
note that during the production process errors may be discovered which could affect the content, and
all legal disclaimers that apply to the journal pertain.
 ACCEPTED MANUSCRIPT

Highlights

We study the scheduling of quay cranes with non-crossing constraints.

New lower bounds on the optimal solutions are provided.

T
A new algorithm is designed and analyzed for m quay cranes.

IP
Discussions on several previous algorithms and the computational experiments are made.

An approximation algorithm for two quay cranes with different speeds are presented.

CR
US
AN
M
ED
PT
CE
AC
 ACCEPTED MANUSCRIPT

Approximate the scheduling of quay cranes with non-crossing

constraints

T
IP
An Zhang Wenshuai Zhang
Yong Chen
Guangting Chen Xufeng Chen

CR
Abstract
In port container terminals, the scheduling of quay cranes (QCs) for a container vessel is one

US
of the most critical operations. This paper investigates the problem of scheduling quay cranes
with non-crossing constraints, wherein QCs cannot cross over each other because they are on the
same track. The objective is to minimise the makespan of a container vessel, which is the latest
AN
completion time among all handling tasks of the vessel. Compared with several 2-approximation
algorithms in the literature, this paper presents an approximation algorithm with a worst case
2
ratio 2 m+1 < 2 for any m QCs. This ratio is demonstrated to be the best possible among
all partition-based algorithms in the literature. Besides, we study the scheduling of two quay
M

cranes with different processing speeds. For an arbitrary speed ratio s 1, an approximation
(1+s)2
algorithm with worst case ratio 1+s+s 2 is provided.

keywords: Scheduling, Non-crossing, Quay cranes, Approximation algorithms, Worst case anal-
ED

ysis

Mathematics Subject Classification(2000): 90B35, 90C27

PT

1 Introduction
CE

In recent years, the topic of operations management for container terminals has attracted con-
siderable interest in the field of operations research and optimisation [1, 2, 3, 4, 5]. Typically,
AC

seaside operations planning for container terminals involves berth allocation, storage space allo-
cation, quay crane assignment, quay crane scheduling, yard crane scheduling, and so on [6, 7, 8].

Corresponding author. Department of Mathematics, Hangzhou Dianzi University, Hangzhou 310018, P. R. China.
[email protected]. Supported by the Zhejiang Provincial Natural Science Foundation of China (LY16A010015)
and the National Natural Science Foundation of China (11201105).

Department of Mathematics, Hangzhou Dianzi University, Hangzhou 310018, P. R. China.

Department of Mathematics, Hangzhou Dianzi University, Hangzhou 310018, P. R. China. Supported by the
National Natural Science Foundation of China (11401149).

Taizhou University, Linhai 317000, Zhejiang, China. Supported by the National Natural Science Foundation of
China (11571252). [email protected]

Department of Mathematics, Hangzhou Dianzi University, Hangzhou 310018, P. R. China.

2
 ACCEPTED MANUSCRIPT

All these container terminal operations impact each other. In particular, the scheduling of quay
cranes significantly influences the turn-around time of a container vessel. The main objective of
this process is to determine the sequence of loading or unloading operations so that the makespan
of a container vessel, that is, the latest completion time among all handling tasks of the vessel, is
minimised. In the quay crane scheduling problem (QCSP), it is commonly assumed that a con-

T
tainer vessel can be divided into holds and only one quay crane can work on a hold till completion.

IP
Comparing the overall processing time for loading or unloading operations in a hold by a quay
crane, the travel time of a quay crane between two holds is small and hence can be ignored.

CR
The non-crossing constraints in the QCSP were first incorporated by Kim and Park [9], where
quay cranes (QCs) cannot cross over each other because they are on the same track. In [9], Kim and

US
Park studied the location of quay cranes and their release dates. An MIP formulation was provided,
subject to both non-crossing and precedence constraints. To solve the problem, they proposed a
branch and bound method and a heuristic algorithm. Note the objective discussed in [9] was to
AN
minimise the weighted sum of the makespan of the container vessel and the total completion time
of all quay cranes. As noticed by Moccia et al. [10], the model of Kim and Park [9] may yield
solutions where interference between QCs is not detected. A revised formulation of the QCSP
M

was presented by the authors. They developed a Branch-and-Cut algorithm applying inequality
constraints adopted from solution methods for the Precedence Constrained Traveling Salesman
ED

Problem. Lee et al. [11] provided a more concise MIP model for the makespan minimisation
problem with non-crossing constraints. A genetic algorithm was obtained by Lee et al. [12] as
well . For the same problem, Zhu and Lim [13] also formulated an MIP model and solved it by a
PT

branch and bound algorithm and a simulated annealing heuristic. Lee and Chen [14] examined the
common deficiencies in modelling the QCSP with non-crossing constraints in previous studies and
CE

proposed additional constraints in order to fix the problems. Besides, they presented two heuristics
to solve the problem and compared their performances through numerical experiments. Lim et al.
AC

[15] extended the quay crane scheduling problem for multiple container vessels with non-crossing
constraints. To produce a crane-to-job matching that maximises the total profit, they presented
dynamic programming algorithms, a probabilistic tabu search, and a squeaky wheel optimisation
heuristic. Shang et al [16] investigated the integrated berth allocation and QC assignment problem
in container terminals. A deterministic model is formulated by considering the setup time of quay
cranes. To handle the uncertainties, a robust optimisation model is established.

It must be noted that even minimising the makespan of one single container vessel with non-
 ACCEPTED MANUSCRIPT

crossing constraints is an NP-hard problem, see e.g., [13, 17, 12, 11, 18]. For an arbitrary number
of QCs, several 2-approximation algorithms have been proposed in the literature [18, 17, 11]. In
[18], Lim et al. presented a dynamic programming algorithm to solve the QCSP, and based on
this DP algorithm, they derived a fully polynomial time approximation scheme (FPTAS) for any
constant number of QCs. Liu et al. [19] studied the scheduling of a small number of quay cranes

T
with non-crossing constraints. For two and three quay cranes, they proved that the heuristic

IP
4
proposed by Lee et al. [11] is 3 and 35 -approximation, respectively. Turkogullari et al. [20] studied
the berth allocation, time-variant QC assignment, and scheduling problem with QC setup time,

CR
considering the costs of deviation from the desired berthing position in the objective function.
To solve the model, the cutting plane procedure was proposed. An important issue of container

US
terminal optimisation related to the QCSP is the quay crane double-cycling problem (QCDCP),
which was initiated by Goodchild and Daganzo [21, 22]. Recently, Lee et al. [23] formulated the
general QCDCP with hatch covers as a flow shop scheduling problem with series-parallel precedence
AN
constraints, which indicates that the general QCDCP can be solved in polynomial time. For other
studies with respect to the QCSP and other optimisation problems in container terminals, we refer
to survey papers [6, 7] and the references therein.
M

In this paper, we focus on the scheduling of quay cranes to serve a berthed container vessel.
We assume that the container vessel can be divided into holds and that quay cranes can move
ED

from hold to hold but tasks are non-preemptive, so that only one quay crane can work on one
hold or task to complete it. The non-crossing constraints between quay cranes must be satisfied
owing to the common track on which the quay cranes can move. The objective is to minimise the
PT

makespan of the container vessel. Our model is the same with Lim et al. [18] or Lee et al. [11]. As
a new contribution to this problem, we first provide a new lower bound on the optimal solutions
CE

2
caused by the non-crossing constraints. Then, a 2 m+1 -approximation algorithm is presented for
any m QCs; the algorithm performs better than the previous ones [18, 11, 19, 17] for a constant
AC

number of QCs. Besides, we demonstrate that it is one of the best algorithms for partitioning.
Finally, we study the case where quay cranes might have different speeds for handling tasks. For
two uniform QCs with a speed ratio of s 1, an approximation algorithm with worst case ratio
(1+s)2
1+s+s2
is proposed.

The rest of the paper is organised as follows. Section 2 provides a formal description of the
problem and discusses the lower bounds. Section 3 studies the problem with m QCs. Section 4 con-
siders the scheduling of two QCs with different speeds. In Section 5, we make some computational
 ACCEPTED MANUSCRIPT

experiments. Finally, some concluding remarks are presented in Section 6.

2 Problem description

Throughout the paper, we study the scheduling of quay cranes with non-crossing constraints to

T
minimise the makespan of a container vessel. Suppose that the container vessel is divided longitu-

IP
dinally between head (left) and tail (right) into holds indexed by 1, 2, , n, respectively (See Fig.
1). In each hold, there are containers that must be loaded or unloaded by quay cranes. Only one

CR
quay crane can handle one hold till completion. Let the processing time of the j-th hold be pj > 0
and for convenience, assume that the QCs are located parallel to the container vessel and indexed

US
by 1, 2, , m, respectively (See also Fig. 1), the quay crane scheduling problem is therefore finding
a map from the set of holds to the set of QCs, and determining for each hold j an exact time sj
when it starts. Owing to the non-crossing constraints for QCs, which move on the track, a scheme
AN
is feasible if and only if for any two holds j, j 0 with j < j 0 , either their processing windows do not
overlap, i.e., [sj , sj + pj ) [sj 0 , sj 0 + pj 0 ) = or they are assigned to QCs with (j) < (j 0 ). With
such constraints, a simple observation can follow.
M

Proposition 2.1 At any moment while the i-th crane is processing the j-th hold, neither a crane
i0 with i0 > i can process a hold j 0 with j 0 j, nor a crane i00 with i00 < i can process a hold j 00 with
ED

j 00 j.
PT

Holds in the vessel

CE

Head 1 2 3 n-1 n Tail

AC

Berth
1 2 3 m

Quay cranes

Figure 1: The quay crane scheduling problem (QCSP) with non-crossing constraints
 ACCEPTED MANUSCRIPT

Pn
For simplicity, let j=1 pj = 1 and pmax = maxj=1,2, ,n {pj }. Further, let C A and C be the
makespan generated by an algorithm A and the optimal makespan, respectively. Then, similar
to the parallel machine scheduling problem, we have the following lower bound on the optimal
makespan.

T
1
Theorem 2.2 C max{ m , pmax }.

IP
Besides, due to the non-crossing constraints of QCs, we obtain another lower bound.

CR
P 1+pl L
Theorem 2.3 If L = l1
j=1 pj < pl for some hold l 1, then C min{ m , pl + mL
}; symmet-
Pn
rically, if R = j=r+1 pj < pr for some hold r n, then C min{ 1+pmr R , pr + mR
}.

Proof. If there is a hold l > 1 with L =

optimal algorithm would assign the l-th hold.
Pl1
US
j=1 pj < pl , then consider quay crane (l) to which an
AN
Case 1: (l) = 1. By Proposition 2.1, no crane can handle the leftmost l 1 holds during the
Pl1
pj L
time when the first crane is processing the l-th hold. Thus, clearly, C pl + j=1
m = pl + m.

Case 2: (l) = i > 1. By Proposition 2.1, no cranes on the right side of QC i can process the
M

leftmost l holds during the time interval [sl , sl + pl ) when it is processing the l-th hold. Accordingly,
each of the leftmost i 1 QCs must be either processing the leftmost l 1 holds or be idle during
P
ED

that time. Since the overall processing time of the leftmost l 1 holds equals L = l1
j=1 pj < pl , the
total idle time of these cranes during that time interval must be no shorter than (il)pl L pl L.
1+pl L
Accordingly, we can obtain C m .
PT

Hence, C min{ 1+pml L , pl + L

m }. The symmetric part can be proved in a similar manner. 2
CE

The following instance shows that our new lower bound indeed works.

Instance 1: Let there be three QCs and seven holds, where p1 = p3 = p4 = 61 , p5 = p6 = p7 = 1

18
and p2 = 13 . Since p1 < p2 , we obtain C min{ 1+p32 p1 , p2 + p1
3 } = 7
18 by Theorem 2.3. However,
AC

by Theorem 2.2, only that C max{ 31 , p2 } = 1

3 can be obtained. Actually, the optimal makespan
7
of the instance equals exactly 18 , which is attained by letting (1) = (5) = 1, (2) = (6) = 2
and (3) = (4) = (7) = 3, and setting s1 = s2 = s3 = 0, s4 = 16 , s5 = s6 = s7 = 1
3 (see Fig. 2).
 ACCEPTED MANUSCRIPT

1 2 3 4 5 6 7

1 2 3

T
IP
1
t [ 0, )

CR
6

Idle
2 3 4

US
5 6 7 4 5 6 7
AN
1 2 3 1 2 3
M

t [, ) t [, )

ED

Figure 2: Illustration for an optimal solution of Instance 1

3 A better approximation algorithm for m QCs

PT

Recall that there are several 2-approximation algorithms in the literature [18, 17, 11] and an im-
proved analysis of one algorithm [11] for a small number of QCs [19]. In this section, we provide a
CE

better approximation algorithm and prove its performance ratio.

AC

3.1 Description of the algorithm

Denote by k = b m1
2 c, j0 = 0 and for any 1 q k, define jq as the hold satisfying that

jq 1 jq
X 2q X
pj < pj . (1)
m+1
j=1 j=1
 ACCEPTED MANUSCRIPT

It is clear that jq is well-defined and 1 j1 j2 jk n. Let set H(q 1 : q) consist of

contiguous holds indexed from jq1 + 1 to jq 1, i.e., H(q 1 : q) = {jq1 + 1, , jq 1}. Note
that H(q 1 : q) = when jq1 + 1 > jq 1. If H(q 1 : q) 6= , then

jq 1 jq1
X X X 2q 2(q 1) 2
pj = pj pj < = , (2)

T
m+1 m+1 m+1
jH(q1:q) j=1 j=1

IP
where the inequality is due to (1). For simplicity, we also denote H(k : n) = {jk + 1, , n}. An
intuitive illustration for the above definitions or notations is given in Fig. 3.

CR
1 2

H(0: 1)
j

H(1: 2)
j

US

H(k 1: k)
j

H(k: n)
n
AN
2 4
2( 1) 2
0 1
+1 +1 +1 +1

Figure 3: Illustration for the holds jq , H(q 1 : q) and H(k : n).

M
ED

To describe briefly, let P (q 1 : q) be the overall processing time of holds in the set H(q 1 : q),
P P
i.e., P (q 1 : q) = jH(q1:q) pj , q = 1, 2, , k, and also let P (k : n) = jH(k:n) pj .
PT

2 3
Lemma 3.1 If m is odd, then P (k : n) m+1 ; if m is even, then P (k : n) m+1 .
CE

Pjk
Proof. If m is odd, then k = b m1
2 c =
m1
2 . By (1), we have
2k m1
j=1 pj m+1 = m+1 . Thus,
P Pk
P (k : n) = jH(k:n) pj = 1 jj=1 m1
pj 1 m+1 2
= m+1 . If m is even, then k = b m1 m2
2 c = 2 .
Pjk 2k P jk
Moreover, by (1), we have j=1 pj m+1 = m2
m+1 . Similarly, we have P (k : n) = 1 j=1 pj
AC

3
m+1 . 2

Now adequate context has been provided to describe the algorithm. The algorithm partitions
the holds from the leftmost to the rightmost of the vessel into m subsets and processes each subset
independently by one of the m quay cranes, on the condition that each subset is not too large.
We call algorithms that consider such an idea as Partition-based Algorithms. Note there have been
three partition-based algorithms in the literature, i.e., APPX1 and APPX2 in [18] and another in
 ACCEPTED MANUSCRIPT

[11]. In our algorithm, a partition can be made easily if the last subset is small or if m is odd.
Otherwise, we first partition the holds into m + 1 subsets, then choose two adjacent ones from those
subsets and merge them together. This algorithm is named as Selected Partition-based Algorithm
or shortly denoted by SPA. For convenience, let H(q) = {jq }, q = 1, 2, , k. Below is the detailed
description.

T
Selected Partition-based Algorithm (SPA)

IP
1. For q = 1, 2, , k, determine jq by (1). In addition, partition the holds from left to right

CR
into 2k + 1 m subsets, i.e., H(0 : 1), H(1), H(1 : 2), H(2), , H(k 1 : k), H(k), H(k : n).

2
2. If P (k : n) m+1 , then assign one by one the current leftmost subset integrally to the
leftmost unutilised quay crane.

3. If P (k : n) > 2
m+1
US
(Note this happens only when m is even, i.e., m = 2k + 2), then find the
AN
hold jk+1 such that
jk+1 1 jk+1
X 1 X
pj < P (k : n) pj . (3)
2
j=jk +1 j=jk +1
M

The subset H(k : n) is further partitioned from left to right into three subsets, H(k : k + 1) =
{jk + 1, , jk+1 1}, H(k + 1) = {jk+1 } and H(k + 1 : n) = {jk+1 + 1, , n} (see Fig 4.).
ED

The total number of subsets attained is 2k + 3 = m + 1. Let P (k : k + 1) and P (k + 1 : n)

be the overall processing time of holds in H(k : k + 1) and H(k + 1 : n), respectively.

3.1 If P (k : k + 1) + pjk+1 = 12 P (k : n), then merge H(k : k + 1) and H(k + 1) into one.
PT

3.2 If P (k : k + 1) + pjk+1 > 12 P (k : n), then let P (r 1 : r) + pjr = minq=1,2, ,k+1 {P (q 1 :

q) + pjq }, where ties are broken arbitrarily.
CE

3.2.1 If P (r 1 : r) + pjr pjk+1 + P (k + 1 : n), then merge H(r 1 : r) and H(r) into
one.
AC

3.2.2 If P (r 1 : r) + pjr > pjk+1 + P (k + 1 : n), then merge H(k + 1) and H(k + 1 : n)
into one.

3.3 Each time choose the unassigned leftmost subset and assign it integrally to the leftmost
unutilised quay crane.
 ACCEPTED MANUSCRIPT

10

H(k: n)

j j n

H(k + 1: n)

T
H(k: k + 1)

IP
P(k: n)
2

CR
Figure 4: Partition the subset H(k : n).

3.2 Analysis of the algorithm

US
Since any partition-based algorithm (e.g., SPA) assigns a subset of holds integrally to an unutilised
quay crane, the makespan must be determined by one of the subsets. More precisely, it is attained
AN
by the subset with the maximum total processing time. The following observation further proves
2
that a partition-based algorithm can be bounded within 2 m+1 if there are not too many subsets
and the total processing time of each subset is not too large.
M

Lemma 3.2 If a partition-based algorithm A can partition holds into at most m subsets and the
ED

2 2
overall processing time of each subset is no more than max{ m+1 , pmax }, then C A (2 m+1 )C .

2
Proof. If it is the case, then C A max{ m+1 , pmax }. Combining it with the fact C
PT

1 2
max{ m , pmax } from Theorem 2.2, we get C A (2 m+1 )C . 2
CE

2 2
Lemma 3.3 If either P (k : n) m+1 or P (k : n) > m+1 and P (k : k + 1) + pjk+1 = 12 P (k : n),
2 2
then C SP A max{ m+1 , pmax } (2 m+1 )C .
AC

2 2
Proof. By (2), P (q 1 : q) m+1 . If P (k : n) m+1 , then

2
C SP A = max {P (q 1 : q), pjq , P (k : n)} max{ , pmax }.
q=1,2, ,k m+1

2
If P (k : n) > m+1 and P (k : k + 1) + pjk+1 = P (k + 1 : n), then by Lemma 3.1, it happens only
P (k:n) 3 2
when m is even, i.e., m = 2k + 2. Besides, we have P (k : k + 1) + pjk+1 = 2 2(m+1) < m+1
by Lemma 3.1. In accordance with the algorithms rule, the two subsets H(k : k + 1) and H(k + 1)
 ACCEPTED MANUSCRIPT

11

have to be merged into one. Thus, we have

2
C SP A = max {P (q 1 : q), pjq , P (k : k + 1) + pjk+1 , P (k + 1 : n)} max{ , pmax }.
q=1,2, ,k m+1

2
Since in both cases, C SP A max{ m+1 , pmax }, the desired result can follow by Lemma 3.2. 2

T
2
From Lemma 3.1 and Lemma 3.3, the only remaining case is that m = 2k + 2, P (k : n) > m+1

IP
and P (k : k + 1) + pjk+1 > 21 P (k : n). In this case, SPA has to choose two adjacent subsets from
the 2k + 3 = m + 1 subsets and merge them into one. Since each of the 2k + 3 = m + 1 subsets

CR
2
have an overall processing time of no more than max{ m+1 , pmax } by (2), (3) and Lemma 3.1, the
desired bound holds from Lemma 3.2 as long as the processing time of the merged subset does not

US
2
exceed m+1 . For this reason, let us assume in the following discussion that the processing time of
2
the merged subset is strictly larger than m+1 and that the makespan of the algorithm is determined
by this merged subset, which we refer to in the remainder case. By Step 3.2.1 and 3.2.2 of the
AN
algorithm, the remainder case satisfies that

2
C SP A = min {P (q 1 : q) + pjq , pjk+1 + P (k + 1 : n)} > . (4)
q=1,2, ,k+1 m+1
M

Consequently, we have
ED

X k+1
SP A 1 2(1 + pjk+1 )
C {pjk+1 + P (k + 1 : n) + (P (q 1 : q) + pjq )} = . (5)
k+2 m+2
q=1
PT

By (4), it follows that

2
P (k : k + 1) + pjk+1 > (6)
m+1
CE

and
2
pjk+1 + P (k + 1 : n) > . (7)
m+1
AC

From Lemma 3.1 and note that m is even, we get

3
P (k : n) = P (k : k + 1) + pjk+1 + P (k + 1 : n) .
m+1

Combining it with (6) and (7), we can deduce

1
P (k + 1 : n) < < pjk+1 , (8)
m+1
 ACCEPTED MANUSCRIPT

12

Pn
which means that j=jk+1 +1 pj < pjk+1 . By Theorem 2.3, it yields that

1 + pjk+1 P (k + 1 : n) P (k + 1 : n)
C min{ , pjk+1 + }. (9)
m m

Based on the above, we close the remainder case.

T
2
Lemma 3.4 In the remainder case, it is still valid that C SP A (2 m+1 )C .

IP
Proof. We distinguish two subcases according to the right side of (9).

CR
1+pjk+1 P (k+1:n)
Case 1. If C m , then by (5),

C SP A 2m 1 + pjk+1

C

< US
m + 2 1 + pjk+1 P (k + 1 : n)
2m (m + 2)P (k + 1 : n)
m + 2 (m + 2)P (k + 1 : n) P (k + 1 : n)
2m 2
AN
= =2 ,
m+1 m+1

where the second inequality is due to 1 + pjk+1 > (m + 2)P (k + 1 : n) by (8).

M

P (k+1:n)
Case 2. If C pjk+1 + m , then by (5), and together with (7) and (8), we can conclude
that
ED

C SP A 2m 1 + pjk+1

C m + 2 mpjk+1 + P (k + 1 : n)
2m 1 + pjk+1
=
PT

m + 2 (m 1)(1 + pjk+1 ) + (pjk+1 + P (k + 1 : n)) (m 1)

2m 1 + pjk+1
2
m + 2 (m 1)(1 + pjk+1 ) + m+1 (m 1)
CE

2m 1 + pjk+1
=
m + 2 (m 1)(1 + pjk+1 ) m2 3
m+1
1
2m 1+ m+1
AC

1 m2 3
m + 2 (m 1)(1 +
m+1 ) m+1
2m 2
= =2 .
m+1 m+1

Hence, we are done. 2

Finally, by Lemma 3.3 and Lemma 3.4, our main result follows.

2
Theorem 3.5 The worst case ratio of SP A is no larger than 2 m+1 .
 ACCEPTED MANUSCRIPT

13

3.3 Discussion on partition-based algorithms

Note that a partition-based algorithm, partitions the holds into m subsets and process each subset
by one quay crane independently. Other than SPA, three partition-based algorithms were found
in the literature, all of which were shown to be 2-approximation. A simplified description of these

T
algorithms can be as follows.

IP
APPX1(EPA)[18]

Each time compute the unassigned leftmost holds with an overall processing time no smaller

CR
1
than m and choose the smallest one to form a subset. If m 1 subsets are determined, then the rest
of the holds form the last subset. Let us call APPX1 as Easy Partition-based Algorithm (EPA).

GPA[11]

US
We call the algorithm in [11] as Greedy Partition-based Algorithm (GPA). The difference between
GPA and EPA is that GPA always forms a subset with an overall processing time closest to 1
AN
m
among all the unassigned leftmost holds.

APPX2(CPA)[18, 14]
M

Using a dynamic programming procedure, it can choose the best m-subset-partition. We call
this algorithm as Complete Partition-based Algorithm (CPA).
ED

It is clear that CPA is at least as good as SPA. By Theorem 3.5, we have

2
Corollary 3.6 The worst case ratio of CPA is no larger than 2 m+1 .
PT

The following instances indicate that the worst case ratio of EPA is no smaller than 2 and that
1
of GPA when m > 2 is no smaller than 2 m.
CE

Instance 2: Let there be 2m holds. The leftmost m holds all have the same processing time of
1
m  (called large holds), while the rightmost m holds all have the same processing time of  > 0
AC

2
(called small holds). It is easy that C EP A = m 2 by the algorithms rule. However, an optimal
solution may first process m large holds evenly on m QCs, then m small holds evenly on m QCs,
1 C EP A
resulting that C = m. Thus, we have C = 2 2m 2 (when  0).
1
Instance 3: The structure of this instance is the same with Instance 2, where we let  = m2
.
1 1 1 1 1
Accordingly, C = m. Since 2( m ) m m (m ) due to m > 2, the algorithm GPA would
assign the first m 1 large hold evenly to m 1 QCs and assign the other holds to the last QC,
1 2m1 C GP A 1
such that C GP A = ( m ) + m = m2
. Thus, we have C =2 m.
 ACCEPTED MANUSCRIPT

14

Partition-based algorithm Lower bound Upper bound Time complexity

EPA 2[18] 2[18] O(n)[18]
1
GPA(m > 3) 2 m * 2[11]
5 5
GPA(m = 3) 3 * 3 [19] O(n)[11]
4 4
GPA(m = 2) 3 [19] 3 [19]
2 2
CPA 2 m+1 * 2 m+1 * O(mn log n)[14]

T
2 2
SPA 2 m+1 * 2 m+1 * O(n)*

IP
Table 1: Comparison of partition-based algorithms (* this paper)

CR
In [19], Liu et al provided a better analysis of GPA for m = 2 and m = 3, where the worst case
4
ratios are shown to be no larger than 3 and 35 , respectively. In addition, they constructed a tight
instance for m = 2. With Instance 3, the tightness for m = 3 remains valid as well. We now prove

US
a lower bound on the worst case ratio that a partition-based algorithm can reach.

Theorem 3.7 The worst case ratio of any partition-based algorithm is no smaller than 2 2
m+1 .
AN
Hence, CP A and SP A are the best possible algorithms for partitions.

Proof. Consider another instance structured like Instance 2.

M

1 1
Instance 4: The processing times of each large and small holds are m+1 and m(m+1) , respectively.
1
Clearly C = m . If a partition-based algorithm A assigns two of the large holds to one quay
ED

2
crane, then C A m+1 . Otherwise, all the holds except the leftmost m 1 large ones have to be
1 1 2
assigned to one single quay crane for partitioning, thus we have C A m m(m+1) + m+1 = m+1 .
PT

2
Therefore, C A (2 m+1 )C . 2

Thus far, to the best of our knowledge, there is only one polynomial time algorithm that does
CE

not partition, namely APPX3 by Lim et al. [18]. It can be seen as an extension of APPX2 (CPA)
by using a O(m2 n3 )-time dynamic programming procedure on any partial sequence of holds so
that either it is partitioned like CPA or it is divided into two subsequences and processed one after
AC

another. It is clear that APPX3 performs no worse than any partition-based algorithm. In [18],
the authors provided an upper bound of 2 for APPX3. A comparison of existing partition-based
algorithms is made in Table 1.
 ACCEPTED MANUSCRIPT

15

4 Scheduling two QCs with different speeds

This section studies two uniform quay crane scheduling problems, where QCs might have different
speeds for handling tasks. Without loss of generality, let the left quay crane (QC 1) have a speed
1 and the right quay crane (QC 2) have a speed s 1. In other words, a hold j can either be

T
p
processed by QC 1 with a time of pj or be processed by QC 2 with a time of sj . Recall that
Pn

IP
j=1 pj = 1 and pmax = maxj=1,2, ,n {pj } have similar lower bounds as those in Theorem 2.2 and
Theorem 2.3.

CR
1
Corollary 4.1 C max{ 1+s , pmax
s }.

Pl1

US
p
pl 1+ sl L L
Corollary 4.2 If L = j=1 pj < s for some hold l 1, then C min{ 1+s , pl + 1+s };
P 1+pr R
Symmetrically, if R = nj=r+1 pj < spr for some hold r n, then C min{ 1+s s , psr + 1+s
R
}.
AN
1+s
By the simple partition idea, we can design a 1+s+s2
-approximation algorithm for two uniform
QCs. Here is the detailed description (See also Fig. 5).

A Partition-based Algorithm for two Uniform QCs (PA2U in short)

M

Find the hold c such that

c1
X X c
1
L= pj < pj . (10)
ED

1+s
j=1 j=1
Pn pc +R
Let R = 1 L pc = j=c+1 pj . If L + pc s , then assign the leftmost c holds to QC 1 and
PT

the others to QC 2. Otherwise, assign the leftmost c 1 holds to QC 1 and the others to QC 2.
CE

1 2 c n-1 n
AC

L R
1
1+

Figure 5: Illustration for algorithm PA2U.

1
Lemma 4.3 If L + pc = 1+s , then C P A2U = C .
 ACCEPTED MANUSCRIPT

16

1 s R pc +R
Proof. By L + pc = 1+s , we get R = 1 L pc = 1+s . Thus L + pc = s < s , which follows
1
C P AU = L + pc = 1+s = C by the algorithms rule and Corollary 4.1. 2

Lemma 4.4 If L + pc > 1

1+s , then C P A2U = min{L + pc , pc +R
s }
1+pc
1+s .

T
1 R
Proof. By (10), L < 1+s < L + pc . Combining it with R = 1 L pc , we have L + pc > s and

IP
pc +R
s > L. By the algorithms rule, we obtain C P A2U = max{L + pc , Rs } = L + pc if L + pc pc +R
s
and C P AU = max{L, pc +R
s } =
pc +R
on the contrary. Hence, C P A2U pc +R
= min{L + pc , s }

CR
s
1 s pc +R 1+pc
1+s (L + pc ) + 1+s s = 1+s . 2

By Lemma 4.4, if we have min{L + pc , pc +R

s }
1+s
1+s+s2
, then together with Corollary 4.1, we
have
C P A2U = min{L + pc ,
s
US
pc + R
}
1+s
1 + s + s2

(1 + s)2
1 + s + s2
C .
AN
For this reason, we suppose that
1+s
L + pc > (11)
1 + s + s2
M

and
s + s2
pc + R > . (12)
1 + s + s2
ED

Combining (11), (12), and the fact L + pc + R = 1, it further follows

s
pc = (L + pc ) + (pc + R) 1 > , (13)
1 + s + s2
PT

1 pc
L = 1 (pc + R) < < (14)
1 + s + s2 s
CE

and
s2
R = 1 (L + pc ) < < spc . (15)
1 + s + s2
AC

This is sufficient to prove the result.

1+s
Theorem 4.5 The worst case ratio of PA2U is no larger than 1+s+s2
for any s 1.

1+ psc L L
Proof. By (14) and Corollary 4.2 , we have C min{ 1+s , pc + 1+s }. Two cases are
distinguished.
 ACCEPTED MANUSCRIPT

17

L
Case 1. C pc + 1+s . Together with Lemma 4.4, (11) and (13), we can deduce that

1+p s
C P A2U 1+s
c
1 + pc 1 + pc 1+ 1+s+s2 (1 + s)2

L
= < 1+s < s2
= .
C pc + 1+s spc + (L + pc ) spc + 1+s+s 2
1+s
+ 1+s+s 1 + s + s2
1+s+s2 2

1+ psc L
Case 2. C By Lemma 4.4, C P A2U = min{L + pc , pc +R

T
1+s . s }.
pc +R pc +R
then C P A2U =

IP
Subcase 2.1 If L + pc > s , s . Combining it with (15) and the fact
1 L = pc + R, we have

CR
pc +R
C P A2U s (1 + s)(pc + R) 1+s 1+s (1 + s)2
1+ psc L
= = pc < pc = .
C pc + s(pc + R) pc +R+s +s
pc +spc 1 + s + s2
1+s

Subcase 2.2 If L + pc
pc + R = 1 L, we can deduce
pc +R
s ,
US
then C P A2U = L + pc . In addition, by L + pc pc +R
s and
AN
(s + 1)L + spc 1. (16)
1+ psc L
Now, we assume that (1 + s + s2 )C P A2U > (1 + s)2 C , i.e., (1 + s + s2 )(L + pc ) > (1 + s)2 1+s .
By a simple calculation, it follows that s(2 + 2s + s2 )L + (1 + s2 + s3 )pc > s(s + 1) or due to (14)
M

and (16), it is equivalent with

pc
ED

s(s + 1) < s(2 + 2s + s2 )L + (1 + s2 + s3 )pc = s(s + 1){(s + 1)L + spc } + s(L ) < s(s + 1),
s
(1+s)2
, which is a contradiction. Hence, we must have C P A2U 1+s+s2
C . 2
PT

To show the tightness, consider the following instance.

1 s s2
Instance 5: There are four holds with p1 = , p2 = , p3 = and p4 =
CE

1+s+s2 1+s+s2 (1+s)(1+s+s2 )

s3
(1+s)(1+s+s2 )
. Since p1 < 1
1+s < p1 + p2 , we have C P A2U = min{p1 + p2 , p2 +ps3 +p4 } = 1+s+s
1+s
2 by

Lemma 4.4 and the algorithms rule. However, an optimal solution can first simultaneously process
AC

p1 by QC 1 and p2 by QC 2, then simultaneously process p3 by QC 1 and p4 by QC 2, resulting

C P A2U (1+s)2
that C = max{p1 + p3 , p3 +p
s }=
4 1
1+s . Thus, it follows C = 1+s+s2
for any s 1.

With Instance 5 and similar arguments as Theorem 3.7, we also have

Theorem 4.6 Any partition-based algorithm for two uniform QCs must have a worst case ratio
1+s
no smaller than 1+s+s2
. Hence P A2U is a best possible partition-based algorithm for two uniform
QCs.
 ACCEPTED MANUSCRIPT

18

5 Computational experiments

In Section 3.3, we compared four existing partition-based algorithms in the theoretical sense. Now
a series of computational experiments are conducted to examine the average performance of these
algorithms. For an algorithm A, its error bound (or gap) is denoted by the following percentage,

T
CA C

IP
GAPA = 100%,
C

where the optimal value C is estimated by the lower bounds given in Theorem 2.2 and 2.3.

CR
To show the performance of those partition-based algorithms, 500 instances were randomly
generated for each algorithm. For each instance, the workload/processing time of a hold followed a

US
uniform discrete distribution in the range [30, 180]. For each algorithm, we computed the maximum
and average gap among the 500 instances. Table 2 summarised the results of instances with small
sizes that the number (n) of holds and the number (m) of cranes that ranged in [6, 30] and [2, 4],
AN
respectively. Table 3 summarised the results of instances with large sizes for the numbers n and m
within the range [50, 300] and [6, 15], respectively.
M

From Table 2 and Table 3, we found that though SPA is shown to be as good as CPA in the
theoretical sense, it performs much worse than the other partition-based algorithms for random
instances except the two-quay-crane case. This is perhaps because in SPA, it becomes probable
ED

that a quay crane might choose a subset of holds with a heavy workload, resulting in a bad instance.
However, the combination of GPA and SPA (denoted as GSPA), which always outputs the better
PT

solution between GPA and SPA, would maintain a linear running time and can handle most of
such bad instances. Consider for example that the average gap of GSPA for small sized instances
CE

is no more than 25.91% (attained when n m = 7 4) and it is at most 2.49% upon that of
CPA; the average gap of GSPA for large sized instances is no more than 26.27% (attained when
n m = 50 15) and it is at most 9.78% upon that of CPA. It is also observed that the maximum
AC

gap of GPA might exceed 100% for some instances (see Table 3), while GSPA can always avoid
such bad cases.

6 Conclusion

We considered the problem of scheduling quay cranes to serve a berthed container vessel. The
objective is to minimise the makespan of the vessel subject to the non-crossing constraints between
 ACCEPTED MANUSCRIPT

19

GAPEP A GAPGP A GAPCP A GAPSP A GAPGSP A

nm Aver Max Aver Max Aver Max Aver Max Aver Max
62 19.12% 71.61% 9.81% 30.10% 9.81% 30.10% 9.81% 30.10% 9.81% 30.10%
63 38.74% 93.59% 20.25% 64.04% 18.47% 45.28% 33.73% 50.00% 19.81% 49.27%
64 51.99% 92.67% 24.82% 89.08% 20.05% 51.01% 27.79% 59.84% 21.48% 58.63%
72 17.38% 49.11% 8.83% 27.47% 8.83% 27.47% 8.83% 27.47% 8.83% 27.47%
73 33.86% 77.88% 18.00% 59.75% 16.70% 40.25% 37.02% 50.00% 17.91% 48.89%
74 49.38% 91.71% 28.75% 94.69% 23.43% 52.43% 34.74% 59.90% 25.91% 57.58%

T
82 14.79% 47.53% 7.39% 22.33% 7.39% 22.33% 7.39% 22.33% 7.39% 22.33%
83 31.13% 73.66% 15.64% 56.36% 14.56% 34.95% 38.93% 50.00% 15.59% 49.03%

IP
84 45.20% 89.09% 25.86% 90.01% 22.27% 46.71% 38.07% 59.90% 24.54% 58.87%
92 13.02% 43.13% 6.76% 22.36% 6.76% 22.36% 6.76% 22.36% 6.76% 22.36%
93 26.72% 79.12% 14.47% 48.07% 13.35% 31.93% 40.46% 50.00% 14.47% 48.07%

CR
94 40.96% 82.90% 22.41% 88.54% 18.95% 42.67% 38.09% 59.82% 21.25% 52.31%
10 2 12.15% 35.67% 6.03% 19.07% 6.03% 19.07% 6.03% 19.07% 6.03% 19.07%
10 3 25.18% 60.15% 12.34% 46.94% 11.35% 28.93% 40.83% 50.00% 12.34% 46.94%
10 4 37.53% 72.55% 20.12% 65.71% 17.28% 38.87% 39.96% 60.00% 19.47% 56.73%
15 2 7.50% 21.84% 3.84% 14.71% 3.84% 14.71% 3.84% 14.71% 3.84% 14.71%
15 3
15 4
20 2
20 3
16.50% 36.88%
24.50% 51.23%
5.80% 17.90%
12.66% 29.21%
8.53%

2.78%
6.26%
24.86%
14.02% 51.09%
9.09%
21.24%
US
7.84%

2.78%
5.77%
18.97%
12.11% 25.34%
9.09%
16.77%
44.17% 50.00%
44.35% 59.89%
2.78% 9.09%
45.79% 50.00%
8.53%

2.78%
6.26%
24.86%
13.92% 42.22%
9.09%
21.24%
AN
20 4 18.67% 36.38% 10.41% 36.89% 8.78% 19.90% 47.72% 60.00% 10.41% 36.89%
25 2 4.96% 13.54% 2.34% 7.15% 2.34% 7.15% 2.34% 7.15% 2.34% 7.15%
25 3 9.47% 23.97% 5.09% 16.36% 4.68% 13.09% 46.48% 49.95% 5.09% 16.36%
25 4 15.18% 28.13% 8.20% 26.74% 6.94% 17.21% 50.85% 60.00% 8.20% 26.74%
30 2 3.84% 11.09% 1.89% 5.36% 1.89% 5.36% 1.89% 5.36% 1.89% 5.36%
M

30 3 7.87% 18.53% 4.29% 12.40% 3.97% 9.55% 47.03% 50.00% 4.29% 12.4%
30 4 12.47% 23.93% 6.80% 27.54% 5.83% 13.89% 52.57% 60.00% 6.80% 27.54%

Table 2: Results of random instances with small sizes

ED

quay cranes. We designed a Selected Partition-based Algorithm (SPA) for m quay cranes and
2
demonstrated its worst case ratio to be 2 m+1 , which is better than several previous algorithms.
PT

In addition, we showed that SPA is one of the best possible algorithm for the purpose of partition-
ing. For two quay cranes with different processing hold speeds, the best possible partition-based
CE

(1+s)2
algorithm with worst case ratio 1+s+s2
is also provided, where s 1 is the speed ratio of the two
QCs. Computational experiments have been performed to examine the partition-based algorithms.
The results showed that SPA performs even worse than existing partition-based algorithms, never-
AC

theless, the combination of SPA and GPA is effective and efficient enough for solving the QCSP.

Several questions deserve further study. First, how to design and analyse a simple algorithm that
does not consider partitioning. Any algorithm with theoretical performance ratio strictly smaller
than 2 (even when m tends to infinity) would be interesting. Secondly, it is a natural question
to extend the results of this paper to m uniform quay cranes. The double-cycling problem where
loading and unloading are simultaneously incorporated also deserves further study. In addition, this
 ACCEPTED MANUSCRIPT

20

GAPEP A GAPGP A GAPCP A GAPSP A GAPGSP A

nm Aver Max Aver Max Aver Max Aver Max Aver Max
50 6 13.10% 23.82% 7.45% 23.59% 5.74% 12.72% 65.63% 71.43% 7.45% 23.59%
50 8 18.82% 29.40% 11.22% 46.17% 8.16% 15.02% 70.86% 77.78% 11.22% 46.17%
50 13 32.83% 47.73% 21.15% 141.02% 13.89% 21.66% 78.89% 85.68% 20.97% 83.08%
50 14 36.04% 51.05% 26.65% 132.38% 15.37% 25.46% 77.19% 86.67% 26.10% 84.20%
50 15 39.23% 55.04% 26.51% 113.58% 16.49% 25.74% 79.74% 87.46% 26.27% 86.72%
60 6 10.94% 18.34% 6.06% 25.49% 4.80% 9.38% 66.74% 71.40% 6.06% 25.49%

T
60 8 15.76% 25.18% 9.84% 38.11% 6.86% 13.25% 71.95% 77.78% 9.84% 38.11%
60 13 27.53% 40.06% 18.42% 78.01% 11.91% 20.83% 80.03% 85.66% 18.42% 78.01%

IP
60 14 29.90% 42.41% 21.21% 101.72% 12.61% 20.56% 79.08% 86.64% 21.06% 80.19%
60 15 32.72% 45.01% 22.96% 98.14% 13.53% 21.23% 80.88% 87.50% 22.87% 84.90%
80 6 8.15% 13.39% 4.72% 15.07% 3.66% 7.67% 67.89% 71.43% 4.72% 15.07%

CR
80 8 11.66% 17.51% 6.94% 23.86% 5.09% 9.68% 73.44% 77.76% 6.94% 23.86%
80 13 20.94% 29.62% 13.27% 53.61% 8.68% 12.94% 81.49% 85.71% 13.27% 53.61%
80 14 22.37% 31.67% 15.89% 67.77% 9.58% 14.67% 80.46% 86.62% 15.89% 67.77%
80 15 24.33% 33.72% 18.02% 92.27% 10.24% 15.63% 82.47% 87.50% 18.00% 80.38%
100 6 6.44% 10.66% 3.77% 13.32% 2.96% 5.97% 68.64% 71.43% 3.77% 13.32%
100 8
100 13
100 14
100 15
9.19% 14.74%
16.68% 23.46%
18.25% 25.71%
19.78% 25.95%
5.89%
11.06%
12.88%
13.04%
22.41%
44.27%
55.29%
48.55%
US
4.17%
7.06%
7.64%
8.24%
7.37%
12.53%
12.58%
12.23%
74.51% 77.75%
82.03% 85.71%
81.80% 86.61%
83.97% 87.50%
5.89% 22.41%
11.06% 44.27%
12.88% 55.29%
13.04% 48.55%
AN
200 6 3.27% 5.32% 1.88% 7.27% 1.49% 2.81% 69.98% 71.40% 1.88% 7.27%
200 8 4.65% 7.06% 2.90% 9.12% 2.07% 4.02% 76.10% 77.77% 2.90% 9.12%
200 13 8.33% 11.23% 5.77% 21.81% 3.52% 5.86% 84.08% 85.69% 5.77% 21.81%
200 14 9.06% 12.32% 6.36% 25.01% 3.84% 6.22% 84.25% 86.66% 6.36% 25.01%
200 15 10.04% 13.44% 6.56% 27.40% 4.09% 6.83% 85.58% 87.49% 6.56% 27.40%
M

300 6 2.21% 3.36% 1.26% 4.79% 0.97% 2.11% 70.45% 71.43% 1.26% 4.79%
300 8 3.07% 4.46% 2.00% 7.85% 1.38% 2.84% 76.64% 77.77% 2.00% 7.85%
300 13 5.57% 7.45% 3.71% 15.78% 2.33% 3.69% 84.56% 85.71% 3.71% 15.78%
300 14 6.11% 8.26% 3.93% 18.28% 2.52% 4.36% 84.96% 86.66% 3.93% 18.28%
ED

300 15 6.60% 8.52% 4.55% 19.88% 2.74% 4.29% 86.25% 87.50% 4.55% 19.88%

Table 3: Results of random instances with large sizes

PT

paper only focuses on non-crossing constraints of the QCSP. In the more general setting, there are
non-interference constraints that cover both non-crossing constraints and safety margins between
CE

QCs, where a safety margin signifies a certain number of in-between holds between adjacent QCs.
It is of great interest to understand how to approximate the general QC scheduling with non-
interference constraints.
AC

Acknowledgement The first author was supported by the Zhejiang Provincial Natural Sci-
ence Foundation of China (LY16A010015) and the National Natural Science Foundation of China
(11201105). The third author was supported by the National Natural Science Foundation of China
(11401149). The fourth author was supported by the National Natural Science Foundation of China
(11571252). The authors would like to acknowledge the anonymous referees for their careful reading
of our paper and their valuable comments.
 ACCEPTED MANUSCRIPT

21

References

[1] Meersmans, P. J. M., Dekker, R. (2001). Operations research supports container handling.
Econometric Institute Report, 234, Erasmus University Rotterdam.

[2] Vis, I. F. A., de Koster, R. (2003). Transshipment of containers at a container terminal: an

T
overview. European Journal of Operational Research, 147 (1), 1-16.

IP
[3] Vacca, I., Bierlaire, M., Salani, M. (2007). Optimization at container terminals: Status, trends

CR
and perspectives. In: Proceedings of the Swiss Transport Research Conference (STRC). Monte
Verita/Ascona, pp. 1-21.

US
[4] Goodchild, A., Zhao, W., Wygonik, E. (2010). Decision problems and applications of oper-
ations research at marine container terminals. In: J.J. Cochran, L.A. Cox, P. Keskinocak,
J.P. Kharoufeh, J.C. Smith(Eds.), Wiley encyclopedia of operations research and management
AN
science (pp.1-20). John Wiley & Sons, Inc.

[5] Lehnfeld, J., Knust, S. (2014). Loading, unloading and premarshalling of stacks in storage
M

areas: Survey and classification. European Journal of Operational Research, 239(2), 297-312.

[6] Bierwirth, C., Meisel, F. (2010). A survey of berth allocation and quay crane scheduling
ED

problems in container terminals. European Journal of Operational Research, 202, 615-627.

[7] Bierwirth, C., Meisel, F. (2015). A follow-up survey of berth allocation and quay crane schedul-
ing problems in container terminals. European Journal of Operational Research, 244, 675-689.
PT

[8] Ng, W. C. (2005). Crane scheduling in container yards with inter-crane interference. European
CE

Journal of Operibiational Research, 164, 64-78.

[9] Kim, K. H., Park, Y. M. (2004). A crane scheduling method for port container terminals.
European Journal of Operational Research, 156(3), 752-768.
AC

[10] Moccia, L., Cordeau, J. F., Gaudioso, M., Laporte, G. (2006). A branch-and-cut algorithm for
the quay crane scheduling problem in a container terminal. Naval Research Logistics, 53(1),
45-59.

[11] Lee, D. H., Wang, H. Q., Miao, L. (2007). An approximation algorithm for quay crane schedul-
ing with noninterference constraints in port container terminals. Presented at Tristan VI,
Phuket, June 10-15.
 ACCEPTED MANUSCRIPT

22

[12] Lee, D. H., Wang, H. Q., Miao, L. (2008). Quay crane scheduling with non-interference con-
straints in port container terminals. Transportation Research Part E, 44, 124-135.

[13] Zhu, Y., Lim, A. (2006). Crane scheduling with non-crossing constraint. Journal of the Oper-
ation Research Society, 57(12), 1464-1471.

T
[14] Lee, D. H., Chen, J. H. (2010). An improved approach for quay crane scheduling with non-

IP
crossing constraints. Engineering Optimization, 42(1), 1-15.

CR
[15] Lim, A., Rodrigues, B., Xiao, F., Zhu, Y. (2004). Crane scheduling with spatial constraints.
Naval Research Logistics, 51, 386-406.

US
[16] Shang, X. T., Cao, J. X., Ren, J. (2016). A robust optimization approach to the integrated
berth allocation and quay crane assignment problem. Transportation Research Part E, 94,
44-65.
AN
[17] Lim, A., Rodrigues, B., Xu, Z. (2007). A m-parallel crane scheduling problem with a non-
crossing constraint. Naval Research Logistics, 54, 115-127.
M

[18] Lim, A., Rodrigues, B., Xu, Z. (2004). Approximation Schemes for the Crane Scheduling
Problem. Hagerup, T., Katajainen, J. (Eds.): SWAT2004, LNCS, 3111, pp. 323-335.
ED

[19] Liu, M., Zheng, F. F., Li, J. F. (2015). Scheduling small number of quay cranes with non-
interference constraint. Optimization letters, 9(2), 403-412.
PT

[20] Turkogullari, Y. B., Taskin, Z. C., Aras, N., Altinel, I.K. (2016). Optimal berth allocation,
time-variant quay crane assignment and scheduling with crane setups in container terminals.
CE

European Journal of Operational Research, 254 (3), 985-1001.

[21] Goodchild, A. V., Daganzo, C. F. (2006). Double-cycling strategies for container ships and
AC

their effect on ship loading and unloading operations. Transportation Science 40(4), 473-483.

[22] Goodchild, A. V., Daganzo, C. F. (2007). Crane double cycling in container ports: Planning
methods and evaluation. Transportation Research Part B: Methodological, 41(8), 875-891.

[23] Lee, C. Y., Liu, M., Chu, C. B. (2015). Optimal algorithm for the general quay crane double-
cycling problem. Transportation Science, 49(4), 957-967.