Approximate the scheduling of quay cranes with non-crossing constraints

作者：Zhang, An^*; Zhang, Wenshuai; Chen, Yong; Chen, Guangting; Chen, Xufeng

来源：European Journal of Operational Research, 2017, 258(3): 820-828.

DOI：10.1016/j.ejor.2016.10.021

• Scheduling
• Non-crossing
• Quay cranes
• Approximation algorithms
• Worst case analysis

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 - 2/m+1 < 2 for any in 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)(2)/1+s+s(2) is provided.

• 出版日期2017-5-1
• 单位杭州电子科技大学; 台州学院