Skip to main content
main-content
Top

Hint

Swipe to navigate through the articles of this issue

Published in: Journal of Scheduling 2/2019

16-07-2018

A multi-mode resource-constrained project scheduling reformulation for the waterway ship scheduling problem

Authors: Alessandro Hill, Eduardo Lalla-Ruiz, Stefan Voß, Marcos Goycoolea

Published in: Journal of Scheduling | Issue 2/2019

Login to get access
share
SHARE

Abstract

In this paper, we address the waterway ship scheduling problem (WSSP), which finds applications in the management of ship arrivals and departures at maritime ports near channels and waterways. It incorporates practically relevant conflicts which stem from tidal changes, curfews, ship properties or traffic. We propose a reformulation of the WSSP as a variant of the multi-mode resource-constrained project scheduling problem, which incorporates time-dependent resource capacities besides earliest and latest start times for the tasks. This problem is solved through integer programming, using a compact mathematical formulation. Our approach outperforms previous methods by solving all the existing literature instances to optimality. Most of them are solved at the root node within less than 2 s.

To get access to this content you need the following product:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Testen Sie jetzt 15 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Testen Sie jetzt 15 Tage kostenlos.

Footnotes
1
http://www.om-db.wi.tum.de/psplib.
 
Literature
go back to reference Amirgaliyeva, Z., Mladenović, N., Todosijević, R., & Urošević, D. (2017). Solving the maximum min-sum dispersion by alternating formulations of two different problems. European Journal of Operational Research, 260(2), 444–459. CrossRef Amirgaliyeva, Z., Mladenović, N., Todosijević, R., & Urošević, D. (2017). Solving the maximum min-sum dispersion by alternating formulations of two different problems. European Journal of Operational Research, 260(2), 444–459. CrossRef
go back to reference Bartusch, M., Möhring, R. H., & Radermacher, F. J. (1988). Scheduling project networks with resource constraints and time windows. Annals of Operations Research, 16(1), 199–240. CrossRef Bartusch, M., Möhring, R. H., & Radermacher, F. J. (1988). Scheduling project networks with resource constraints and time windows. Annals of Operations Research, 16(1), 199–240. CrossRef
go back to reference Beck, J. C., Prosser, P., & Selensky, E. (2002). On the reformulation of vehicle routing problems and scheduling problems. In International symposium on abstraction, reformulation, and approximation (pp. 282–289). Berlin: Springer. Beck, J. C., Prosser, P., & Selensky, E. (2002). On the reformulation of vehicle routing problems and scheduling problems. In International symposium on abstraction, reformulation, and approximation (pp. 282–289). Berlin: Springer.
go back to reference Buhrkal, K., Zuglian, S., Ropke, S., Larsen, J., & Lusby, R. (2011). Models for the discrete berth allocation problem: A computational comparison. Transportation Research Part E: Logistics and Transportation Review, 47(4), 461–473. CrossRef Buhrkal, K., Zuglian, S., Ropke, S., Larsen, J., & Lusby, R. (2011). Models for the discrete berth allocation problem: A computational comparison. Transportation Research Part E: Logistics and Transportation Review, 47(4), 461–473. CrossRef
go back to reference Campbell, J. F., Smith, L. D., Sweeney, D. C. I., Mundy, R., & Nauss, R. M. (2007). Decision tools for reducing congestion at locks on the upper Mississippi river. In 40th Hawaii international conference on system sciences, HICSS (pp. 56–56). IEEE. Campbell, J. F., Smith, L. D., Sweeney, D. C. I., Mundy, R., & Nauss, R. M. (2007). Decision tools for reducing congestion at locks on the upper Mississippi river. In 40th Hawaii international conference on system sciences, HICSS (pp. 56–56). IEEE.
go back to reference Disser, Y., Klimm, M., & Lübbecke, E. (2015). Scheduling bidirectional traffic on a path. In International colloquium on automata, languages, and programming (pp. 406–418). Berlin: Springer. Disser, Y., Klimm, M., & Lübbecke, E. (2015). Scheduling bidirectional traffic on a path. In International colloquium on automata, languages, and programming (pp. 406–418). Berlin: Springer.
go back to reference Du, Y., Chen, Q., Lam, J. S. L., Xu, Y., & Cao, J. X. (2015). Modeling the impacts of tides and the virtual arrival policy in berth allocation. Transportation Science, 49(4), 939–956. CrossRef Du, Y., Chen, Q., Lam, J. S. L., Xu, Y., & Cao, J. X. (2015). Modeling the impacts of tides and the virtual arrival policy in berth allocation. Transportation Science, 49(4), 939–956. CrossRef
go back to reference Ernst, A. T., Oğuz, C., Singh, G., & Taherkhani, G. (2017). Mathematical models for the berth allocation problem in dry bulk terminals. Journal of Scheduling, 20(5), 459–473. CrossRef Ernst, A. T., Oğuz, C., Singh, G., & Taherkhani, G. (2017). Mathematical models for the berth allocation problem in dry bulk terminals. Journal of Scheduling, 20(5), 459–473. CrossRef
go back to reference Fischetti, M., & Monaci, M. (2014). Exploiting erraticism in search. Operations Research, 62(1), 114–122. CrossRef Fischetti, M., & Monaci, M. (2014). Exploiting erraticism in search. Operations Research, 62(1), 114–122. CrossRef
go back to reference Fügenschuh, A. (2011). A set partitioning reformulation of a school bus scheduling problem. Journal of Scheduling, 14(4), 307–318. CrossRef Fügenschuh, A. (2011). A set partitioning reformulation of a school bus scheduling problem. Journal of Scheduling, 14(4), 307–318. CrossRef
go back to reference Hartmann, S., & Briskorn, D. (2010). A survey of variants and extensions of the resource-constrained project scheduling problem. European Journal of Operational Research, 207(1), 1–14. CrossRef Hartmann, S., & Briskorn, D. (2010). A survey of variants and extensions of the resource-constrained project scheduling problem. European Journal of Operational Research, 207(1), 1–14. CrossRef
go back to reference Iris, Ç., Pacino, D., Ropke, S., & Larsen, A. (2015). Integrated berth allocation and quay crane assignment problem: Set partitioning models and computational results. Transportation Research Part E: Logistics and Transportation Review, 81, 75–97. CrossRef Iris, Ç., Pacino, D., Ropke, S., & Larsen, A. (2015). Integrated berth allocation and quay crane assignment problem: Set partitioning models and computational results. Transportation Research Part E: Logistics and Transportation Review, 81, 75–97. CrossRef
go back to reference Lalla-Ruiz, E., Expósito-Izquierdo, C., Melián-Batista, B., & Moreno-Vega, J. M. (2016). A set-partitioning-based model for the berth allocation problem under time-dependent limitations. European Journal of Operational Research, 250(3), 1001–1012. CrossRef Lalla-Ruiz, E., Expósito-Izquierdo, C., Melián-Batista, B., & Moreno-Vega, J. M. (2016). A set-partitioning-based model for the berth allocation problem under time-dependent limitations. European Journal of Operational Research, 250(3), 1001–1012. CrossRef
go back to reference Lalla-Ruiz, E., Shi, X., & Voß, S. (2018). The waterway ship scheduling problem. Transportation Research Part D: Transport and Environment, 60, 191–209. CrossRef Lalla-Ruiz, E., Shi, X., & Voß, S. (2018). The waterway ship scheduling problem. Transportation Research Part D: Transport and Environment, 60, 191–209. CrossRef
go back to reference Lalla-Ruiz, E., & Voß, S. (2016a). Improving solver performance through redundancy. Journal of Systems Science and Systems Engineering, 25(3), 303–325. Lalla-Ruiz, E., & Voß, S. (2016a). Improving solver performance through redundancy. Journal of Systems Science and Systems Engineering, 25(3), 303–325.
go back to reference Lalla-Ruiz, E., & Voß, S. (2016b). Popmusic as a matheuristic for the berth allocation problem. Annals of Mathematics and Artificial Intelligence, 76(1–2), 173–189. Lalla-Ruiz, E., & Voß, S. (2016b). Popmusic as a matheuristic for the berth allocation problem. Annals of Mathematics and Artificial Intelligence, 76(1–2), 173–189.
go back to reference López, C. O., & Beasley, J. (2016). A formulation space search heuristic for packing unequal circles in a fixed size circular container. European Journal of Operational Research, 251(1), 64–73. CrossRef López, C. O., & Beasley, J. (2016). A formulation space search heuristic for packing unequal circles in a fixed size circular container. European Journal of Operational Research, 251(1), 64–73. CrossRef
go back to reference Lübbecke, E. (2015). On- and offline scheduling of bidirectional traffic. Berlin: Logos Verlag Berlin GmbH. Lübbecke, E. (2015). On- and offline scheduling of bidirectional traffic. Berlin: Logos Verlag Berlin GmbH.
go back to reference Norman, R.J. (1973). An algorithm for the scheduling of vessels through the Panama Canal. Ph.D. thesis, Monterey, California. Naval Postgraduate School. Norman, R.J. (1973). An algorithm for the scheduling of vessels through the Panama Canal. Ph.D. thesis, Monterey, California. Naval Postgraduate School.
go back to reference Passchyn, W., Coene, S., Briskorn, D., Hurink, J. L., Spieksma, F. C. R., & Berghe, G. V. (2016). The lockmaster’s problem. European Journal of Operational Research, 251(2), 432–441. CrossRef Passchyn, W., Coene, S., Briskorn, D., Hurink, J. L., Spieksma, F. C. R., & Berghe, G. V. (2016). The lockmaster’s problem. European Journal of Operational Research, 251(2), 432–441. CrossRef
go back to reference Reyck, B. D., & Herroelen, W. (1999). The multi-mode resource-constrained project scheduling problem with generalized precedence relations. European Journal of Operational Research, 119(2), 538–556. CrossRef Reyck, B. D., & Herroelen, W. (1999). The multi-mode resource-constrained project scheduling problem with generalized precedence relations. European Journal of Operational Research, 119(2), 538–556. CrossRef
go back to reference Rocha, R., Grossmann, I. E., & de Aragão, M. V. P. (2017). Petroleum supply planning: Reformulations and a novel decomposition algorithm. Optimization and Engineering, 18(1), 215–240. CrossRef Rocha, R., Grossmann, I. E., & de Aragão, M. V. P. (2017). Petroleum supply planning: Reformulations and a novel decomposition algorithm. Optimization and Engineering, 18(1), 215–240. CrossRef
go back to reference Rom, W. O., Tukel, O. I., & Muscatello, J. R. (2002). MRP in a job shop environment using a resource constrained project scheduling model. Omega, 30(4), 275–286. CrossRef Rom, W. O., Tukel, O. I., & Muscatello, J. R. (2002). MRP in a job shop environment using a resource constrained project scheduling model. Omega, 30(4), 275–286. CrossRef
go back to reference Schwindt, C., & Zimmermann, J. (2015). Handbook on project management and scheduling (Vol. 1). Berlin: Springer. Schwindt, C., & Zimmermann, J. (2015). Handbook on project management and scheduling (Vol. 1). Berlin: Springer.
go back to reference Talbot, F. B. (1982). Resource-constrained project scheduling with time-resource tradeoffs: The nonpreemptive case. Management Science, 28(10), 1197–1210. CrossRef Talbot, F. B. (1982). Resource-constrained project scheduling with time-resource tradeoffs: The nonpreemptive case. Management Science, 28(10), 1197–1210. CrossRef
go back to reference Voß, S., & Lalla-Ruiz, E. (2016). A set partitioning reformulation for the multiple-choice multidimensional knapsack problem. Engineering Optimization, 48(5), 831–850. CrossRef Voß, S., & Lalla-Ruiz, E. (2016). A set partitioning reformulation for the multiple-choice multidimensional knapsack problem. Engineering Optimization, 48(5), 831–850. CrossRef
go back to reference Wang, S., & Meng, Q. (2012). Robust schedule design for liner shipping services. Transportation Research Part E: Logistics and Transportation Review, 48(6), 1093–1106. CrossRef Wang, S., & Meng, Q. (2012). Robust schedule design for liner shipping services. Transportation Research Part E: Logistics and Transportation Review, 48(6), 1093–1106. CrossRef
go back to reference Xu, D., Li, C. L., & Leung, J. Y. T. (2012). Berth allocation with time-dependent physical limitations on vessels. European Journal of Operational Research, 216(1), 47–56. CrossRef Xu, D., Li, C. L., & Leung, J. Y. T. (2012). Berth allocation with time-dependent physical limitations on vessels. European Journal of Operational Research, 216(1), 47–56. CrossRef
go back to reference Zhang, X., Lin, J., Guo, Z., & Liu, T. (2016). Vessel transportation scheduling optimization based on channel-berth coordination. Ocean Engineering, 112, 145–152. CrossRef Zhang, X., Lin, J., Guo, Z., & Liu, T. (2016). Vessel transportation scheduling optimization based on channel-berth coordination. Ocean Engineering, 112, 145–152. CrossRef
go back to reference Zhu, G., Bard, J. F., & Yu, G. (2006). A branch-and-cut procedure for the multimode resource-constrained project-scheduling problem. INFORMS Journal on Computing, 18(3), 377–390. CrossRef Zhu, G., Bard, J. F., & Yu, G. (2006). A branch-and-cut procedure for the multimode resource-constrained project-scheduling problem. INFORMS Journal on Computing, 18(3), 377–390. CrossRef
Metadata
Title
A multi-mode resource-constrained project scheduling reformulation for the waterway ship scheduling problem
Authors
Alessandro Hill
Eduardo Lalla-Ruiz
Stefan Voß
Marcos Goycoolea
Publication date
16-07-2018
Publisher
Springer US
Published in
Journal of Scheduling / Issue 2/2019
Print ISSN: 1094-6136
Electronic ISSN: 1099-1425
DOI
https://doi.org/10.1007/s10951-018-0578-9

Other articles of this Issue 2/2019

Journal of Scheduling 2/2019 Go to the issue

Premium Partner