European Journal of Operational Research 232 (2014) 198–208

Contents lists available at SciVerse ScienceDirect

European Journal of Operational Research

journal homepage: www.elsevier.com/locate/ejor

Innovative Applications of O.R.

An effective mathematical formulation for the unidirectional

cluster-based quay crane scheduling problem
Jiang Hang Chen a,⇑, Der-Horng Lee b, Mark Goh c
a
Transport and Mobility Laboratory, École Polytechnique Fédérale de Lausanne, Switzerland
b
Department of Civil Engineering, National University of Singapore, Singapore
c
The Logistics Institute – Asia Pacific, National University of Singapore, Singapore

a r t i c l e i n f o a b s t r a c t

Article history: The quay crane scheduling problem plays an important role in the paradigm of port container terminal
Received 22 November 2011 management, due to the fact that it closely relates to vessel berthing time. In this paper, we focus on
Accepted 26 June 2013 the study of a special strategy for the cluster-based quay crane scheduling problem that forces quay
Available online 5 July 2013
cranes to move unidirectionally during the scheduling. The scheduling problem arising when this strat-
egy is applied is called the unidirectional quay crane scheduling problem in the literature. Different from
Keywords: other researches attempting to construct more sophisticated searching algorithms, in this paper, we seek
(S) Scheduling
for a more compact mathematical formulation of the unidirectional cluster-based quay crane scheduling
Port container terminal
Unidirectional quay crane scheduling
problem that can be easily solved by a standard optimization solver. To assess the performance of the
problem proposed model, commonly accepted benchmark suites are used and the results indicate that the pro-
Mathematical formulation posed model outperforms the state-of-the-art algorithms designed for the unidirectional cluster-based
quay crane scheduling problem.
Ó 2013 Elsevier B.V. All rights reserved.

1. Introduction In the literature, generally speaking, the QCSP can be classified

into two categories by the definition of the tasks assigned to quay
Quay cranes, one of the scarce resources in port container ter- cranes and handled in a non-preemptive manner, i.e., the bay-
minals, are crucial machines loading and discharging containers based QCSP and the cluster-based QCSP. For the former, a task is
onto and from vessels. As the need to satisfy customers (i.e., ship the lump sum of all the loading and unloading jobs located in
carriers) has become more acute, how to reduce vessel service time the same bay. For the latter, a task is defined as a discharging or
remains an important issue for terminal managers. In this regard, loading operation for a cluster which is a collection of adjacent
the quay crane scheduling problem (QCSP) is the most important slots holding the containers with the same loading/destination
and its output usually serves as the input for the immediate deci- port, or the same size, etc. (Kim & Park, 2004).
sions in port container terminals such as the yard truck and yard For the bay-based QCSP, Daganzo (1989) and Peterkofsky and
crane scheduling problems. According to Moccia, Cordeau, Gaudi- Daganzo (1990) introduced the static and dynamic QCSP for multi-
oso, and Laporte (2006), the objective of a QCSP is to determine ple vessels. However, both studies excluded the consideration to
‘‘a sequence of unloading and loading movements for cranes as- prevent the spatial interferences. In Lim, Rodrigues, Xiao, and
signed to a vessel in order to minimize the vessel completion time Zhu (2004), the bay-based QCSP was represented by a bipartite
as well as the crane idle times’’. Here the idle time is referred to the graph matching problem. The downside of this approach is that
time which ‘‘originates from interferences between cranes since the profit value associated with a crane-to-task assignment is not
these roll on the same rails, and thus cannot cross each other, well-defined from a practical point of view. Lim, Rodrigues, and
and from the need to maintain a minimum safety distance be- Xu (2004) also analyzed the properties of the bay-based QCSP
tween them’’. These two kinds of spatial requirements are named but only considering non-crossing constraints. Based on the study,
non-crossing constraint and safety distance constraint, respec- a full polynomial time approximation scheme and three approxi-
tively in the literature. They create the most fundamental differ- mation algorithms were proposed to solve the proposed problem.
ence between the QCSP and the traditional parallel machine In Zhu and Lim (2006), a mixed integer programming (MIP) model
scheduling problem. was developed for the bay-based QCSP with non-crossing con-
straint and it was solved by a branch-and-bound algorithm and a
simulated annealing heuristic. As a summary work, Lim, Rodrigues,
⇑ Corresponding author. Tel.: +41 21 693 25 32; fax: +41 21 693 80 60. and Xu (2007) presented a numerical experiment designed to
E-mail address: jianghang.chen@epfl.ch (J.H. Chen).

0377-2217/$ - see front matter Ó 2013 Elsevier B.V. All rights reserved.
http://dx.doi.org/10.1016/j.ejor.2013.06.051
 J.H. Chen et al. / European Journal of Operational Research 232 (2014) 198–208 199

