IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v45y2011i2p175-198.html
   My bibliography  Save this article

Scheduling Trains with Priorities: A No-Wait Blocking Parallel-Machine Job-Shop Scheduling Model

Author

Listed:
  • Shi Qiang Liu

    (School of Mathematical Sciences, Queensland University of Technology, Brisbane Qld 4001, Australia)

  • Erhan Kozan

    (School of Mathematical Sciences, Queensland University of Technology, Brisbane Qld 4001, Australia)

Abstract

The paper investigates train scheduling problems when prioritised trains and nonprioritised trains are simultaneously traversed in a single-line rail network. In this case, no-wait conditions arise because the prioritised trains such as express passenger trains should traverse continuously without any interruption. In comparison, nonprioritised trains such as freight trains are allowed to enter the next section immediately if possible or to remain in a section until the next section on the routing becomes available, which is thought of as a relaxation of no-wait conditions. With thorough analysis of the structural properties of the No-Wait Blocking Parallel-Machine Job-Shop Scheduling (NWBPMJSS) problem that is originated in this research, an innovative generic constructive algorithm (called NWBPMJSS_Liu-Kozan) is proposed to construct the feasible train timetable in terms of a given order of trains. In particular, the proposed NWBPMJSS_Liu-Kozan constructive algorithm comprises several recursively used subalgorithms (i.e., Best-Starting-Time-Determination Procedure, Blocking-Time-Determination Procedure, Conflict-Checking Procedure, Conflict-Eliminating Procedure, Tune-Up Procedure, and Fine-Tune Procedure) to guarantee feasibility by satisfying the blocking, no-wait, deadlock-free, and conflict-free constraints. A two-stage hybrid heuristic algorithm (NWBPMJSS_Liu-Kozan-BIH) is developed by combining the NWBPMJSS_Liu-Kozan constructive algorithm and the Best-Insertion-Heuristic (BIH) algorithm to find the preferable train schedule in an efficient and economical way. Extensive computational experiments show that the proposed methodology is promising because it can be applied as a standard and fundamental toolbox for identifying, analysing, modelling, and solving real-world scheduling problems.

