Online integrated allocation of berths and quay cranes in container terminals with 1-lookahead
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