compare the performance of the algorithms to solve the bay-based researchers and practitioners are able to obtain faster solutions
QCSP with non-crossing constraint proposed in their previous for the unidirectional cluster-based QCSP.
studies. The paper is organized as follows. In Section 2, after the formal
Liu, Wan, and Wang (2006) proposed a two-level framework for description of the unidirectional cluster-based QCSP, an MIP model
quayside operations. In the vessel-level model, an MIP was devised is proposed and meanwhile a simplification rule and a relaxed for-
for the bay-based QCSP. Different from the previous works, the MIP mulation for tighter lower bounds are provided. In Section 3, com-
developed in this paper forced the quay cranes to move from stem prehensive computational experiments are conducted to evaluate
to stern or vice versa. To the authors’ best knowledge, this MIP the performance of the proposed mathematical model solved by
model is the first formulation in the literature for the unidirec- CPLEX. Comparisons are made between the proposed approach
tional QCSP. and the latest LTM algorithm. Finally, Section 4 concludes the
For other works in this line of research, the readers can refer to paper.
Ng and Mak (2006), Lee, Wang, and Miao (2008), Lee and Chen
(2010), etc. Note that the common disadvantages for the aforemen-
tioned studies lie on the facts that: (1) the safety distance con- 2. Mathematical formulation
straint is usually not considered in the models; (2) the crane
travel time is usually not calculated and included in the objective For a cluster-based QCSP, we are given a set of tasks
function; and (3) the information such as the crane ready times X = {1, 2, . . . , n} scattered in a ship with m bays. We denote the
and the crane initial positions is not considered in the models. set of bays as B = {1, 2, . . . , m}. Each task i 2 X represents a loading
Another branch of the study on the QCSP is the cluster-based or unloading operation of a container group. Each task has a pro-
QCSP. Kim and Park (2004) firstly proposed the cluster-based QCSP cessing time pi and a bay position li, li 2 B. From an operational
and formulated it as an MIP model. In this model, the non-crossing point of view, each individual task must be processed by a quay
constraint, the safety distance constraint, the precedence con- crane without preemption.
straint among tasks located in the same bays, the crane moving Let U denote the set of precedence constrained task pairs (i, j), i,
times, the crane ready times, and the crane initial positions were j 2 X. For the cluster-based QCSP, according to Kim and Park
all well considered. For solution, a branch-and-bound and a heuris- (2004), the rules to generate the precedence constrained task pairs
tic were developed. Moccia et al. (2006) examined the MIP formu- are: when discharging tasks and loading tasks must be performed
lated by Kim and Park (2004) and managed to ameliorate the at the same bay, the discharging tasks must precede the loading
mathematical model. Meanwhile, a more efficient branch-and- tasks; when a discharging operation is performed in a bay, the
cut algorithm was developed. Based on Moccia et al. (2006) and tasks on the deck must be performed before the tasks in the hold
Sammarra, Cordeau, Laporte, and Monaco (2007) developed a tabu of the same bay; the loading tasks in the hold must precede the
search for the same problem, aiming to solve larger instances for loading tasks on the deck of the same bay. We are also given a
practical applications. Bierwirth and Meisel (2009) spotted the set of quay cranes Q = {1, 2, . . . , q}. It is supposed that no two quay
incorrectness of the model in Sammarra et al. (2007) and brought cranes can simultaneously operate at the same bay. All quay cranes
up the idea to insert a minimum temporal distance between tasks can move between two adjacent bays in an identical travel time
so as to fix the drawbacks of the previous models. Apart from that, ^t > 0. They are not allowed to cross each other and have to keep
Bierwirth and Meisel (2009) proposed a branch-and-bound meth- a safety margin d, measured in units of bays. For each quay crane
k
od to obtain the optimal solution for the unidirectional cluster- k 2 Q, a ready time rk, a due time dk, and an initial bay position l0
based QCSP. Monaco and Sammarra (2011) examined the cluster- are given. The cluster-based QCSP aims to determine the schedul-
based QCSP with time windows, one-way and spatial constraints. ing plan for all the tasks in X such that the makespan for the
An MIP formulation was developed and a heuristic algorithm was scheduling is minimized.
proposed for solutions. Meisel (2011) also studied the cluster- Slightly different from the standard QCSP, an unidirectional
based QCSP with time windows. Built on the heuristic method pro- QCSP designs to seek the schedule plan in that all the quay cranes
posed in Bierwirth and Meisel (2009), a new problem-oriented once starting to handle tasks, move in the same direction con-
algorithm was presented for the cluster-based QCSP with time stantly either from stem to stern or vice versa throughout the rest
windows. Legato, Trunfio, and Meisel (2012) extended the research of the scheduling. As mentioned in Section 1, the first MIP for the
of Bierwirth and Meisel (2009) in two directions. First, a so-called unidirectional QCSP appeared in Liu et al. (2006). This formulation
rich QCSP was proposed and formulated by an MIP. Compared to is compact and unique in the sense that the leading actors in the
the traditional cluster-based QCSP, a rich QCSP is enriched by con- model are quay cranes rather than tasks. From Kim and Park
sidering non-uniform quay cranes, time windows, and unidirec- (2004) to Legato et al. (2012), in their MIP models, the binary deci-
tional crane movement. Next, a more efficient solving algorithm sion variable zij, i, j 2 X (equals to 1 if the task i is completed before
denoted by LTM was developed. According to the computational the task j starts; 0, otherwise) is always used. Such an approach is a
experiments, LTM is significantly faster than the heuristic proposed natural way to describe the problem and has the advantage to di-
in Bierwirth and Meisel (2009) by reducing the computational time rectly obtain the completion times of the tasks after solving. How-
down to 14% for certain instance sets. It is clear that LTM is the ever, for most of the cases, the number of tasks n is a relatively
state-of-the-art method to handle the unidirectional cluster-based large number compared to both the number of quay cranes q and
QCSP. the number of bays m. Thus, by using the binary zij, at least n2 bin-
As put in Legato et al. (2012), ‘‘considering merely unidirec- ary decision variables are inevitably needed for the MIP model and
tional schedules in a solution process simplifies the decision mak- it usually prevents the MIP models from solving to optimality with
ing’’. In the light of this observation, this paper aims to formulate a standard optimizers as the number of tasks increases. Done differ-
much simpler mathematical model for the unidirectional cluster- ently, Liu et al. (2006) shows that by only introducing the binary
based QCSP by the inspiration of the MIP formulated in Liu et al. decision variable xki, k 2 Q, i 2 X (note that in the bay-based QCSP,
(2006) and to solve the model using an off-the-shelf optimizer B = X), it is enough to formulate the unidirectional QCSP. Although
such as CPLEX. The motivation of this research is straightforward: the completion times of the tasks cannot be explicitly obtained,
since the unidirectional scheduling for the cluster-based QCSP is a they can be easily derived based on the obtained xkis. Nevertheless,
tested effective strategy, by developing a simpler mathematical as mentioned in the previous section, in Liu et al. (2006), the MIP
model and using an off-the-shelf optimization software, more model (denoted as formulation FL, hereafter) is only suitable for
200 J.H. Chen et al. / European Journal of Operational Research 232 (2014) 198–208

the unidirectional bay-based QCSP. Since all the jobs at the same li xki 6 bk ; 8k 2 Q ; i 2 X ð5Þ
bay have been accumulated as a single task, according to Kim ak þ d þ 1 6 akþ1 ; 8k þ 1 2 Q ð6Þ
and Park (2004), the set of precedence constrained task pairs
bk þ d þ 1 6 bkþ1 ; 8k þ 1 2 Q ð7Þ
should be empty for the bay-based QCSP. Apart from that, in the
formulation FL, neither the crane ready times nor the crane initial ^tðlk  ak Þ ¼ tk0 ; 8k 2 Q ð8Þ
0
positions are considered. In order to build a more general MIP 8k; k0 2 Q ; k0 < k; ði; jÞ 2 U
xk0 i 6 1  xkj ; ð9Þ
model for the unidirectional cluster-based QCSP, these basic ingre- b  ak þ  6 Mð1  ukb Þ; 8k 2 Q; b 2 B ð10Þ
dients need including. This paper extends the MIP model con-
structed in Liu et al. (2006) to cover the unidirectional cluster-
ak  b 6 Mukb ; 8k 2 Q ; b 2 B ð11Þ
based QCSP with crane ready times and initial positions. Without X X
h
pi xki þ ykb þ ^tðh  ak Þ þ t k0
any loss of generality, we increasingly number the quay cranes
i2KðhÞ b¼1
and the bays along the direction from stem to stern of a vessel
and the direction for the unidirectional scheduling is also from X X
hþdþ1
P pi xkþ1;i þ ykþ1;b þ ^tðh þ d þ 1  akþ1 Þ
stem to stern. For the reverse directional scheduling, the only mod- i2Kðhþdþ1Þ b¼1
ification exists in the input of both the numbering of the quay
cranes and bays (in reverse order). For ease of description and to
þ tkþ1  Mðukh þ ukþ1;hþdþ1 Þ; 8h þ d þ 1 2 B; k þ 1 2 Q ð12Þ
X 0 X
present how the model evolves, first of all, we assume that quay pi xki þ ykb þ ^tðbk  ak Þ þ t k0 6 cmax ; 8k 2 Q ð13Þ
cranes have zero ready times. The fully generalized formulation X
i2X
X
b2B
k
will be given in Section 2.2. pi xki þ ykb þ ^tðbk  ak Þ þ t k0 6 d ; 8k 2 Q ð14Þ
i2X b2B
2.1. Formulation without the consideration of crane ready times ak ; bk ; ykb ; tk0 ; cmax 2 Rþ ; 8k 2 Q ; b 2 B ð15Þ
xki ; ukb 2 f0; 1g; 8k 2 Q; i 2 X; b 2 B ð16Þ
The following lists the assumption, the required parameters and
the decision variables to formulate the unidirectional cluster-based The objective function (1) aims to minimize the makespan for
QCSP. Note that in this section, all the quay cranes are ready at the scheduling. Constraints (2) ensure that every task is processed
time 0. by one quay crane and constraints (3) ensure that at least one task
should assign to a quay crane due to the non-idleness assumption
Assumption: of quay cranes. Constraints (4) and (5) define the boundaries ak, bk
– No quay crane will remain idle during the full planning hori- for the movement of the quay crane k. Constraints (6) and (7) state
zon. Such an assumption is reasonable in practice. However, the properties of both ak and bk based on the safety distances
if the number of tasks is fewer than the number of available requirement. Constraints (8) define the travel time of the quay
k
cranes (i.e., n < q), then the model users can simply exclude crane k to traverse from its initial position l0 to the first position
k ^ k
(q  n) redundant cranes assigned to the vessel to guarantee ak, i.e., t0 ¼ tðl0  ak Þ. Constraints (9) play very important roles
the validity of the assumption. which distinguish the proposed model from the formulation of
Parameters: the unidirectional bay-based QCSP, i.e., FL. The rationale for such
– K(b) = {ijli 6 b, i 2 X, b 2 B}: a set of tasks whose bay posi- constraints is: since the task i must be handled before the task j
tions are less or equal to b; and quay cranes are moving from stem to stern during the process-
– M: a sufficiently large positive constant; ing, if the task j is assigned to the quay crane k, then it is impossible
– : a sufficiently small positive constant. to assign the task i to another quay crane k0 (k0 < k). In other words,
Decision variables: if the task j is assigned to the quay crane k, then the task i must
– cmax: the makespan for the scheduling; have been completed by one of the quay cranes in {k, k + 1, . . . , q}.
– ak: the leftmost position of the quay crane k where it starts Mathematically, if xkj = 1, then xk0 i ¼ 0. Note that such idea has also
k
to move rightwards; obviously, ak 6 l0 ; appeared in the so-called ‘‘Branching Criterion 1’’ in Bierwirth and
– bk: the rightmost position of the quay crane k where it stops Meisel (2009). Constraints (10) and (11) define the decision vari-
and becomes
 idle; able ukb. If b P ak, then b  ak +  > 0 and from constraints (10),
