Some complexity results and an efficient algorithm for quay crane scheduling problem. (English) Zbl 1355.90026
Summary: This paper investigates the quay crane scheduling problem (QCSP) at container ports, subject to arbitrary precedence constraint among vessel container tasks. Differing from classic machine scheduling problems, noncrossing constraint for quay cranes must be satisfied. This is because quay cranes work in parallel and they travel on a same rail (along the berth), to perform container unloading and loading tasks for vessels. Precedence relation in an arbitrary form is rarely investigated in the literature, however, it may be originated from reefers or dangerous cargo which requires high priority of processing, and yard stacking plan. We present the computational complexity for several problem variations. In particular, we show the QCSP, even without precedence constraint, is strongly NP-hard. This complexity result improves the state-of-the-art, in which the same problem is shown to be NP-hard in the ordinary sense. Besides, we also prove that for two parallel quay cranes, if the processing times of container tasks are ones and twos, then this scheduling problem is NP-hard. This result implies that the QCSP with arbitrary precedence constraint is very difficult to solve. A genetic algorithm is proposed to obtain near-optimal solutions. Computational experiments demonstrate the efficiency.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [1] | 1. I. Aho and E. Makinen, On a parallel machine scheduling problem with precedence constraints, J. Sched.9(5) (2006) 493-495. genRefLink(16, ’S1793830916500580BIB001’, ’10.1007 · Zbl 1154.90400 |
| [2] | 2. C. Bierwirth and F. Meisel, A fast heuristic for quay crane scheduling with interference constraints, J. Sched.12(4) (2009) 345-360. genRefLink(16, ’S1793830916500580BIB002’, ’10.1007 · Zbl 1185.90140 |
| [3] | 3. C. Bierwirth and F. Meisel, A survey of berth allocation and quay crane scheduling problems in container terminals, European J. Oper. Res.202(3) (2010) 615-627. genRefLink(16, ’S1793830916500580BIB003’, ’10.1016 · Zbl 1176.90373 |
| [4] | 4. H. J. Carlo, I. F. A. Vis and K. J. Roodbergen, Seaside operations in container terminals: Literature overview, trends, and research directions, Flex. Serv. Manuf. J. (2013), doi: [doi:10.1007/s10696-013-9178-3] . · Zbl 1338.90003 |
| [5] | 5. J. H. Chen, D. H. Lee and M. Goh, An effective mathematical formulation for the unidirectional cluster-based quay crane scheduling problem, European J. Oper. Res.232(1) (2013) 198-208. genRefLink(16, ’S1793830916500580BIB005’, ’10.1016 |
| [6] | 6. S. Choo, D. Klabjan and D. Simchi-Levi, Multiship crane sequencing with yard congestion constraints, Transp. Sci.44(1) (2010) 98-115. genRefLink(16, ’S1793830916500580BIB006’, ’10.1287 |
| [7] | 7. T. G. Crainic and K. H. Kim, Intermodal transportation, Handbooks in Operations Research and Management Science, Vol. 14 (Elsevier, 2007), pp. 467-537. |
| [8] | 8. C. F. Daganzo, The crane scheduling problem, Transp. Res. Part B23(3) (1989) 159-175. genRefLink(16, ’S1793830916500580BIB008’, ’10.1016 |
| [9] | 9. A. V. Goodchild and C. F. Daganzo, Double-cycling strategies for container ships and their effect on ship loading and unloading operations, Trans. Sci.40(4) (2006) 473-483. genRefLink(16, ’S1793830916500580BIB009’, ’10.1287 |
| [10] | 10. N. G. Hall and M. E. Posner, Generating experimental data for computational testing with machine scheduling application, Oper. Res.49(7) (2001) 854-865. genRefLink(16, ’S1793830916500580BIB010’, ’10.1287 · Zbl 1163.90490 |
| [11] | 11. J. H. Holland, Adaption in natural and artificial systems, Ph.D. thesis, University of Michigan Press, Ann Arbor (1975). · Zbl 0317.68006 |
| [12] | 12. A. Imai, E. Nishimura and S. Papadimitriou, The dynamic berth allocation problem for a container port, Trans. Res. Part B35(4) (2001) 401-417. genRefLink(16, ’S1793830916500580BIB012’, ’10.1016 |
| [13] | 13. A. Imai, K. Sasaki, E. Nishimura and S. Papadimitriou, Multi-objective simultaneous stowage and load planning for a container ship with container rehandle in yard stacks, European J. Oper. Res.171(2) (2006) 373-389. genRefLink(16, ’S1793830916500580BIB013’, ’10.1016 · Zbl 1090.90009 |
| [14] | 14. N. Kaveshgar, N. Huynh and S. K. Rahimian, An efficient genetic algorithm for solving the quay crane scheduling problem, Expert Syst. Appl.39(18) (2012) 13108-13117. genRefLink(16, ’S1793830916500580BIB014’, ’10.1016 |
| [15] | 15. K. H. Kim and Y.-M. Park, A crane scheduling method for port container terminals, European J. Oper. Res.156(3) (2004) 752-768. genRefLink(16, ’S1793830916500580BIB015’, ’10.1016 · Zbl 1062.90027 |
| [16] | 16. D. H. Lee, H. Q. Wang and L. X. Miao, Quay crane scheduling with noninterference constraints in port container terminals, Trans. Res. Part E-Logist. Trans. Rev.44(1) (2008) 124-135. genRefLink(16, ’S1793830916500580BIB016’, ’10.1016 |
| [17] | 17. D. H. Lee and J. H. Chen, An improved approach for quay crane scheduling with non-crossing constraints, Eng. Optim.42(1) (2010) 1-15. genRefLink(16, ’S1793830916500580BIB017’, ’10.1080 |
| [18] | 18. P. Legato, R. Trunfio and F. Meisel, Modeling and solving rich quay crane scheduling problems, Comput. Oper. Res.39(9) (2012) 2063-2078. genRefLink(16, ’S1793830916500580BIB018’, ’10.1016 · Zbl 1251.90163 |
| [19] | 19. J. Y. Liu, Y. W. Wan and L. Wang, Quay crane scheduling at container terminals to minimize the maximum relative tardiness of vessel departures, Naval Res. Logist.53(1) (2006) 60-74. genRefLink(16, ’S1793830916500580BIB019’, ’10.1002 · Zbl 1112.90031 |
| [20] | 20. Z. X. Liu, Single machine scheduling to minimize maximum lateness subject to release dates and precedence constraints, Comput. Oper. Res.37(9) (2010) 1537-1543. genRefLink(16, ’S1793830916500580BIB020’, ’10.1016 · Zbl 1187.90136 |
| [21] | 21. A. Lim, B. Rodrigues and Z. Xu, Approximation schemes for the crane scheduling problem, in Algorithm theory, SWAT 2004, Ninth Scandinavian workshop on algorithm theory, Humlebaek, July 8-10 (Springer, Berlin, 2004), pp. 323-335. · Zbl 1095.90551 |
| [22] | 22. A. Lim and Z. Xu, A critical-shaking neighborhood search for the yard allocation problem, European J. Oper. Res.174(2) (2006) 1247-1259. genRefLink(16, ’S1793830916500580BIB022’, ’10.1016 · Zbl 1103.90342 |
| [23] | 23. A. Lim, B. Rodrigues and Z. Xu, A m-parallel crane scheduling problem with a non-crossing constraint, Naval Res. Logist.54(2) (2007) 115-127. genRefLink(16, ’S1793830916500580BIB023’, ’10.1002 · Zbl 1126.90025 |
| [24] | 24. Z. Q. Lu, X. L. Han, L. F. Xi and A. L. Erera, A heuristic for the quay crane scheduling problem based on contiguous bay crane operations, Comput. Oper. Res.39(12) (2012) 2915-2928. genRefLink(16, ’S1793830916500580BIB024’, ’10.1016 · Zbl 1349.90379 |
| [25] | 25. F. Meisel and C. Bierwirth, A unified approach for the evaluation of quay crane scheduling models and algorithms, Comput. Oper. Res.38(3) (2011) 683-693. genRefLink(16, ’S1793830916500580BIB025’, ’10.1016 |
| [26] | 26. F. Meisel and C. Bierwirth, A framework for integrated berth allocation and crane operations planning in seaport container terminals, Trans. Sci.47(2) (2013) 131-147. genRefLink(16, ’S1793830916500580BIB026’, ’10.1287 |
| [27] | 27. L. Moccia, J. F. Cordeau, M. Gaudioso and G. Laporte, A branch-and-cut algorithm for the quay crane scheduling problem in a container terminal, Naval Res. Logist.53(1) (2006) 45-59. genRefLink(16, ’S1793830916500580BIB027’, ’10.1002 · Zbl 1112.90033 |
| [28] | 28. W. C. Ng and K. L. Mak, Quay crane scheduling in container terminals, Eng. Optim.38(6) (2006) 723-737. genRefLink(16, ’S1793830916500580BIB028’, ’10.1080 |
| [29] | 29. M. Pinedo, Scheduling: Theory, Algorithms, and Systems, 2nd edn. (Prentice-Hall, Englewood Cliffs, NJ, 2000). |
| [30] | 30. M. Queyranne and A. S. Schulz, Approximation bounds for a general class of precedence constrained parallel machine scheduling problem, SIAM J. Comput.35(5) (2006) 1241-1253. genRefLink(16, ’S1793830916500580BIB030’, ’10.1137 · Zbl 1100.68010 |
| [31] | 31. R. Stahlbock and S. Vo{\(\beta\)}, Operations research at container terminals: A literature update, OR Spectrum30(1) (2008) 1-52. genRefLink(16, ’S1793830916500580BIB031’, ’10.1007 · Zbl 1133.90313 |
| [32] | 32. D. Steenken, S. Vo{\(\beta\)} and R. Stahlbock, Container terminal operation and operations research – a classification and literature review, OR Spectrum26(1) (2004) 3-49. genRefLink(16, ’S1793830916500580BIB032’, ’10.1007 · Zbl 1160.90322 |
| [33] | 33. I. F. A. Vis and H. J. Carlo, Sequencing two cooperating automated stacking cranes in a container terminal, Transp. Sci.44(2) (2010) 169-182. genRefLink(16, ’S1793830916500580BIB033’, ’10.1287 |
| [34] | 34. S. J. Wang and M. Liu, A genetic algorithm for two-stage no-wait hybrid flow shop scheduling problem, Comput. Oper. Res.40(4) (2013) 1064-1075. genRefLink(16, ’S1793830916500580BIB034’, ’10.1016 · Zbl 1349.90414 |
| [35] | 35. J. K. Lenstra and A. H. G. Rinnooy Kan, Complexity of scheduling under precedence constraints, Operations Research26(1) (1978) 22-35. genRefLink(16, ’S1793830916500580BIB035’, ’10.1287 |
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.
