TY  - JOUR
PY  - 2017//
TI  - Approximate the scheduling of quay cranes with non-crossing constraints
JO  - European journal of operational research
A1  - Zhang, An
A1  - Zhang, Wenshuai
A1  - Chen, Yong
A1  - Chen, Guangting
A1  - Chen, Xufeng
SP  - 820
EP  - 828
VL  - 258
IS  - 3
N2  - In port container terminals, the scheduling of quay cranes (QCs) for a container vessel is one 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 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 ratio 2−2m+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 cranes with different processing speeds. For an arbitrary speed ratio s ≥ 1, an approximation algorithm with worst case ratio (1+s)21+s+s2 is provided.<p />  <p>Language: en</p>
LA  - en
SN  - 0377-2217
UR  - http://dx.doi.org/10.1016/j.ejor.2016.10.021
ID  - ref1
ER  -