k
– tk0 ¼ ^t l0  ak : the travel time of the quay crane k to tra- ukb = 0. Conversely, if b < ak, constraints (11) force ukb = 1. Con-
k
verse from its initial position l0 to the position ak; straints (12) present the essential idea rooted in FL. The left term
P Ph k
– xki: 1, if the quay crane k is assigned to serve the task i, and 0, in the inequality i2KðhÞ pi xki þ
^
b¼1 ykb þ tðh  ak Þ þ t 0 calculates
otherwise; the time at which moment the quay crane k is about to move be-
P
– ykb: the waiting time of the quay crane k at the bay b due to yond the bay h. Here i2KðhÞ pi xki is the workload assigned to the
P
being blocked by the quay crane (k + 1); quay crane k on or before the bay h; hb¼1 ykb is the total waiting
– ukb: 0, if b  ak P 0, and 1, otherwise. time of the quay crane k due to the blocking of the quay crane
(k + 1); ^tðh  ak Þ þ t k0 is the sum of time taken by the quay crane
k
For notation simplicity, for a set S of integers, an element of set k to move from the initial position l0 to the position ak and then
S, i, and an integer constant c, let i + c 2 S be equivalent to from the position ak to the bay h. By the same token, the right hand
i 2 {i0 j(i0 2 S) ^ (i0 + c 2 S)}. The following is the mathematical side of the inequality equals to the time instance beyond which the
model. quay crane (k + 1) has been moved away from the bay (h + d + 1). It
should be highlighted that we need to guarantee that both h  ak -
min : cmax ð1Þ
X P 0 and h + d + 1  ak+1 P 0 for the constraints (12). Otherwise,
s:t: xki ¼ 1; 8i 2 X ð2Þ the terms ^tðh  ak Þ and ^tðh þ d þ 1  akþ1 Þ would lose their physi-
k2Q cal meanings. To achieve so, the term M(ukh + uk+1,h+d+1) could
X
xki P 1; 8k 2 Q ð3Þ be inserted into constraints (12). In summary, by enforcing con-
i2X straints (12), the non-crossing constraint and the safety distance
ak  li xki 6 Mð1  xki Þ; 8k 2 Q ; i 2 X ð4Þ constraint would not be violated by any two adjacent quay cranes.
Constraints (13) ensure that the service of the vessel is completed
 J.H. Chen et al. / European Journal of Operational Research 232 (2014) 198–208 201

the task 1 to the quay crane 1 and the task 2 to the quay crane 2
1 2 (with makespan 46, see Fig. 2(a) for the optimal scheduling).
However, by solving the mathematical models proposed in the
previous studies, say Bierwirth and Meisel (2009), the generated
plan (with makespan 43) is shown in Fig. 2(b). Clearly, blocking
Task 1 Task 2 is not taken into account by the models and the generated optimal
(20) (40) solution is infeasible.
In the unidirectional cluster-based QCSP, a quay crane k (k – 1,
k – q) can be blocked at the initial stage by the quay cranes (k  1)
Bay 1 2 3 4 5 6 or (k + 1). Since the blocking time of the quay crane k by the quay
crane (k + 1) has been captured by the decision variable ykb already,
Fig. 1. Example for the blocking phenomena. the remaining scenario is the case where the quay crane k is
only after all quay cranes have finished their assigned jobs. In con- blocked by the quay crane (k  1) at the initial stage. Note that
P whether the quay crane k would be blocked by the quay crane
straints (13), i2X pi xki is the total workload assigned to the quay
P (k  1) at the initial stage or not depends on the leftmost position
crane k; b2B ykb is the total waiting time when blocking occurs;
^tðbk  ak Þ þ t k is the total moving time for the quay crane k. Simi- ak of the quay crane k. Specifically, for the quay crane k (k – 1), if
0 h i
k1
larly, constraints (14) make sure that for all the quay cranes, their its leftmost position ak falls within the bay interval 1; l0 þ d ,
due times are respected. Finally, constraints (15) and (16) define the quay crane k may be blocked by the quay crane (k  1) at the
the domains for all the decision variables. initial stage. To illustrate, we take the 2 quay cranes in Fig. 3 as
k1 k
an example. Suppose l0 ¼ b þ 1; l0 ¼ b þ 6; d ¼ 1; ak ¼ b þ 2
and rk = 0. If rk1 6 3 and the quay crane (k  1) is able to move
2.2. Blocking phenomena at the initial stage of the scheduling leftward by at least one bay, then the quay crane k would not be
blocked by the quay crane (k  1) at the initial stage. However,
In this section, the crane ready times will be taken into account when rk1 P 4 or the quay crane (k  1) is blocked by the quay
and a generalized formulation catering for a much more complex crane (k  2) and stays idle at the bay (b + 1) even after time
situation, blocking at the initial stage of the scheduling, will be t = 4, then the quay crane k would be blocked by the quay crane
presented. (k  1) at the initial stage.
Previous studies in the literature, for example, Kim and Park As a result, to calculate the blocking time of the quay crane k at
(2004), Moccia et al. (2006), Sammarra et al. (2007), Bierwirth the initial stage, another decision variable denoted as yþ kb could be
and Meisel (2009), and Legato et al. (2012), assume that the quay defined to count the initial stage blocking time of the quay crane k
cranes all move from the dummy node 0 to begin their service of k1
by the quay crane (k  1) at the bay b. Note that if ak 6 l0 þ d,
a vessel and no blocking would occur when the quay cranes move k1
then ak1 < l0 . Otherwise, the spatial interference would defi-
from the node 0 to their first positions {ak}k2Q. Such a treatment
nitely occur at some point in time. Additionally, as
might pose a problem when quay cranes have non-zero ready k k1 k1 k k
times, as illustrated in Fig. 1. l 0 P l0 þ d þ 1, if ak 6 l0 þ d, then ak 6 l0  1 < l0 . Therefore,
k k1 k1
Fig. 1 shows an example with 2 tasks and 2 quay cranes. The both ak < l0 and ak1 < l0 indicate that if ak 6 l0 þ d, the quay
task 1 and the task 2 are located in the bay 1 and the bay 3, respec- cranes (k  1) and k would move from stern to stem at the initial
tively. The processing time for the task 1 is 20 and 40 for the task 2. stage of the scheduling. To avoid the violation of the non-crossing
The quay cranes 1 and 2 are initially positioned at the bays 4 and 6. and safety distance constraints, similar inequalities to the con-
Assume the ready times for the quay cranes 1 and 2 are 3 and 0, straints (12) should be added into the MIP model. In the following,
respectively. Let the safety margin be one bay and the travel speed constraints (17) serve the function aforementioned. In constraints
Plk0 þ  
for both quay cranes is one bay per time unit. Obviously, one can (17), in the time instance b¼h
k
ykb þ ^t l0  h þ rk , the quay crane k
easily approach the optimal task assignment plan, i.e., assigning

