Top

Journal of Scheduling

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

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

über 102.000 Bücher
über 537 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

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

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

Jetzt Wissensvorsprung sichern!

inform now

http://www.om-db.wi.tum.de/psplib.

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

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

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.

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

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.

Dassault Systems, D. (2017). Quintic website. Accessed Feburary 02, 2018, from http://www.quintiq.com/news-2017/panama-canal-to-launch-state-of-the-art-vessel-scheduling-and-maritime-resources-management-system.html.

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.

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

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

Fischetti, M., & Monaci, M. (2014). Exploiting erraticism in search. Operations Research, 62(1), 114–122.CrossRef

Fügenschuh, A. (2011). A set partitioning reformulation of a school bus scheduling problem. Journal of Scheduling, 14(4), 307–318.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

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

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., Shi, X., & Voß, S. (2018). The waterway ship scheduling problem. Transportation Research Part D: Transport and Environment, 60, 191–209.CrossRef

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. (2016b). Popmusic as a matheuristic for the berth allocation problem. Annals of Mathematics and Artificial Intelligence, 76(1–2), 173–189.

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übbecke, E. (2015). On- and offline scheduling of bidirectional traffic. Berlin: Logos Verlag Berlin GmbH.

Norman, R.J. (1973). An algorithm for the scheduling of vessels through the Panama Canal. Ph.D. thesis, Monterey, California. Naval Postgraduate School.

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

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

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

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

Schwindt, C., & Zimmermann, J. (2015). Handbook on project management and scheduling (Vol. 1). Berlin: Springer.

Talbot, F. B. (1982). Resource-constrained project scheduling with time-resource tradeoffs: The nonpreemptive case. Management Science, 28(10), 1197–1210.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

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

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

Zhang, X., Lin, J., Guo, Z., & Liu, T. (2016). Vessel transportation scheduling optimization based on channel-berth coordination. Ocean Engineering, 112, 145–152.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

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