Suggested Citation

  • Shi Qiang Liu & Erhan Kozan, 2011. "Scheduling Trains with Priorities: A No-Wait Blocking Parallel-Machine Job-Shop Scheduling Model," Transportation Science, INFORMS, vol. 45(2), pages 175-198, May.
    • Handle: RePEc:inm:ortrsc:v:45:y:2011:i:2:p:175-198
    DOI: 10.1287/trsc.1100.0332
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.1100.0332
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.1100.0332?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. Christian Liebchen, 2008. "The First Optimized Railway Timetable in Practice," Transportation Science, INFORMS, vol. 42(4), pages 420-435, November.
    2. Carey, Malachy & Crawford, Ivan, 2007. "Scheduling trains on a network of busy complex stations," Transportation Research Part B: Methodological, Elsevier, vol. 41(2), pages 159-178, February.
    3. Alberto Caprara & Matteo Fischetti & Paolo Toth, 2002. "Modeling and Solving the Train Timetabling Problem," Operations Research, INFORMS, vol. 50(5), pages 851-861, October.
    4. D'Ariano, Andrea & Pacciarelli, Dario & Pranzo, Marco, 2007. "A branch and bound algorithm for scheduling trains in a railway network," European Journal of Operational Research, Elsevier, vol. 183(2), pages 643-657, December.
    5. S. Q. Liu & H. L. Ong, 2004. "Metaheuristics For The Mixed Shop Scheduling Problem," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 21(01), pages 97-115.
    6. Burdett, R.L. & Kozan, E., 2006. "Techniques for absolute capacity determination in railways," Transportation Research Part B: Methodological, Elsevier, vol. 40(8), pages 616-632, September.
    7. Chung, Ji-Won & Oh, Seog-Moon & Choi, In-Chan, 2009. "A hybrid genetic algorithm for train sequencing in the Korean railway," Omega, Elsevier, vol. 37(3), pages 555-565, June.
    8. E. R. Petersen, 1974. "Over-the-Road Transit Time for a Single Track Railway," Transportation Science, INFORMS, vol. 8(1), pages 65-74, February.
    9. Mascis, Alessandro & Pacciarelli, Dario, 2002. "Job-shop scheduling with blocking and no-wait constraints," European Journal of Operational Research, Elsevier, vol. 143(3), pages 498-517, December.
    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. Allahverdi, Ali, 2016. "A survey of scheduling problems with no-wait in process," European Journal of Operational Research, Elsevier, vol. 255(3), pages 665-686.
    2. Marco Pranzo & Dario Pacciarelli, 2016. "An iterated greedy metaheuristic for the blocking job shop scheduling problem," Journal of Heuristics, Springer, vol. 22(4), pages 587-611, August.
    3. Mina Aliakbari & Joseph Geunes, 2022. "Multiple Train Repositioning Operations in a Railyard Network," SN Operations Research Forum, Springer, vol. 3(4), pages 1-31, December.
    4. Sels, P. & Dewilde, T. & Cattrysse, D. & Vansteenwegen, P., 2016. "Reducing the passenger travel time in practice by the automated construction of a robust railway timetable," Transportation Research Part B: Methodological, Elsevier, vol. 84(C), pages 124-156.
    5. Talebian, Ahmadreza & Zou, Bo, 2015. "Integrated modeling of high performance passenger and freight train planning on shared-use corridors in the US," Transportation Research Part B: Methodological, Elsevier, vol. 82(C), pages 114-140.
    6. Burdett, RL, 2016. "Optimisation models for expanding a railway's theoretical capacity," European Journal of Operational Research, Elsevier, vol. 251(3), pages 783-797.
    7. Jayanth Krishna Mogali & Joris Kinable & Stephen F. Smith & Zachary B. Rubinstein, 2021. "Scheduling for multi-robot routing with blocking and enabling constraints," Journal of Scheduling, Springer, vol. 24(3), pages 291-318, June.
    8. Yu-Jun Zheng, 2018. "Emergency Train Scheduling on Chinese High-Speed Railways," Transportation Science, INFORMS, vol. 52(5), pages 1077-1091, October.
    9. Ahmadian, Mohammad Mahdi & Salehipour, Amir & Cheng, T.C.E., 2021. "A meta-heuristic to solve the just-in-time job-shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 288(1), pages 14-29.
    10. Meloni, Carlo & Pranzo, Marco & Samà, Marcella, 2022. "Evaluation of VaR and CVaR for the makespan in interval valued blocking job shops," International Journal of Production Economics, Elsevier, vol. 247(C).
    11. Fei Luan & Zongyan Cai & Shuqiang Wu & Shi Qiang Liu & Yixin He, 2019. "Optimizing the Low-Carbon Flexible Job Shop Scheduling Problem with Discrete Whale Optimization Algorithm," Mathematics, MDPI, vol. 7(8), pages 1-17, August.

    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. Matthew E. H. Petering & Mojtaba Heydar & Dietrich R. Bergmann, 2016. "Mixed-Integer Programming for Railway Capacity Analysis and Cyclic, Combined Train Timetabling and Platforming," Transportation Science, INFORMS, vol. 50(3), pages 892-909, August.
    2. Burdett, R.L. & Kozan, E., 2009. "Techniques for inserting additional trains into existing timetables," Transportation Research Part B: Methodological, Elsevier, vol. 43(8-9), pages 821-836, September.
    3. Cacchiani, Valentina & Furini, Fabio & Kidd, Martin Philip, 2016. "Approaches to a real-world Train Timetabling Problem in a railway node," Omega, Elsevier, vol. 58(C), pages 97-110.
    4. Wang, Dian & D’Ariano, Andrea & Zhao, Jun & Zhong, Qingwei & Peng, Qiyuan, 2022. "Integrated rolling stock deadhead routing and timetabling in urban rail transit lines," European Journal of Operational Research, Elsevier, vol. 298(2), pages 526-559.
    5. Min, Yun-Hong & Park, Myoung-Ju & Hong, Sung-Pil & Hong, Soon-Heum, 2011. "An appraisal of a column-generation-based algorithm for centralized train-conflict resolution on a metropolitan railway network," Transportation Research Part B: Methodological, Elsevier, vol. 45(2), pages 409-429, February.
    6. Corman, Francesco & D'Ariano, Andrea & Pacciarelli, Dario & Pranzo, Marco, 2010. "A tabu search algorithm for rerouting trains during rail operations," Transportation Research Part B: Methodological, Elsevier, vol. 44(1), pages 175-192, January.
    7. Corman, F. & D’Ariano, A. & Pacciarelli, D. & Pranzo, M., 2012. "Optimal inter-area coordination of train rescheduling decisions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(1), pages 71-88.
    8. Meng, Lingyun & Zhou, Xuesong, 2014. "Simultaneous train rerouting and rescheduling on an N-track network: A model reformulation with network-based cumulative flow variables," Transportation Research Part B: Methodological, Elsevier, vol. 67(C), pages 208-234.
    9. Jiateng Yin & Lixing Yang & Andrea D’Ariano & Tao Tang & Ziyou Gao, 2022. "Integrated Backup Rolling Stock Allocation and Timetable Rescheduling with Uncertain Time-Variant Passenger Demand Under Disruptive Events," INFORMS Journal on Computing, INFORMS, vol. 34(6), pages 3234-3258, November.
    10. Sartor, Giorgio & Mannino, Carlo & Nygreen, Thomas & Bach, Lukas, 2023. "A MILP model for quasi-periodic strategic train timetabling," Omega, Elsevier, vol. 116(C).
    11. Bettinelli, Andrea & Santini, Alberto & Vigo, Daniele, 2017. "A real-time conflict solution algorithm for the train rescheduling problem," Transportation Research Part B: Methodological, Elsevier, vol. 106(C), pages 237-265.
    12. Mina Aliakbari & Joseph Geunes, 2022. "Multiple Train Repositioning Operations in a Railyard Network," SN Operations Research Forum, Springer, vol. 3(4), pages 1-31, December.
    13. Huang, Yeran & Mannino, Carlo & Yang, Lixing & Tang, Tao, 2020. "Coupling time-indexed and big-M formulations for real-time train scheduling during metro service disruptions," Transportation Research Part B: Methodological, Elsevier, vol. 133(C), pages 38-61.
    14. Jiang, Feng & Cacchiani, Valentina & Toth, Paolo, 2017. "Train timetabling by skip-stop planning in highly congested lines," Transportation Research Part B: Methodological, Elsevier, vol. 104(C), pages 149-174.
    15. Zhang, Chuntian & Gao, Yuan & Cacchiani, Valentina & Yang, Lixing & Gao, Ziyou, 2023. "Train rescheduling for large-scale disruptions in a large-scale railway network," Transportation Research Part B: Methodological, Elsevier, vol. 174(C).
    16. Han Zheng & Junhua Chen & Zhaocha Huang & Jianhao Zhu, 2022. "Joint Optimization of Multi-Cycle Timetable Considering Supply-to-Demand Relationship and Energy Consumption for Rail Express," Mathematics, MDPI, vol. 10(21), pages 1-29, November.
    17. Dewilde, Thijs & Sels, Peter & Cattrysse, Dirk & Vansteenwegen, Pieter, 2014. "Improving the robustness in railway station areas," European Journal of Operational Research, Elsevier, vol. 235(1), pages 276-286.
    18. 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.
    19. Mogali, Jayanth Krishna & Barbulescu, Laura & Smith, Stephen F., 2021. "Efficient primal heuristic updates for the blocking job shop problem," European Journal of Operational Research, Elsevier, vol. 295(1), pages 82-101.
    20. Zhang, Yongxiang & Peng, Qiyuan & Yao, Yu & Zhang, Xin & Zhou, Xuesong, 2019. "Solving cyclic train timetabling problem through model reformulation: Extended time-space network construct and Alternating Direction Method of Multipliers methods," Transportation Research Part B: Methodological, Elsevier, vol. 128(C), pages 344-379.

    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:ortrsc:v:45:y:2011:i:2:p:175-198. 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.