This paper studies the reclaimer scheduling problem that arises in the management of a stockyard at a coal terminal. In this problem, we are given a single reclaimer initially located at the left end of a stock pad of length L. The reclaimer can either travel across or reclaim stockpiles on the stock pad, with a speed ratio of s ≥ 1. The scheduler has to decide the placement positions of the stockpiles on the stock pad and sequence the reclaiming of the stockpiles so as to minimize the total time serving the arrived vessels. We show that there exists an approximation algorithm with a worst case ratio no larger than 1 + 1/4s, provided that the reclaimer has to return to the endpoints of the stock pad.
WANG Yizhan, ZHANG An, CHEN Yong, CHEN Guangting
. An approximation algorithm for reclaimer scheduling[J]. Operations Research Transactions, 2020
, 24(1)
: 147
-154
.
DOI: 10.15960/j.cnki.issn.1007-6093.2020.01.012
[1] Kalinowski T, Kapoor R, Savelsbergh Martin W P. Scheduling reclaimers serving a stock pad at a coal terminal[J]. Journal of Scheduling, 2017, 20(1):85-101.
[2] Angelelli E, Kalinowski T, Kapoor R, et al. A reclaimer scheduling problem arising in coal stockyard management[J]. Journal of Scheduling, 2016, 19(5):563-582.
[3] Bierwirth C, Meisel F. A survey of berth allocation and quay crane scheduling problems in container terminals[J]. European Journal of Operational Research, 2010, 202(3):615-627.
[4] Bierwirth C, Meisel F. A follow-up survey of berth allocation and quay crane scheduling problems in container terminals[J]. European Journal of Operational Research, 2015, 244(3):675-689.
[5] Boysen B, Briskorn D, Meisel F. A generalized classification scheme for crane scheduling with interference[J]. European Journal of Operational Research, 2017, 258:343-357.
[6] Zhen L, Yu S C, Wang S A, et al. Scheduling quay cranes and yard trucks for unloading operations in container ports[J]. Annals of Operations Research, 2019, 273:455-478.
[7] Ma H L, Chung S H, Chan H K, et al. An integrated model for berth and yard planning in container terminals with multi-continuous berth layout[J]. Annals of Operations Research, 2019, 273:409-431.
[8] Graham R L. Bounds on multiprocessing timing anomalies[J]. SIAM Journal on Applied Mathematics, 1969, 17(2):416-429.