Bay Bay
Quay crane 6 Quay crane 6
2 2

5 5

Quay crane 4 Quay crane 4

1 1

3 2 (40) 3 2 (40)

2 2

1 1 (20) 1 1 (20)

0 5 10 15 20 25 30 35 40 45 50 0 5 10 15 20 25 30 35 40 45 50

(a) (b)
Fig. 2. Feasible and infeasible optimal schedules.
202 J.H. Chen et al. / European Journal of Operational Research 232 (2014) 198–208

decision flexibility to operators. The rule is a non-optimal strategy

k-1 k
and can be expressed by constraints (23).

bk 6 akþ1 þ d; 8k þ 1 2 Q ð23Þ

b b+1 b+2 b+3 b+4 b+5 b+6 b+7 Here the integer constant d is an adjustable parameter in the inter-
val [1, m]. The main purpose of constraints (23) is to restrict the
task assignment for the quay crane k such that all the tasks located
in the bays ak+1 + d + 1, . . . , m are not assigned to the quay crane k.
Particularly, if d = 1, since bk 6 ak+1  1, the resulting task assign-
Fig. 3. Example where the quay crane k might be blocked by the quay crane k  1. ment plan splits the whole vessel into q parts and assigns all the
tasks located in the kth part to the quay crane k. Alternatively, if
d = m, since bk 6 m, constraints (23) become trivial and under such
Pl0kþ1 þ a condition, the rule does not take any effect.
is about to move beyond the bay h. b¼hþdþ1 ykþ1;b þ
  Although the simplification rule cannot guarantee to achieve
^t l0kþ1  h  d  1 þ rkþ1 is the moment when the quay crane the optimality, since it has the merit to speed up the branch-
(k + 1) moves beyond the bay h + d + 1. If akþ1 6 l0 þ d which is
k and-bound or branch-and-cut procedure in the optimization solv-
equivalent to ukþ1;lk þd ¼ 0, then to avoid the spatial interference, ers, such a rule still worths adopting when the original MIP model
0 cannot be efficiently solved.
Plk0 þ P kþ1
y ^tðlk0  hÞ þ rk should be less or equal to l0 þ
þ b¼hþdþ1 ykþ1;b þ
 b¼h kb 
^t l0kþ1  h  d  1 þ rkþ1 . Thus, by introducing yþ , the blocking
kb
2.4. Relaxed formulation for lower bound
time for the quay crane k at the initial stage, can be computed by
P þ
b2B ykb . Constraints (18)–(20) present the corresponding updated As mentioned in the part of the problem description, for the
inequalities for constraints (12)–(14) when blocking times at the cluster-based QCSP, all tasks must be processed by the quay cranes
initial stage are taken into consideration. without preemption (i.e., a task can only be processed by one quay
The complete MIP formulation (called F hereafter) of the unidi- crane). To achieve a tight lower bound for the unidirectional clus-
rectional cluster-based QCSP is listed below. Additionally, the cor- ter-based QCSP, such a restriction can be lifted (i.e., a task can be
rect formulation to avoid the initial stage blocking phenomena for processed by multiple quay cranes). To fulfill such a purpose, addi-
the MIP formulations proposed in Kim and Park (2004) to Legato tional decision variables {wki}k2Q,i2X need to be defined.
et al. (2012) is summarized in Appendix A (take the formulation
presented in Bierwirth & Meisel (2009) as an example). – wki: the amount of workload of the task i processed by the quay
½Fmin : cmax crane k.

s:t: Constraints ð2Þ—ð11Þ

The relaxed formulation for the unidirectional cluster-based
kþ1
lk0 l0   QCSP can be expressed as:
X k
X kþ1
yþkb þ ^tðl0  hÞ þ r k 6 yþkþ1;b þ ^t l0  h  d  1
b¼h b¼hþdþ1
k
min : cmax
þr kþ1
þ Mukþ1;lk þd ; 8h 2 fbjb 2 B;b 6 l0 g; k þ 1 2 Q ð17Þ X
0 s:t: wki ¼ pi ; 8i 2 X ð24Þ
X X
h X k2Q
pi xki þ ykb þ yþkb þ ^tðh  ak Þ þ t k0 þ r k
wki 6 pi xki ; 8i 2 X ð25Þ
i2KðhÞ b¼1 b2B

X X
hþdþ1 X X X
h X
P pi xkþ1;i þ ykþ1;b þ yþkþ1;b wki þ ykb þ yþkb þ ^tðh  ak Þ þ t k0 þ rk
i2KðhÞ b¼1 b2B
i2Kðhþdþ1Þ b¼1 b2B
X X
hþdþ1 X
þ ^tðh þ d þ 1  akþ1 Þ þ t kþ1
0 þ rkþ1  Mðukh þ ukþ1;hþdþ1 Þ; P wkþ1;i þ ykþ1;b þ yþkþ1;b
8h þ d þ 1 2 B; k þ 1 2 Q ð18Þ i2Kðhþdþ1Þ b¼1 b2B
X X 
pi xki þ ykb þ yþkb þ ^tðbk  ak Þ þ t k0 þ r k 6 cmax ; þ ^tðh þ d þ 1  akþ1 Þ þ t 0kþ1 þ rkþ1  Mðukh þ ukþ1;hþdþ1 Þ;
i2X b2B 8h þ d þ 1 2 B; k þ 1 2 Q ð26Þ
8k 2 Q ð19Þ X X 
X X  wki þ ykb þ yþkb þ ^tðbk  ak Þ þ tk0 þ r k 6 cmax ;
k
pi xki þ ykb þ yþkb þ ^tðbk  ak Þ þ t k0 þ r k 6 d ; i2X b2B
i2X b2B 8k 2 Q ð27Þ
8k 2 Q ð20Þ X X  k
wki þ ykb þ yþkb þ ^tðbk  ak Þ þ tk0 þ r k 6 d ;
ak ;bk ;ykb ;yþkb ;tk0 ;cmax 2 Rþ ; 8k 2 Q ; b 2 B ð21Þ i2X b2B

