×

zbMATH — the first resource for mathematics

Interference aware scheduling of triple-crossover-cranes. (English) Zbl 1446.90073
Summary: In order to increase the productivity of sea port container storage yards, a triple-crossover-stacking-crane setting can be deployed. Although this setting yields promising results, there is increasing risk of cranes interfering. Coping with interference is a key factor for exploiting the potential of triple-crossover-stacking-cranes to increase overall productivity. In this paper, we tackle the problem of finding an assignment of transport jobs to cranes, a processing sequence for each crane as well as a conflict-free routing under the objective of minimizing the makespan. We develop several variants of branch-and-bound algorithms differing in the order of assignment and sequencing decisions and in the techniques applied for routing decisions. We compare the performance of our algorithms with regard to solution quality and run times and use standard solver CPLEX as benchmark.
MSC:
90B35 Deterministic scheduling theory in operations research
90C27 Combinatorial optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90B06 Transportation, logistics and supply chain management
Software:
CPLEX
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Boysen, N.; Briskorn, D.; Meisel, F., A generalized classification scheme for crane scheduling with interference, European Journal of Operational Research, 258, 1, 343-357 (2017) · Zbl 1380.90108
[2] Briskorn, D.; Angeloudis, P., Scheduling co-operating stacking cranes with predetermined container sequences, Discrete Applied Mathematics, 201, 70-85 (2016) · Zbl 1336.90009
[3] Briskorn, D.; Zey, L., Resolving interferences of triple-crossover-cranes by determining paths in networks, Naval Research Logistics, 65, 6-7, 477-498 (2018) · Zbl 1407.90141
[4] Briskorn, D.; Jaehn, F.; Wiehl, A., A generator for test instances of scheduling problems concerning cranes in transshipment terminals, OR Spectrum, 41, 1, 45-69 (2019)
[5] Briskorn, D., Jaehn, F., & Wiehl, A. (2019b). Test data generator-version, 1.08. Retrieved May 9, 2018 from http://www.instances.de/dfg.
[6] Carlo, H.; Vis, I.; Roodbergen, K., Seaside operations in container terminals: Literature overview, trends, and research directions, Flexible Services and Manufacturing Journal, 27, 2-3, 224-262 (2015)
[7] Carlo, HJ; Vis, IF; Roodbergen, KJ, Transport operations in container terminals: Literature overview, trends, research directions and classification scheme, European Journal of Operational Research, 236, 1, 1-13 (2014) · Zbl 1338.90003
[8] Carlo, HJ; Vis, IF; Roodbergen, KJ, Storage yard operations in container terminals: Literature overview, trends, and research directions, European Journal of Operational Research, 235, 2, 412-430 (2014) · Zbl 1305.90007
[9] Choe, R.; Park, T.; Ok, SM; Ryu, KR; Orgun, MA; Thornton, J., Real-time scheduling for non-crossing stacking cranes in an automated container terminal, AI 2007: Advances in artificial intelligence: 20th Australian joint conference on artificial intelligence, gold coast, Australia, December 2-6, 2007. Proceedings, 625-631 (2007), Berlin: Springer, Berlin
[10] Choe, R., Yuan, H., Yang, Y., & Ryu, K.R. (2012). Real-time scheduling of twin stacking cranes in an automated container terminal using a genetic algorithm. In Proceedings of the 27th annual ACM symposium on applied computing, SAC ’12 (pp. 238-243). New York, NY, USA: ACM.
[11] Dorndorf, U.; Schneider, F., Scheduling automated triple cross-over stacking cranes in a container yard, OR Spectrum, 32, 617-632 (2010) · Zbl 1200.90072
[12] Gharehgozli, AH; Laporte, G.; Yu, Y.; de Koster, R., Scheduling twin yard cranes in a container block, Transportation Science, 49, 3, 686-705 (2015)
[13] Gharehgozli, AH; Yu, Y.; de Koster, R.; Udding, JT, An exact method for scheduling a yard crane, European Journal of Operational Research, 235, 2, 431-447 (2014) · Zbl 1305.90182
[14] Gilmore, PC; Gomory, R., Sequencing a one state-variable machine: A solvable case of the traveling salesman problem, Operations Research, 12, 5, 655-679 (1964) · Zbl 0126.36006
[15] Heitmann, H. (2015). Selected scheduling applications. Schriftenreihe QM: Quantitative Methoden in Forschung und Praxis 38. Hamburg: Kovač.
[16] Kemme, N., Design and operation of automated container storage systems (2013), Heidelberg: Physica-Verlag, Heidelberg
[17] Klaws, J.; Stahlbock, R.; Voß, S.; Böse, JW; Hu, H.; Jahn, C.; Shi, X.; Stahlbock, R.; Voß, S., Container terminal yard operations—Simulation of a side-loaded container block served by triple rail mounted gantry cranes, Computational logistics: Second international conference, ICCL 2011, Hamburg, Germany, September 19-22, 2011. Proceedings, 243-255 (2011), Berlin: Springer, Berlin
[18] Li, W.; Goh, M.; Wu, Y.; Petering, M.; de Souza, R.; Wu, Y., A continuous time model for multiple yard crane scheduling with last minute job arrivals, International Journal of Production Economics, 136, 2, 332-343 (2012)
[19] Li, W.; Wu, Y.; Petering, MEH; Goh, M.; de Souza, R., Discrete time model and algorithms for container yard crane scheduling, European Journal of Operational Research, 198, 165-172 (2009) · Zbl 1163.90496
[20] Ng, WC; Mak, KL, An effective heuristic for scheduling a yard crane to handle jobs with different ready times, Engineering Optimization, 37, 867-877 (2005)
[21] Nossack, J.; Briskorn, D.; Pesch, E., Container dispatching and conflict-free yard crane routing in an automated container terminal, Transportation Science, 52, 5, 1059-1076 (2018)
[22] Stahlbock, R.; Voß, S., Operations research at container terminals: A literature update, OR Spectrum, 30, 1-52 (2008) · Zbl 1133.90313
[23] Steenken, D.; Voß, S.; Stahlbock, R., Container terminal operations and operations research—A classification and literature review, OR Spectrum, 26, 3-49 (2004) · Zbl 1160.90322
[24] Vis, IF, A comparative analysis of storage and retrieval equipment at a container terminal, International Journal of Production Economics, 103, 2, 680-693 (2006)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.