Skip to main content
Top
Published in: Journal of Scheduling 4/2014

01-08-2014

Optimization of inland shipping

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

Author: Jens Hermans

Published in: Journal of Scheduling | Issue 4/2014

Log in

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

search-config
loading …

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.

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!

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!

Appendix
Available only for authorised users
Footnotes
1
The superscript \(A\) refers to the direction of the first task in the backschedule.
 
2
This does not include the extra forbidden zones from Sect.  4.2.2.
 
3
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\).
 
4
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.
 
5
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.
 
Literature
go back to reference 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. (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
go back to reference Baptiste, P. (2000). Scheduling equal-length jobs on identical parallel machines. Discrete Applied Mathematics, 103(1–3), 21–32. Baptiste, P. (2000). Scheduling equal-length jobs on identical parallel machines. Discrete Applied Mathematics, 103(1–3), 21–32.
go back to reference 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 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
go back to reference 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 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
go back to reference 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 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
go back to reference Hermans, J. (2008). Optimalisatie van binnenscheepvaart. Master’s thesis, KU Leuven. Hermans, J. (2008). Optimalisatie van binnenscheepvaart. Master’s thesis, KU Leuven.
go back to reference Lawler, E. (1973). Optimal sequencing of a single machine subject to precedence constraints. Management Science, 19(5), 544–546.CrossRef Lawler, E. (1973). Optimal sequencing of a single machine subject to precedence constraints. Management Science, 19(5), 544–546.CrossRef
go back to reference Lodi, A., Martello, S., & Vigo, D. (2002). Recent advances on two-dimensional bin packing problems. Discrete Applied Mathematics, 123(1–3), 379–396.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
go back to reference 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). 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).
go back to reference Simons, B. (1983). Multiprocessor scheduling of unit-time jobs with arbitrary release times and deadlines. SIAM Journal on Computing, 12, 294.CrossRef Simons, B. (1983). Multiprocessor scheduling of unit-time jobs with arbitrary release times and deadlines. SIAM Journal on Computing, 12, 294.CrossRef
go back to reference 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 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
go back to reference 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). 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).
Metadata
Title
Optimization of inland shipping
A polynomial time algorithm for the single-ship single-lock optimization problem
Author
Jens Hermans
Publication date
01-08-2014
Publisher
Springer US
Published in
Journal of Scheduling / Issue 4/2014
Print ISSN: 1094-6136
Electronic ISSN: 1099-1425
DOI
https://doi.org/10.1007/s10951-013-0364-7

Other articles of this Issue 4/2014

Journal of Scheduling 4/2014 Go to the issue