xki ; ukb 2 f0;1g; 8k 2 Q ; i 2 X; b 2 B ð22Þ 8k 2 Q ð28Þ

wki 2 Rþ ; ukb 2 f0; 1g; 8k 2 Q; i 2 X; b 2 B ð29Þ
2.3. A rule for simplification Constraints ð4Þ—ð11Þ; ð15Þ; andð17Þ

In real world practice, container port operators usually adopt Constraints (24) ensure that each task must be completed. Con-
the ‘‘divide-and-conquer’’ strategy of partitioning a vessel into q straints (25) state that if the task i is not assigned to the quay crane
non-overlapping bay areas and assigning one crane to exactly k, then wki should be zero. Constraints (26)–(28) are the updates of
one bay area (Legato et al., 2012). The simplification rule proposed the constraints (18)–(20). Constraints (29) impose the nonnegative
here is in the same line of such a strategy however provides more and integral requirements for wki and ukb, respectively.
 J.H. Chen et al. / European Journal of Operational Research 232 (2014) 198–208 203

3. Computational experiments Table 2

Computational results for benchmark instances in the set B of Meisel and Bierwirth
(2011).
To verify the performance of the proposed MIP model for the
unidirectional cluster-based QCSP, computational experiments # n = 45 n = 50 n = 55 n = 60 n = 65 n = 70
using the two commonly accepted benchmark suites provided by 1 758(755) 774(755) 758(755) 781(781) 758(755) 756a(755)
Bierwirth and Meisel (2009) (originally proposed in Kim & Park 2 759(759) 771(769) 783(779) 756(755) 799(799) 764a(755)
3 759(756) 772(772) 779(779) 758(756) 803(803) 760(755)
(2004) and Meisel & Bierwirth (2011)) were conducted. As men-
4 789(788) 765(757) 759(757) 765(760) 758(757) 760(757)
tioned in Section 1, the LTM algorithm developed in Legato et al. 5 758(755) 762(755) 758(757) 760(755) 758(757) 757(756)
(2012) is the best method so far to solve the unidirectional clus- 6 789(767) 765(755) 789(789) 758(755) 757(756) 761(761)
ter-based QCSP. Therefore, it is reasonable to compare the LTM 7 798(798) 782(782) 768(768) 786(786) 757(757) 758a(757)
algorithm and the proposed MIP model solved by a standard opti- 8 759(757) 761(755) 767(757) 757(755) 756(756) 757(756)
9 797(797) 798(798) 801(801) 785(785) 758(756) 757(755)
mization solver. All the tests have been carried out in a Dell M4700
10 792(792) 759(756) 757(756) 805(805) 786(786) 779(777)
with CPU 2.60 gigahertz and 8.00 gigabytes RAM and solved by
CPLEX 12.3. For the CPLEX parameters, the followings are used ACT 0.020 0.023 0.017 0.022 0.025 0.030
throughout the experiments:
The value in parentheses is the lower bound.
a
New best solution; ACT: average computational time (minute).
 IloCplex::NodeLim = 100,000,000. The node limit is set to 100
million nodes.
 IloCplex::TiLim is set as default, i.e., 1E + 75. Therefore, all the stern and the other for the opposite direction. For a fair compari-
instances are solved to optimality. son, the computational time for CPLEX to solve the model F is de-
 IloCplex::MIPEmphasis = 2. The MIP emphasis is set to fined as the sum of time (measured in minutes) consumed for the
