Online integrated allocation of berths and quay cranes in container terminals with 1-lookahead

Springer Science and Business Media LLC - Tập 36 - Trang 617-636 - 2017
Jiayin Pan1,2, Yinfeng Xu1,2, Guiqing Zhang3
1School of Management, Xi’an Jiaotong University, Xi’an, China
2The State Key Lab for Manufacturing Systems Engineering, Xi’an, China
3School of Finance and Economics, Xi’an Jiaotong University, Xi’an, China

Tóm tắt

This paper studies an online over-list model of the integrated allocation of berths and quay cranes (QCs) in container terminals with 1-lookahead ability. The objective is to minimize the maximum completion time of container vessels, i.e., the makespan. We focus on two different types of vessels, three berths and a small number of QCs in the hybrid berth layout, with 1-lookahead ability. We propose a $${{(1 + \sqrt{2} )/2}}$$ -competitive algorithm for the case with four cranes, a 5/4-competitive algorithm for the case with five cranes and a 4/3-competitive algorithm for the case with six cranes, respectively. All of the algorithms are proved to be optimal.

Tài liệu tham khảo

Bierwirth C, Meisel F (2010) A survey of berth allocation and quay crane scheduling problems in container terminals. Eur J Oper Res 202(3):615–627 Blazewicz J, Cheng TCE, Machowiak M, Oguz C (2011) Berth and quay crane allocation: a moldable task scheduling model. J Oper Res Soc 62:1189–1197 Borodin A, El-Yaniv R (1998) Online computation and competitive analysis. Cambridge University Press, New York Carlo H, Vis I, Roodbergen K (2013) Seaside operations in container terminals: literature overview, trends, and research directions. Flex Serv Manuf J 27:1–39 Chen JH, Lee DH, Cao JX (2012) A combinatorial benders cuts algorithm for the quayside operation problem at container terminals. Transp Res Part E Logist Transp Rev 48(1):266–275 (2012) (select Papers from the 19th International Symposium on Transportation and Traffic Theory) Giallombardo G, Moccia L, Salani M, Vacca I (2010) Modeling and solving the tactical berth allocation problem. Transp Res Part B Methodol 44(2):232–245 Imai A, Sun X, Nishimura E, Papadimitriou S (2005) Berth allocation in a container port: using a continuous location space approach. Transp Res Part B Methodol 39(3):199–221 Liang C, Guo J, Yang Y (2011) Multi-objective hybrid genetic algorithm for quay crane dynamic assignment in berth allocation planning. J Intell Manuf 22(3):471–479 Lokuge P, Alahakoon D (2007) Improving the adaptability in automated vessel scheduling in container ports using intelligent software agents. Eur J Oper Res 177(3):1985–2015 Mandelbaum M, Shabtay D (2011) Scheduling unit length jobs on parallel machines with lookahead information. J Sched 14(4):335–350 Park YM, Kim KH (2003) A scheduling method for berth and quay cranes. OR Spectr 25(1):1–23 Theofannis S, Golias M, Boile M (2007) Berth and quay crane scheduling: a formulation reflecting service deadlines and productivity agreements. In: Proceedings of the international conference on transport science and technology (TRANSTEC 2007), Prague, pp 124–140 Zhang L, Khammuang K, Wirth A (2008) On-line scheduling with non-crossing constraints. Oper Res Lett 36(5):579–583 Zheng F, Xu Y, Zhang E (2008) How much can lookahead help in online single machine scheduling. Inf Pro Lett 106:70–74 Zheng F, Qiao L, Liu M (2015) An Online Model of Berth and Quay Crane Integrated Allocation in Container Terminals. In: Lu Z, Kim D, Wu W, Li W, Du DZ (eds) Combinatorial Optimization and Applications. Lecture Notes in Computer Science, vol 9486. Springer, Cham, pp 721–730 Zhen L, Chew EP, Lee LH (2011) An integrated model for berth template and yard template planning in transshipment hubs. Transp Sci 45(4):483–504 Zheng F, Cheng Y, Liu M, Xu Y (2013) Online interval scheduling on a single machine with finite lookahead. Comput Oper Res 40(1):180–191 Zheng F, Qiao L, Liu M, Chu C. Online integrated allocation for small numbers of berths and quay cranes in container terminals, private communication