IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v31y2019i3p413-428.html
   My bibliography  Save this article

No-Wait Scheduling for Locks

Author

Listed:
  • Ward Passchyn

    (Faculty of Economics and Business, ORSTAT, KU Leuven, 3000 Leuven, Belgium; OM Partners, 2160 Wommelgem, Belgium;)

  • Dirk Briskorn

    (Lehrstuhl für Produktion und Logistik, Bergische Universität Wuppertal, 42119 Wuppertal, Germany;)

  • Frits C. R. Spieksma

    (Faculty of Economics and Business, ORSTAT, KU Leuven, 3000 Leuven, Belgium; Department of Mathematics and Computer Science, Eindhoven University of Technology, 5600 Eindhoven, Netherlands)

Abstract

We introduce and investigate the problem of scheduling a single lock with parallel chambers. Special cases of this problem are related to interval scheduling. We focus on the existence of no-wait schedules and characterize their feasibility for a lock consisting of two chambers using new graph-theoretical concepts. We obtain a linear time algorithm for this special case. We also provide an efficient algorithm for the case where all chambers of the lock are identical. Furthermore, we describe a dynamic programming algorithm for the general case with arbitrary chambers. Finally, we indicate how our methods for the no-wait case can be applied to practical settings where waiting time is unavoidable.

Suggested Citation

  • Ward Passchyn & Dirk Briskorn & Frits C. R. Spieksma, 2019. "No-Wait Scheduling for Locks," INFORMS Journal on Computing, INFORMS, vol. 31(3), pages 413-428, July.
    • Handle: RePEc:inm:orijoc:v:31:y:2019:i:3:p:413-428
    DOI: 10.1287/ijoc.2018.0848
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/ijoc.2018.0848
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2018.0848?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Douglas Smith, L. & Nauss, Robert M. & Mattfeld, Dirk Christian & Li, Jian & Ehmke, Jan F. & Reindl, M., 2011. "Scheduling operations at system choke points with sequence-dependent delays and processing times," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 47(5), pages 669-680, September.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Lijuan Yang & Eldon Y. Li & Yu Zhang, 2020. "Pricing and Subsidy Models for Transshipment Sustainability in the Three Gorges Dam Region of China," Sustainability, MDPI, vol. 12(17), pages 1-20, August.
    2. Golak, Julian Arthur Pawel & Defryn, Christof & Grigoriev, Alexander, 2022. "Optimizing fuel consumption on inland waterway networks: Local search heuristic for lock scheduling," Omega, Elsevier, vol. 109(C).
    3. Buchem, Moritz & Golak, Julian Arthur Pawel & Grigoriev, Alexander, 2022. "Vessel velocity decisions in inland waterway transportation under uncertainty," European Journal of Operational Research, Elsevier, vol. 296(2), pages 669-678.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Karsu, Özlem & Morton, Alec, 2015. "Inequity averse optimization in operational research," European Journal of Operational Research, Elsevier, vol. 245(2), pages 343-359.
    2. Gharehgozli, Amir & Zaerpour, Nima, 2018. "Stacking outbound barge containers in an automated deep-sea terminal," European Journal of Operational Research, Elsevier, vol. 267(3), pages 977-995.
    3. Buchem, Moritz & Golak, Julian Arthur Pawel & Grigoriev, Alexander, 2022. "Vessel velocity decisions in inland waterway transportation under uncertainty," European Journal of Operational Research, Elsevier, vol. 296(2), pages 669-678.
    4. Golak, Julian Arthur Pawel & Defryn, Christof & Grigoriev, Alexander, 2022. "Optimizing fuel consumption on inland waterway networks: Local search heuristic for lock scheduling," Omega, Elsevier, vol. 109(C).
    5. Passchyn, Ward & Briskorn, Dirk & Spieksma, Frits C.R., 2016. "Mathematical programming models for lock scheduling with an emission objective," European Journal of Operational Research, Elsevier, vol. 248(3), pages 802-814.
    6. Ward Passchyn & Frits C. R. Spieksma, 2019. "Scheduling parallel batching machines in a sequence," Journal of Scheduling, Springer, vol. 22(3), pages 335-357, June.
    7. Lijuan Yang & Eldon Y. Li & Yu Zhang, 2020. "Pricing and Subsidy Models for Transshipment Sustainability in the Three Gorges Dam Region of China," Sustainability, MDPI, vol. 12(17), pages 1-20, August.
    8. Sweeney, Kevin D. & Sweeney, Donald C. & Campbell, James F., 2019. "The performance of priority dispatching rules in a complex job shop: A study on the Upper Mississippi River," International Journal of Production Economics, Elsevier, vol. 216(C), pages 154-172.
    9. Passchyn, Ward & Coene, Sofie & Briskorn, Dirk & Hurink, Johann L. & Spieksma, Frits C.R. & Vanden Berghe, Greet, 2016. "The lockmaster’s problem," European Journal of Operational Research, Elsevier, vol. 251(2), pages 432-441.
    10. Zhao, Ke & Jin, Jian Gang & Zhang, Di & Ji, Sheng & Lee, Der-Horng, 2023. "A variable neighborhood search heuristic for real-time barge scheduling in a river-to-sea channel with tidal restrictions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 179(C).
    11. Nicolas Pinson & Frits C. R. Spieksma, 2019. "Online interval scheduling on two related machines: the power of lookahead," Journal of Combinatorial Optimization, Springer, vol. 38(1), pages 224-253, July.
    12. Deng, Yao & Sheng, Dian & Liu, Baoli, 2021. "Managing ship lock congestion in an inland waterway: A bottleneck model with a service time window," Transport Policy, Elsevier, vol. 112(C), pages 142-161.
    13. Verstichel, J. & De Causmaecker, P. & Spieksma, F.C.R. & Vanden Berghe, G., 2014. "Exact and heuristic methods for placing ships in locks," European Journal of Operational Research, Elsevier, vol. 235(2), pages 387-398.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orijoc:v:31:y:2019:i:3:p:413-428. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.