optimality. two branches of searches. In fact, the computational time could be
shorter if both search processes can be preformed concurrently and
After some trials, we note that in F, if the decision variable cmax the information of the upper bound is shared and updated in these
is set as integer rather than float decision variable, the computa- two independent searches. Thus, the unfruitful unidirectional
tional time can be significantly reduced. Noted that in all the search can be terminated as soon as possible.
benchmark instances all parameters are integers, therefore, we Table 1 reports the computational results for the benchmark in-
can set cmax as an integer decision variable. For other instances stances of Bierwirth and Meisel (2009). The columns of LB present
with fractional parameters, the same trick can be used provided the lower bounds obtained by solving the relaxed formulation pre-
that all the parameters are proportionally scaled to integers. It sented in Section 2.4. Using CPLEX, the lower bound model can be
should be highlighted that in order to obtain true optimal solutions solved to optimality for all 60 instances. The average computa-
for the unidirectional cluster-based QCSP, the MIP model F should tional time is 18.8 seconds and tighter lower bound values can
be run twice, once for the case that the direction is from stem to be delivered except for the 4 instances in the set I (i.e., I2, I3, I4,

Table 1
Comparison of solution methods on benchmark instances of Bierwirth and Meisel (2009).

# I II III
LB W CPU LB W CPU LB W CPU
LTM F LTM F LTM F LTM F LTM F LTM F
1 861 876 876 0.21 0.02 717 717 717 18.02 0.02 939 948 948 0.56 0.10
2 813a 822 822 0.20 0.02 765 774 774 0.30 0.02 729 741 741 0.51 0.07
3 822a 834 834 0.18 0.02 675 684 684 0.30 0.02 834 837 837 0.70 0.05
4 684a 690 690 0.19 0.02 678 690 690 0.38 0.03 918 924 924 0.38 0.10
5 792 792 792 0.17 0.02 693 705 705 0.31 0.05 867 882 882 0.39 0.12
6 627a 639 639 0.19 0.02 777 786 786 0.29 0.10 960 963 963 0.35 0.03
7 885 894 894 0.18 0.02 678 687 687 0.32 0.03 795 807 807 0.56 0.03
8 738 741 741 0.17 0.00 771 783 783 0.32 0.03 948 957 957 0.44 0.05
9 789 798 798 0.17 0.02 627 639 639 0.30 0.03 831 834 834 0.99 0.02
10 948 960 960 0.17 0.02 837 837 837 0.30 0.05 738 744 744 0.38 0.08

Avg. 805 805 0.18 0.02 730 730 2.08 0.04 864 864 0.53 0.07

IV V VI
1 849 870 870 6.82 0.48 939 948 948 1.02 0.40 798 810 810 8.43 4.28
2 834 843 843 1.56 0.15 888 897 897 0.98 0.27 777 786 786 19.84b 1.08
3 669 675 675 0.90 0.17 960 972 972 1.08 0.87 822 834 834 18.87b 14.13
4 843 852 852 0.81 0.13 801 816 816 5.88 0.67 795 801 801 3.66 6.55c
5 690 699 699 0.86 0.82 852 867 867 16.29 0.43 702 717 717 33.70b 8.72
6 630 642 642 1.45 1.55c 756 768 768 1.89 0.32 726 735 735 1.52 2.40c
7 735 744 744 0.91 0.53 831 843 843 1.09 0.58 831 852 852 20.69b 290.27c
8 735 750 750 0.88 0.93c 1041 1053 1053 2.65 0.43 867 876 876 2.84 1.40
9 726 738 738 0.93 0.68 822 837 837 1.83 1.20 789 813 810d 39.48b 10.02
10 711 717 717 0.91 0.28 885 897 897 2.78 1.05 885 897 897 5.62 4.55

Avg. 753 753 1.60 0.57 890 890 3.55 0.62 812 812 15.47 34.34

LB: lower bound; W: makespan; CPU: computational time in minutes.

a
Worse lower bound.
b
LTM stops at max nodes.
c
Longer computational time.
d
New best solution.
204 J.H. Chen et al. / European Journal of Operational Research 232 (2014) 198–208

Table 3
Computational results for benchmark instances in the set C of Meisel and Bierwirth (2011).

# n = 75 n = 80 n = 85 n = 90 n = 95 n = 100
a
1 1178(1178) 1173(1173) 1049(1049) 1008 (1007) 1174(1174) 1008a(1007)
2 1011(1007) 1023(1005) 1017(1007) 1015a(1006) 1090(1090) 1104(1104)
3 1182(1182) 1013(1006) 1027(1027) 1011(1006) 1010a(1007) 1107(1107)
4 1107(1107) 1202(1202) 1186(1186) 1063(1063) 1138(1138) 1202(1202)
5 1192(1192) 1036(1036) 1082(1082) 1062(1062) 1143(1143) 1008a(1007)
6 1123(1123) 1117(1117) 1009a(1006) 1193(1193) 1055(1055) 1136(1136)
7 1200(1200) 1201(1201) 1195(1195) 1108(1108) 1172(1172) 1098(1098)
8 1174(1174) 1038a(1017) 1105(1105) 1094(1094) 1014a(1006) 1151(1151)
9 1074(1074) 1192(1192) 1010(1007) 1075(1075) 1019(1019) 1011(1006)
10 1188(1188) 1206(1206) 1166(1166) 1049(1049) 1007a(1006) 1011a(1007)

ACT 0.022 0.033 0.103 0.153 0.085 0.120

The value in parentheses is the lower bound.

a
New best solution; ACT: average computational time (minute).

Table 4
Comparison of solution methods on benchmark instances of Meisel and Bierwirth (2011).

n, q W CPU n, q W CPU
LTM F LTM F LTM F LTM F
45, 4 775.8 775.8 5.730 0.020 75, 6 1142.9 1142.9 51.850 0.022
50, 4 770.9 770.9 13.780 0.023 80, 6 1120.3 1120.1 48.000 0.033
55, 4 771.9 771.9 10.360 0.017 85, 6 1084.7 1084.6 54.830 0.103
60, 4 771.1 771.1 22.470 0.022 90, 6 1068.8 1067.8 56.390 0.153
65, 4 769.0 769.0 19.600 0.025 95, 6 1082.9 1082.2 57.530 0.085
70, 4 761.9 760.9 22.590 0.030 100, 6 1085.3 1083.6 60.000 0.120
Avg. 770.1 769.9 15.755 0.023 1097.5 1096.9 54.767 0.086

Table 5
methods. Tables 2–4 list the results for the large instances in the
Real world data from Medcenter container port, Italy.
sets B and C of Meisel and Bierwirth (2011). The number of tasks
# LTM F in the set B ranges from 45 to 70, the number of quay cranes
W CPU LB W CPU q = 4, and the bay number m = 15; while for the set C,
1 15.55 0.08 14.92 15.56 0.00 n = 75, 80, . . . , 100, q = 6, and m = 20. For this benchmark suite, the
2 27.50 0.49 27.44 27.53 0.08 proposed method immensely outperforms the LTM algorithm in
3 10.77 0.14 10.78 10.78 0.03 terms of both effectiveness and efficiency. From Tables 2 and 3, 3
4 25.82 0.87 25.66 25.84 0.05
and 10 new optimal solutions have been delivered by the proposed
5 24.95 4.21 24.80 24.98 0.07
6 53.82 26.17 53.78 53.87 0.15
method for the sets B and C, respectively. In addition, as summa-
7 23.14 0.87 22.98 23.16 0.13 rized in Table 4, for the sets B and C, the average computational
8 33.27 3.47 33.08 33.31 0.05 time consumed by the LTM algorithm is 15.8 minutes and
9 37.86 60.00 37.58 37.72 1.05 54.8 minutes, respectively. However, for both the sets B and C,
10 51.14 47.34 50.96 51.10 0.12
CPLEX can solve the MIP model F to optimality within a minute.
ACT 30.38 14.36 30.20 30.38 0.17 The rationales for such an improvement can be:

1. The proposed MIP model F is very compact since it only intro-

and I6). Additionally, Table 1 also shows that CPLEX is capable of duces q  n of xki and q  m of ukb, that is, q  (n + m) binary
solving the MIP model F quite well. Considering the makespan val- decision variables. In comparison, the MIP model for the unidi-
ues in Table 1, by solving the model F, a new best solution for VI9 rectional cluster-based QCSP in Legato et al. (2012) involves at
can be found and the proposed method provides the same solution least n  (n + q) binary decision variables. For example, when
quality for all other instances. In the dimension of efficiency, ex- n = 100, q = 6, m = 20 as some instances in the set C, the number
cept for instance VI7, the formulation F could be solved to optimal- of binary decision variables introduced in F is 720 and its coun-
ity within 10 minutes. Compared with LTM, there are 5 cases (i.e., terpart such as the MIP model in Legato et al. (2012) is at least
IV6, IV8, VI4, VI6, VI7) in which CPLEX consumes more time than 10,600.
LTM (note that CPLEX generates the optimal solutions and LTM 2. The precedence constraints are not nuisances for the unidirec-
only finds incumbent solutions especially for large-scale tional cluster-based QCSP. Contrarily, it is expected that the
instances). more task pairs are in U, the easier the MIP model F can be
The benchmark instances of Bierwirth and Meisel (2009) are solved.
somehow biased according to Meisel and Bierwirth (2011). For 3. The essential part of the LTM heuristic is similar to branch-and-
example, the ratio of n/m is set to 1 for almost the instances and bound. So are the modern MIP solvers. However, in general, MIP
the instances in the sets V and VI are very unrealistic since their solvers are more advanced in effective presolving, smart
bay numbers are up to 50 (the bay number of the largest mega- branch-and-bound tree management, and deep cuts generation.
containership today, say Emma Maersk is around 24). Hence, Mei-
sel and Bierwirth (2011) provides more realistic and challenging To convince the readers that the proposed method is better than
benchmark instances to test the cluster-based QCSP solution LTM, we use the real world data from Medcenter container
 J.H. Chen et al. / European Journal of Operational Research 232 (2014) 198–208 205

Fig. 4. Scheduling plans comparison among manual method, LTM, and the proposed method.

terminal in Gioia Tauro, Italy. The computational results are sum- The slight differences between our results and the ones from Lega-
marized in Table 5. Please note that the time unit for these 10 in- to et al. (2012) may be due to the numerical rounding off during
stances is set to 2.73 minutes as reported by Legato et al. (2012). the computation. As shown in Table 5, 10 instances could be solved
206 J.H. Chen et al. / European Journal of Operational Research 232 (2014) 198–208

Table 6
Computational results for instances in the set D.

# f = 0.2, cl1 f = 0.2, cl2 f = 0.2, uni f = 0.8, cl1 f = 0.8, cl2 f = 0.8, uni
1 807(807) 611(611) 609(608) 2412(2411) 2410(2409) 2409(2409)
2 606(605) 609(609) 609(609) 2408(2407) 2410(2409) 2411(2410)
3 737(737) 608(607) 609(608) 2408(2407) 2410(2410) 2409(2409)
4 808(807) 609(609) 639(639) 2411(2411) 2409(2409) 2410(2410)
5 607(606) 609(608) 610(609) 2411(2410) 2409(2408) 2410(2409)
6 671(671) 609(609) 610(610) 2409(2407) 2410(2409) 2410(2409)
7 626(626) 611(611) 610(610) 2409(2409) 2411(2410) 2410(2409)
8 610(610) 610(609) 610(609) 2409(2407) 2410(2409) 2410(2409)
9 750(750) 610(610) 610(610) 2409(2408) 2410(2410) 2410(2409)
10 647(647) 610(610) 610(610) 2408(2407) 2409(2408) 2410(2409)

