×

The lockmaster’s problem. (English) Zbl 1346.90597

Summary: Inland waterways form a natural network infrastructure with capacity for more traffic. Transportation by ship is widely promoted as it is a reliable, efficient and environmental friendly way of transport. Nevertheless, locks managing the water level on waterways and within harbors sometimes constitute bottlenecks for transportation over water. The lockmaster’s problem concerns the optimal strategy for operating such a lock. In the lockmaster’s problem we are given a lock, a set of upstream-bound ships and another set of ships traveling in the opposite direction. We are given the arrival times of the ships and a constant lockage time; the goal is to minimize total waiting time of the ships. In this paper, a dynamic programming algorithm is proposed that solves the lockmaster’s problem in polynomial time. This algorithm can also be used to solve a single batching machine scheduling problem more efficiently than the current algorithms from the literature do. We extend the algorithm such that it can be applied in realistic settings, taking into account capacity, ship-dependent handling times, weights and water usage. In addition, we compare the performance of this new exact algorithm with the performance of some (straightforward) heuristics in a computational study.

MSC:

90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
90B35 Deterministic scheduling theory in operations research
90C39 Dynamic programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aggarwal, A.; Park, J. K., Improved algorithms for economic lot size problems, Operations Research, 41, 549-571 (1993) · Zbl 0820.90035
[3] Baptiste, P., Batching identical jobs, Mathematical Methods of Operations Research, 52, 355-367 (2000) · Zbl 1023.90020
[4] Boudhar, M., Scheduling a batch processing machine with bipartite compatibility graphs, Mathematical Methods of Operations Research, 57, 513-527 (2003) · Zbl 1175.90158
[5] Brucker, P.; Gladky, A.; Hoogeveen, H.; Kovalyov, M. Y.; Potts, C. N.; Tautenhahn, T.; van de Velde, S. L., Scheduling a batching machine, Journal of Scheduling, 1, 31-54 (1998) · Zbl 0909.90172
[6] Cheng, T. C.E.; Yuan, J. J.; Yang, A. F., Scheduling a batch-processing machine subject to precedence constraints, release dates and identical processing times, Computers and Operations Research, 32, 849-859 (2005) · Zbl 1071.90528
[8] Coene, S.; Spieksma, F. C.R., The Lockmaster’s problem, (Caprara, A.; Kontogiannis, S., 11th workshop on algorithmic approaches for transportation modelling, optimization, and systems, vol. 20 (2011), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik: Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik Dagstuhl, Germany), 27-37 · Zbl 1247.90039
[9] Condotta, A.; Knust, S.; Shakhlevich, N. V., Parallel batch scheduling of equal-length jobs with release and due dates, Journal of Scheduling, 13, 463-477 (2010) · Zbl 1208.90057
[10] Du, J. N.; Yu, S. M., Dynamic programming model and algorithm of shiplock scheduling problem., Computer and Digital Engineering, 31, 47-50 (2003)
[12] Federgruen, A.; Tzur, M., A simple forward algorithm to solve dynamic lot sizing models with n periods in o(n log n) or o(n) time, Management Science, 37, 909-925 (1991) · Zbl 0748.90011
[13] Finke, G.; Jost, V.; Queyranne, M.; Sebő, A., Batch processing with interval graph compatibilities between tasks, Discrete Applied Mathematics, 156, 556-568 (2008) · Zbl 1172.90399
[14] Goodban Belt LLC, New York State Canal System, Technical Report (2010)
[15] Griffiths, J. D., Queueing at the suez canal, Journal of the Operational Research Society, 46, 1299-1309 (1995)
[17] Hermans, J., Optimization of inland shipping - a polynomial time algorithm for the single ship single lock optimization problem, Journal of Scheduling, 17, 305-319 (2014) · Zbl 1305.90188
[18] Inland Navigation Europe, Annual Report, Technical Report (2014)
[19] Lee, C.; Uzsoy, R.; Martin-Vega, L. A., Efficient algorithms for scheduling semiconductor burn-in operations, Operations Research, 40, 764-775 (1992) · Zbl 0759.90046
[20] Luy, M., Algoritmen zum scheduling von schleusungsvorgängen am beispiel des nord-ostsee-kanals (2010), Master’s thesis. TU Berlin
[21] Nauss, R. M., Optimal sequencing in the presence of setup times for tow/barge traffic through a river lock, European Journal of Operational Research, 187, 1268-1281 (2008) · Zbl 1137.90427
[22] Ng, C. T.; Cheng, T. C.E.; Yuan, J. J.; Liu, Z. H., On the single machine serial batching scheduling problem to minimize total completion time with precedence constraints, release dates and identical processing times, Operations Research Letters, 31, 323-326 (2003) · Zbl 1145.90392
[23] Panama Canal Authority, Proposal for the expansion of the Panama Canal, Technical Report (2006)
[24] Passchyn, W.; Coene, S.; Briskorn, D.; Hurink, J. L.; Spieksma, F. C.R.; Vanden Berghe, G., The Lockmaster’s Problem, Research report KBI_1530 (2015), KU Leuven, Department of Decision Sciences and Information Management: KU Leuven, Department of Decision Sciences and Information Management Leuven, Belgium, https://lirias.kuleuven.be/bitstream/123456789/520009/1/KBI_1530.pdf · Zbl 1346.90597
[25] Petersen, E. R.; Taylor, A. J., An optimal scheduling system for the Welland Canal, Transportation Science, 22, 173-185 (1988) · Zbl 0645.90040
[26] Potts, C. N.; Kovalyov, M. Y., Scheduling with batching: a review, European Journal of Operational Research, 120, 228-249 (2000) · Zbl 0953.90028
[29] Smith, L. D.; Nauss, R. M.; Mattfeld, D. C.; Li, J.; Ehmke, J. F.; Reindl, M., Scheduling operations at system choke points with sequence-dependent delays and processing times, Transportation Research Part E, 47, 669-680 (2011)
[30] Smith, L. D.; Sweeney, D. C.; Campbell, J. F., Simulation of alternative approaches to relieving congestion at locks in a river transportation system, Journal of the Operational Research Society, 60, 519-533 (2009) · Zbl 1163.90411
[31] Ting, C.; Schonfeld, P., Control alternatives at a waterway lock, Journal of Waterway, Port, Coastal, and Ocean Engineering, 127, 89-96 (2001)
[32] U. S. Army Corps of Engineers, Waterborne commerce from the United States, Technical Report (2009)
[33] van Haastert, M., Planningsmodel scheepvaartafhandeling bij de noordersluis in IJmuiden (2003), Master’s thesis. TU Delft
[34] Verstichel, J.; De Causmaecker, P.; Spieksma, F. C.R.; Vanden Berghe, G., Exact and heuristic methods for placing ships in locks, European Journal of Operational Research, 235, 387-398 (2014) · Zbl 1305.90262
[35] Verstichel, J.; De Causmaecker, P.; Spieksma, F. C.R.; Vanden Berghe, G., The generalized lock scheduling problem: an exact approach, Transportation Research Part E, 65, 16-34 (2014)
[36] Verstichel, J.; Vanden Berghe, G., A late acceptance algorithm for the lock scheduling problem, Logistik Management, 5, 457-478 (2009)
[37] Wagelmans, A.; Van Hoesel, S.; Kolen, A., Economic lot sizing: an o(n log n) algorithm that runs in linear time in the wagner-whitin case, Operations Research, 40, S145-S156 (1992) · Zbl 0771.90031
[38] Webster, S.; Baker, K. R., Scheduling groups of jobs on a single machine, Operations Research, 43, 692-703 (1995) · Zbl 0857.90062
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.