IDEAS home Printed from https://ideas.repec.org/a/spr/jsched/v22y2019i3d10.1007_s10951-018-0560-6.html
   My bibliography  Save this article

Scheduling parallel batching machines in a sequence

Author

Listed:
  • Ward Passchyn

    (KU Leuven
    OM Partners)

  • Frits C. R. Spieksma

    (KU Leuven
    Eindhoven University of Technology)

Abstract

Motivated by the application of scheduling a sequence of locks along a waterway, we consider a scheduling problem where multiple parallel batching machines are arranged in a sequence and process jobs that travel along this sequence. We investigate the computational complexity of this problem. More specifically, we show that minimizing the sum of completion times is strongly NP-hard, even for two identical machines and when all jobs travel in the same direction. A second NP-hardness result is obtained for a different special case where jobs all travel at an identical speed. Additionally, we introduce a class of so-called synchronized schedules and investigate special cases where the existence of an optimum solution which is synchronized can be guaranteed. Finally, we reinforce the claim that bidirectional travel contributes fundamentally to the computational complexity of this problem by describing a polynomial time procedure for a setting with identical machines and where all jobs travel in the same direction at equal speed.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:jsched:v:22:y:2019:i:3:d:10.1007_s10951-018-0560-6
    DOI: 10.1007/s10951-018-0560-6
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10951-018-0560-6
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10951-018-0560-6?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    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.
    2. 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.
    3. E. R. Petersen & A. J. Taylor, 1988. "An Optimal Scheduling System for the Welland Canal," Transportation Science, INFORMS, vol. 22(3), pages 173-185, August.
    4. 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.
    5. Ove Frank, 1966. "Two-Way Traffic on a Single Line of Railway," Operations Research, INFORMS, vol. 14(5), pages 801-811, October.
    6. L D Smith & D C Sweeney & J F Campbell, 2009. "Simulation of alternative approaches to relieving congestion at locks in a river transportion system," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(4), pages 519-533, April.
    7. Peter Brucker & Sigrid Knust & T.C. Cheng & Natalia Shakhlevich, 2004. "Complexity Results for Flow-Shop and Open-Shop Scheduling Problems with Transportation Delays," Annals of Operations Research, Springer, vol. 129(1), pages 81-106, July.
    8. Giovanni Righini, 2016. "A network flow model of the Northern Italy waterway system," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 5(2), pages 99-122, June.
    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. Leal Filho, Walter & Wall, Tony & Rui Mucova, Serafino Afonso & Nagy, Gustavo J. & Balogun, Abdul-Lateef & Luetz, Johannes M. & Ng, Artie W. & Kovaleva, Marina & Safiul Azam, Fardous Mohammad & Alves,, 2022. "Deploying artificial intelligence for climate change adaptation," Technological Forecasting and Social Change, Elsevier, vol. 180(C).
    2. Christoph Hertrich & Christian Weiß & Heiner Ackermann & Sandy Heydrich & Sven O. Krumke, 2020. "Scheduling a proportionate flow shop of batching machines," Journal of Scheduling, Springer, vol. 23(5), pages 575-593, October.

    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. 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.
    2. 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.
    3. 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).
    4. Ji, Bin & Zhang, Dezhi & Yu, Samson S. & Zhang, Binqiao, 2021. "Optimally solving the generalized serial-lock scheduling problem from a graph-theory-based multi-commodity network perspective," European Journal of Operational Research, Elsevier, vol. 288(1), pages 47-62.
    5. Elisabeth Lübbecke & Marco E. Lübbecke & Rolf H. Möhring, 2019. "Ship Traffic Optimization for the Kiel Canal," Operations Research, INFORMS, vol. 67(3), pages 791-812, May.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. Ziyun Wu & Bin Ji & Samson S. Yu, 2024. "Modeling and Solution Algorithm for Green Lock Scheduling Problem on Inland Waterways," Mathematics, MDPI, vol. 12(8), pages 1-25, April.
    11. 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.
    12. Shuai Jia & Chung-Lun Li & Zhou Xu, 2019. "Managing Navigation Channel Traffic and Anchorage Area Utilization of a Container Port," Transportation Science, INFORMS, vol. 53(3), pages 728-745, May.
    13. 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.
    14. 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.
    15. Ji, Bin & Zhang, Dezhi & Zhang, Zheng & Yu, Samson S. & Van Woensel, Tom, 2022. "The generalized serial-lock scheduling problem on inland waterway: A novel decomposition-based solution framework and efficient heuristic approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 168(C).
    16. Özgecan Ulusçu & Tayfur Altiok, 2013. "Waiting time approximation in multi-class queueing systems with multiple types of class-dependent interruptions," Annals of Operations Research, Springer, vol. 202(1), pages 185-195, January.
    17. Di Zhang & Xinping Yan & Zaili Yang & Jin Wang, 2014. "An accident data–based approach for congestion risk assessment of inland waterways: A Yangtze River case," Journal of Risk and Reliability, , vol. 228(2), pages 176-188, April.
    18. Karsu, Özlem & Morton, Alec, 2015. "Inequity averse optimization in operational research," European Journal of Operational Research, Elsevier, vol. 245(2), pages 343-359.
    19. Leachman, Robert C. & Jula, Payman, 2012. "Estimating flow times for containerized imports from Asia to the United States through the Western rail network," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(1), pages 296-309.
    20. Wiesław Kubiak, 2023. "On the complexity of open shop scheduling with time lags," Journal of Scheduling, Springer, vol. 26(3), pages 331-334, June.

    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:spr:jsched:v:22:y:2019:i:3:d:10.1007_s10951-018-0560-6. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.