ACT (minute) 0.033 0.050 0.077 0.325 0.213 0.213

The value in parentheses is the lower bound.

For the meanings of ‘‘cl1’’, ‘‘cl2’’, and ‘‘uni’’, refer to Bierwirth and Meisel (2009).

Table 7
Computational results for instances in the set E.

# g = 0.80 g = 0.85 g = 0.90 g = 0.95 g = 1.00

1 1510(1509) 1510(1509) 1510(1509) 1510(1509) 1510(1509)
2 1510(1510) 1510(1510) 1510(1510) 1510(1510) 1510(1510)
3 1510(1510) 1510(1510) 1510(1510) 1510(1510) 1510(1510)
4 1510(1510) 1510(1510) 1510(1510) 1510(1510) 1510(1510)
5 1510(1509) 1510(1509) 1510(1509) 1510(1509) 1510(1509)
6 1510(1509) 1510(1509) 1510(1509) 1510(1509) 1510(1509)
7 1509(1509) 1509(1509) 1509(1509) 1509(1509) 1509(1509)
8 1510(1509) 1510(1509) 1510(1509) 1510(1509) 1510(1509)
9 1509(1509) 1509(1509) 1509(1509) 1509(1509) 1510(1509)
10 1510(1509) 1510(1509) 1510(1509) 1510(1509) 1510(1509)

ACT (minute) 0.118 0.108 0.097 0.090 0.105

The value in parentheses is the lower bound.

Table 8
Evaluation of the simplification rule by Set VI in Bierwirth and Meisel (2009).

# VI1 VI2 VI3 VI4 VI5 VI6 VI7 VI8 VI9 VI10
d=1 W 837 840 834 822 747 777 864 945 822 930
CPU 0.05 0.05 0.07 0.02 0.03 0.03 0.03 0.05 0.05 0.02
d=2 W 822 837 834 822 747 741 864 906 822 930
CPU 0.05 0.05 0.07 0.05 0.05 0.05 0.07 0.02 0.05 0.03
d=3 W 816 828 834 822 735 735 858 891 822 900
CPU 0.07 0.12 0.08 0.03 0.05 0.05 0.10 0.05 0.08 0.07
d=4 W 810 795 834 822 735 735 852 882 813 897
CPU 0.07 0.08 0.13 0.13 0.10 0.08 0.10 0.07 0.12 0.08
d=5 W 810 789 834 804 717 735 852 882 813 897
CPU 0.15 0.10 0.25 0.12 0.12 0.12 0.23 0.12 0.13 0.12
d=6 W 810 789 834 801 717 735 852 876 813 897
CPU 0.32 0.12 0.55 0.23 0.13 0.17 0.58 0.12 0.37 0.17
d=7 W 810 786 834 801 717 735 852 876 813 897
CPU 0.37 0.13 0.83 0.28 0.25 0.22 1.50 0.27 0.47 0.25
d=8 W 810 786 834 801 717 735 852 876 813 897
CPU 0.62 0.15 0.88 0.43 0.53 0.50 3.28 0.32 0.65 0.37
d=9 W 810 786 834 801 717 735 852 876 813 897
CPU 0.88 0.20 1.72 0.55 0.47 0.55 1.98 0.38 1.02 0.70
d = 10 W 810 786 834 801 717 735 852 876 810 897
CPU 0.87 0.45 2.77 2.13 0.95 0.68 10.83 0.38 1.15 0.55
d=1 W 810 786 834 801 717 735 852 876 810 897
CPU 4.28 1.08 14.13 6.55 8.72 2.40 290.27 1.40 10.02 4.55

to optimality within 2 minutes. Fig. 4 presents the scheduling Furthermore, besides the above two benchmark suites and the
plans for the instance 10 obtained by 3 methods, i.e., manual real data from Medcenter container terminal, we also used the in-
scheduling, LTM, and by solving F. stance generator introduced in Bierwirth and Meisel (2009) to
 J.H. Chen et al. / European Journal of Operational Research 232 (2014) 198–208 207

produce other two sets of testing instances (i.e., sets D and E). In Appendix A. To fix the issue of initial/final stage blocking
the set D, different spatial distributions of container groups are
considered for a large sized vessel (number of bays 20, bay capacity The previous MIP formulations proposed in Kim and Park
600) under a low handling rate f = 0.2 and a high handling rate (2004) to Legato et al. (2012) fail to consider the blocking phenom-
f = 0.8. The number of container groups is 100 and the number of ena of quay cranes at the initial/final stage. In their models, two
cranes is 4. In the set E, a large sized vessel is considered where dummy tasks 0 and T are used to indicate the beginning and the
the precedence density varies from g = 0.8 to 1.0. Other parameters end of the service of the vessel. However, in order to reflect the
are as in the set D. Tables 6 and 7 summarize the results and show blocking phenomena of quay cranes at the initial/final stage of
that CPLEX can solve the 110 instances within 1 minute. the scheduling, instead of dummy tasks 0 and T, two sets of dum-
n o n o
Finally, the proposed model by adopting the simplification rule k
my tasks 0k jp0k ¼ r k ; l0k ¼ l0
k
and T k jpT k ¼ 0; lT k ¼ lT could
is evaluated by the large-scale instances in the set VI of Bierwirth k2Q k2Q

