nach oben

Journal of Scheduling

Erschienen in:

01.08.2014

Optimization of inland shipping

A polynomial time algorithm for the single-ship single-lock optimization problem

verfasst von: Jens Hermans

Erschienen in: Journal of Scheduling | Ausgabe 4/2014

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this paper, we explore problems and algorithms related to the optimisation of locks, as used in inland shipping. We define several optimisation problems associated with inland shipping. We prove that the problem of scheduling a lock is NP-hard if one allows multiple ships to go through in the same lock operation. The single-ship lock optimization problem can, however, be solved in polynomial time and a novel deterministic scheduling algorithm for solving this problem is presented in this paper.

Nächster Artikel Linear programming-based algorithms for the minimum makespan high multiplicity jobshop problem

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

Nur mit Berechtigung zugänglich

The superscript \(A\) refers to the direction of the first task in the backschedule.

This does not include the extra forbidden zones from Sect. 4.2.2.

Note that if there is an effective forbidden zone \(\tilde{FA}\) between the first \(B\) task and the \(A\) task, then the \(A\)-task would shift to \(\inf (\tilde{FA}) < s_L + 2\).

In 4.2.2 ‘extra’ forbidden zones are defined that could be used to construct an alternative algorithm. One would suspect that using these extra zones would cause a massive number of these ‘influencing’ problems, in which the newly defined forbidden zones influence the previous executions of backscheduling. The results stated here, however, hint otherwise. It is an open problem to check if our results can be extended to these ‘extra’ forbidden zones and by doing this showing even more of the underlying structure of the problem.

In the case that \(r_l^B\) was replaced by \(r'^B_l\) because of one or multiple \(E_2\) events (without any simultaneous \(E_1\) event) the lemma still holds, but \(r_l^B\) is just replaced by \(r'^B_l\) in the proof.

Baptiste, P. (1999). Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times. Journal of Scheduling, 2(6), 245–252.CrossRef

Baptiste, P. (2000). Scheduling equal-length jobs on identical parallel machines. Discrete Applied Mathematics, 103(1–3), 21–32.

Brucker, P., & Knust, S. (2009). Complexity results for scheduling problems. http://www.informatik.uni-osnabrueck.de/knust/class/.

Chrobak, M., Dürr, C., Jawor, W., Kowalik, L., & Kurowski, M. (2006). A note on scheduling equal-length jobs to maximize throughput. Journal of Scheduling, 9(1), 71–73.CrossRef

FKS. (2007). Formal & knowledge systems—waterborne. Retrieved from http://www.fks-waterborne.eu/.

Garey, M., Johnson, D., Simons, B., & Tarjan, R. (1981). Scheduling unit-time tasks with arbitrary release times and deadlines. SIAM Journal on Computing, 10(2), 256–269.CrossRef

Graham, R., Lawler, E., Lenstra, J., & Kan, A. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5(2), 287–326.CrossRef

Hermans, J. (2008). Optimalisatie van binnenscheepvaart. Master’s thesis, KU Leuven.

Lawler, E. (1973). Optimal sequencing of a single machine subject to precedence constraints. Management Science, 19(5), 544–546.CrossRef

Lodi, A., Martello, S., & Vigo, D. (2002). Recent advances on two-dimensional bin packing problems. Discrete Applied Mathematics, 123(1–3), 379–396.CrossRef

López-Ortiz, A., & Quimper, C. G. (2011). A fast algorithm for multi-machine scheduling problems with jobs of equal processing times. In T. Schwentick, & C. Dürr (Eds.), Symposium on Theoretical Aspects of Computer Science (STACS), Vol. 9 of Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (pp. 380–391).

Mundy, R., & Campbell, J. (2005). Management systems for inland waterway traffic control. Technical report. Retrieved from http://www.ctre.iastate.edu/mtc/reports/inland_waterway/volume1.htm.

Simons, B. (1983). Multiprocessor scheduling of unit-time jobs with arbitrary release times and deadlines. SIAM Journal on Computing, 12, 294.CrossRef

Ting, C., & Schonfeld, P. (1998). Integrated control for series of waterway locks. Journal of Waterway, Port, Coastal and Ocean Engineering, 124(4), 199–207.CrossRef

Zhang, X., Qi, H., Fu, X., & Yuan, X. (2007). Hybrid algorithm to minimize total weighted wait-time of ships for navigation co-scheduling in the three Gorges project. In International Conference on Transportation, Engineering (pp. 2759–2764).

Titel: Optimization of inland shipping
A polynomial time algorithm for the single-ship single-lock optimization problem
verfasst von: Jens Hermans
Publikationsdatum: 01.08.2014
Verlag: Springer US
Erschienen in: Journal of Scheduling / Ausgabe 4/2014
Print ISSN: 1094-6136
Elektronische ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-013-0364-7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 4/2014

Single-processor scheduling with time restrictions

Frequency capping in online advertising

Flow shop batching and scheduling with sequence-dependent setup times

On the configuration-LP for scheduling on unrelated machines

Rescheduling for machine disruption to minimize makespan and maximum lateness

Linear programming-based algorithms for the minimum makespan high multiplicity jobshop problem

Premium Partner