Dynamic programming algorithms for the general quay crane double-cycling problem with internal-reshuffles. (English) Zbl 1441.90175
Summary: High utilization of quay cranes is a major objective pursued by seaport terminal managers. Double-cycling technique has been shown to be effective in practice. Complicated with reshuffle operations, the productivity of quay cranes could be further improved, but the problem complexity increases as a side-effect. This paper studies a double-cycling quay crane scheduling problem in which reshuffle containers can be handled internally on the vessel. For this problem, no exact algorithm exists in the literature. We present a dynamic programming approach to optimally solve the problem. Our algorithm runs in polynomial time when the number of container stacks is fixed. We also extend our proposed optimal algorithm to the general case where hatch covers are involved.
MSC:
| 90C39 | Dynamic programming |
| 90C27 | Combinatorial optimization |
| 90B35 | Deterministic scheduling theory in operations research |
| 90C90 | Applications of mathematical programming |
References:
| [1] | Bauer M (2016) Entwurf und experimentelle Analyse von Lösungsverfahren für das Container Sequencing Problem, Ph.D. Dissertation, Universität Passau, pp 88-132 |
| [2] | Bierwirth, C.; Meisel, F., A fast heuristic for quay crane scheduling with interference constraints, J Sched, 12, 4, 345-360 (2009) · Zbl 1185.90140 · doi:10.1007/s10951-009-0105-0 |
| [3] | Bierwirth, C.; Meisel, F., A survey of berth allocation and quay crane scheduling problems in container terminals, Eur J Oper Res, 202, 3, 615-627 (2010) · Zbl 1176.90373 · doi:10.1016/j.ejor.2009.05.031 |
| [4] | Bierwirth, C.; Meisel, F., A follow-up survey of berth allocation and quay crane scheduling problems in container terminals, Eur J Oper Res, 244, 3, 675-689 (2015) · Zbl 1346.90326 · doi:10.1016/j.ejor.2014.12.030 |
| [5] | Carlo, HJ; Vis, IFA; Roodbergen, KJ, Seaside operations in container terminals: literature overview, trends, and research directions, Flex Serv Manuf J, 272, 2, 224-262 (2015) · doi:10.1007/s10696-013-9178-3 |
| [6] | Caserta, M.; Schwarze, S.; Voß, S.; Bose, JW, Container rehandling at maritime container terminals, Handbook of terminal planning, 247-269 (2011), Berlin: Springer, Berlin |
| [7] | Choo, S.; Klabjan, D.; Simchi-Levi, D., Multiship crane sequencing with yard congestion constraints, Transp Sci, 44, 1, 98-115 (2010) · doi:10.1287/trsc.1090.0296 |
| [8] | Daganzo, CF, Crane productivity and ship delay in ports, Transp Res Rec, 1251, 1-9 (1989) |
| [9] | Goodchild, AV; Daganzo, CF, Double-cycling strategies for container ships and their effect on ship loading and unloading operations, Transp Sci, 40, 4, 473-483 (2006) · doi:10.1287/trsc.1060.0148 |
| [10] | Johnson, SM, Optimal two- and three-stage production schedules with setup times included, Naval Res Logist Q, 1, 61-68 (1954) · Zbl 1349.90359 · doi:10.1002/nav.3800010110 |
| [11] | Kim, KH, Evaluation of the number of rehandles in container yards, Comput Ind Eng, 32, 4, 701-711 (1997) · doi:10.1016/S0360-8352(97)00010-7 |
| [12] | Kim, KH; Hong, G-P, A heuristic rule for relocating blocks, Comput Oper Res, 33, 4, 940-954 (2006) · Zbl 1079.90079 · doi:10.1016/j.cor.2004.08.005 |
| [13] | Kim, KH; Park, Y-M, A crane scheduling method for port container terminals, Eur J Oper Res, 156, 3, 752-768 (2004) · Zbl 1062.90027 · doi:10.1016/S0377-2217(03)00133-4 |
| [14] | Lee, CY; Liu, M.; Chu, CB, Optimal algorithm for general quay crane double-cycling problem, Transp Sci, 49, 4, 957-967 (2015) · doi:10.1287/trsc.2014.0563 |
| [15] | Legato, P.; Trunfio, R.; Meisel, F., Modeling and solving rich quay crane scheduling problems, Comput Oper Res, 39, 9, 2063-2078 (2012) · Zbl 1251.90163 · doi:10.1016/j.cor.2011.09.025 |
| [16] | Lim, A.; Rodrigues, B.; Xu, Z., A m-parallel crane scheduling problem with a non-crossing constraint, Naval Res Logist, 54, 2, 115-127 (2007) · Zbl 1126.90025 · doi:10.1002/nav.20189 |
| [17] | Liu, M.; Chu, F.; Zhang, ZZ; Chu, CB, A polynomial-time heuristic for the quay crane double-cycling problem with internal-reshuffling operations, Transp Res Part E, 81, 52-74 (2015) · doi:10.1016/j.tre.2015.06.009 |
| [18] | Liu, M.; Zheng, FF; Li, JF, Scheduling small number of quay cranes with non-interference constraint, Optim Lett, 9, 2, 403-412 (2015) · Zbl 1310.90053 · doi:10.1007/s11590-014-0756-4 |
| [19] | Meisel, F., The quay crane scheduling problem with time windows, Naval Res Logist, 58, 7, 619-639 (2011) · Zbl 1241.90052 · doi:10.1002/nav.20471 |
| [20] | Meisel, F.; Wichmann, M., Container sequencing for quay cranes with internal reshuffles, OR Spectr, 32, 3, 569-591 (2010) · Zbl 1201.90031 · doi:10.1007/s00291-009-0191-6 |
| [21] | Meisel, F.; Bierwirth, C., A unified approach for the evaluation of quay crane scheduling models and algorithms, Comput Oper Res, 38, 3, 683-693 (2011) · doi:10.1016/j.cor.2010.08.001 |
| [22] | Meisel, F.; Bierwirth, C., A framework for integrated berth allocation and crane operations planning in seaport container terminals, Transp Sci, 47, 2, 131-147 (2013) · doi:10.1287/trsc.1120.0419 |
| [23] | Stahlbock, R.; Voß, S., Operations research at container terminals: a literature update, OR Spectr, 30, 1, 1-52 (2008) · Zbl 1133.90313 · doi:10.1007/s00291-007-0100-9 |
| [24] | Zhang, HP; Kim, KH, Maximizing the number of dual-cycle operations of quay cranes in container terminals, Comput Ind Eng, 56, 3, 979-992 (2009) · doi:10.1016/j.cie.2008.09.008 |
| [25] | Zhang, A.; Zhang, WS; Chen, Y.; Chen, GT; Chen, XF, Approximate the scheduling of quay cranes with non-crossing constraints, Eur J Oper Res, 258, 3, 820-828 (2017) · Zbl 1394.90316 · doi:10.1016/j.ejor.2016.10.021 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