and Meisel (2009). We let d vary from 1 to 10 and Table 8 sum- be introduced. Note that the tasks 0k and Tk are the first task and
marizes the results. According to Table 8, when d = 10, by adopt- final task assigned to the quay crane k. Thus, by such a transforma-
ing the rule, the same solution quality can be achieved in tion, each quay crane is ready to serve the vessel at time 0. Let X ¼
significantly less time for all the 10 instances compared with X [ f0k gk2Q [ fT k gk2Q ; X0k ¼ X [ f0k g; XT k ¼ X [ fT k g; tij ¼ ^tjli  lj j
the approach by solving F alone. Note that, for most of the cases ði; j 2 XÞ and redefine the minimal temporal distance proposed in
(see the bold values in Table 8), choosing d = 7 is enough to guar- Bierwirth and Meisel (2009):
antee that the model F can be efficiently solved with a minor loss 8
< ðli  lj þ dv w Þt; if v < w; i – j; li > lj  dv w
> ^
in optimality.
Dijv w ¼ ðlj  li þ dv w Þ^t; if v > w; i – j; li < lj  dv w
>
:
4. Conclusion 0; otherwise
Here, i; j 2 X (note that X is used instead of X), v, w 2 Q and dvw =
This paper studies the unidirectional cluster-based QCSP. Com-
(d + 1)jv  wj. Let H denote the set of all combinations of tasks
pared to other MIP models for the cluster-based QCSP, the pro-
and quay cranes that potentially lead to crane interference.
posed model is compact since it only involves a small pool of n  o
binary decision variables. To speed up the solving of the proposed H ¼ ði; j; v ; wÞ 2 X2  Q 2 jði < jÞ ^ Dvij w > 0
model, a rule aiming to restrict the pattern of task assignment is
expressed as constraints. While adopting such a rule does not al- The corrected MIP formulation (based on the one in Bierwirth &
ways lead to an optimal scheduling plan, it can advance the solu- Meisel (2009)) is:
tion for large instances. In additional, a relaxed formulation is min : cmax ðA:Appendix 1Þ
X
devised as well to obtain a tighter lower bound for the unidirec- s:t: xk0k j ¼ 1; ðk 2 Q Þ ðA:Appendix 2Þ
tional cluster-based QCSP. j2XT k
To test the performance of the proposed MIP model (solved by X
xkjT k ¼ 1; ðk 2 Q Þ ðA:Appendix 3Þ
CPLEX), comprehensive numerical experiments have been con-
j2X0k
ducted to assess the quality of the QCSP solution methods. Based XX
on the experiment results, the proposed method outperforms the xkij ¼ 1; ði 2 XÞ ðA:Appendix 4Þ
k2Q j2XT k
LTM algorithm developed in Legato et al. (2012). X X
The advantages of our proposed MIP model are: (1) The pro- xkji  xkij ¼ 0; ði 2 X; k 2 Q Þ ðA:Appendix 5Þ
posed model is much easier to formulate. Fewer binary decision j2X0k j2X Tk
 
variables are introduced for the proposed model. Apart from this,
ci þ t ij þ pj  cj 6 M 1  xkij ; ði; j; 2 X; k 2 Q Þ
the proposed model also get other great features. For example, in
order to use other models for the cluster-based QCSP, usually ðA:Appendix 6Þ
users need to calculate the minimal temporal distance Dvij w and ci þ pj  cj 6 0; ðði; jÞ 2 UÞ ðA:Appendix 7Þ
the set H (see Appendix A). However, in the proposed MIP model,
ci þ pj  cj 6 Mð1  zij Þ; ði; j 2 XÞ ðA:Appendix 8Þ
Dvij w and H do not need calculation beforehand. Besides, since Dvij w
and H are functions of d and ^t, if d and ^t vary, the formulation cj  pj  ci 6 Mzij ; ði; j 2 XÞ ðA:Appendix 9Þ
developed based on the previous values of d and ^t is no longer va- zij þ zji ¼ 1; ðði; jÞ 2 WÞ ðA:Appendix 10Þ
lid for the new d and ^t. Also, this would become troublesome as X
m xvui þ xwuj 6 1 þ zij þ zji ;
users might try to analyze the cluster-based QCSP with uncer- u2X0v
u2X0w
tainty driven by ^t; (2) Even for large and challenging instances,
the proposed model can be efficiently solved by standard optimi- ðði; j; v ; wÞ 2 HÞ ðA:Appendix 11Þ
0 1
zation solvers, e.g., CPLEX. (3) The proposed model can be gener- X X
alized to a rich unidirectional cluster-based QCSP model with ci þ Dijv w þ pj  cj 6 M @3  zij  xvui  wA
xuj ;
small modifications. (4) The proposed model is the first MIP mod- u2X 0v
u2X0w

el for the cluster-based QCSP immune to the error generated by ðði; j; v ; wÞ 2 HÞ ðA:Appendix 12Þ
ignoring the phenomena of blocking at the initial stage of the 0 1
scheduling. X X
cj þ Dijv w þ pi  ci 6 M @3  zji  xvui  wA
xuj ;
u2X0v u2X0w
Acknowledgements
ðði; j; v ; wÞ 2 HÞ ðA:Appendix 13Þ
The authors like to thank Dr. Frank Meisel (School of Economics ci P 0; ði 2 XÞ ðA:Appendix 14Þ
and Business, Martin-Luther-University Halle-Wittenberg, Ger- ci 6 cmax ; ði 2 fT k gk2Q Þ ðA:Appendix 15Þ
many) and Dr. Roberto Trunfio (Department of Electronics, Com-
xkij 2 f0; 1g; ði; j 2 X; k 2 Q Þ ðA:Appendix 16Þ
puter and System Sciences, University of Calabria, Italy) for
providing the benchmark suites and patient instruction. zij 2 f0; 1g; ði; j 2 XÞ ðA:Appendix 17Þ
208 J.H. Chen et al. / European Journal of Operational Research 232 (2014) 198–208

References Liu, J., Wan, Y., & Wang, L. (2006). Quay crane scheduling at container terminals to
minimize the maximum relative tardiness of vessel departures. Naval Research
Logistics, 53(1), 60–74.
Bierwirth, C., & Meisel, F. (2009). A fast heuristic for quay crane scheduling with
Meisel, F. (2011). The quay crane scheduling problem with time windows. Naval
interference constraints. Journal of Scheduling, 12(4), 345–360.
Research Logistics, 58(7), 619–636.
Daganzo, C. F. (1989). The crane scheduling problem. Transportation Research Part B
Meisel, F., & Bierwirth, C. (2011). A unified approach for the evaluation of quay
– Methodological, 23(3), 159–175.
crane scheduling models and algorithms. Computers and Operations Research,
Kim, K. H., & Park, Y. M. (2004). A crane scheduling method for port container
38(3), 683–693.
terminals. European Journal of Operational Research, 156(3), 752–768.
Moccia, L., Cordeau, J. F., Gaudioso, M., & Laporte, G. (2006). A branch-and-cut
Lee, D. H., & Chen, J. H. (2010). An improved approach for quay crane scheduling
algorithm for the quay crane scheduling problem in a container terminal. Naval
with non-crossing constraints. Engineering Optimization, 42(1), 1–15.
Research Logistics, 53(1), 45–59.
Lee, D. H., Wang, H. Q., & Miao, L. X. (2008). Quay crane scheduling with non-
Monaco, M., & Sammarra, M. (2011). Quay crane scheduling with time windows,
interference constraints in port container terminals. Transportation Research
one-way and spatial constraints. International Journal of Shipping and Transport
Part E – Logistics and Transportation Review, 44(1), 124–135.
Logistics, 3(4), 454–474.
Legato, P., Trunfio, R., & Meisel, F. (2012). Modeling and solving rich quay
Ng, W. C., & Mak, K. L. (2006). Quay crane scheduling in container terminals.
crane scheduling problems. Computers and Operations Research, 39(9),
Engineering Optimization, 38(6), 723–737.
2063–2078.
Peterkofsky, R. I., & Daganzo, C. F. (1990). A branch and bound solution method for
Lim, A., Rodrigues, B., Xiao, F., & Zhu, Y. (2004). Crane scheduling with spatial
the crane scheduling problem. Transportation Research Part B – Methodological,
constraints. Naval Research Logistics, 51(3), 386–406.
24(3), 159–172.
Lim, A., Rodrigues, B., & Xu, Z. (2004). Approximation schemes for the crane
Sammarra, M., Cordeau, J., Laporte, G., & Monaco, M. (2007). A tabu search heuristic
scheduling problem. In T. Hagerup & J. Katajainen (Eds.), 9th Scandinavian
for the quay crane scheduling problem. Journal of Scheduling, 10(4), 327–336.
workshop on algorithm theory (pp. 323–335). Springer.
Zhu, Y., & Lim, A. (2006). Crane scheduling with non-crossing constraint. Journal of
Lim, A., Rodrigues, B., & Xu, Z. (2007). A m-parallel crane scheduling problem with a
the Operational Research Society, 57(12), 1464–1471.
non-crossing constraint. Naval Research Logistics, 54(2), 115–127.