Solving train scheduling problems as a job shop: A brief review
Article Sidebar
Main Article Content
Abstract
An interesting practical problem is the single-track train scheduling problem which can be considered a job shop scheduling problem, namely since the sequence of sections is fixed for a train route, it corresponds to fixed machine routes (technological orders) in a job shop scheduling problem. However, for a train scheduling problem, typically some additional constraints such as blocking, sidings, stations with parallel tracks, deadlocks, train length, or headways, etc. have to be considered. The job shop problem has been well investigated in the literature and belongs to the hardest problems in scheduling theory. In this mini-review, some results in this area are discussed, where the main focus is on results that the author has obtained with his collaborators and Ph.D. students during the last decade.
MSC classification: 90 B 35
Downloads
Article Details
Copyright (c) 2022 Frank Werner.
This work is licensed under a Creative Commons Attribution 4.0 International License.
Licensing and protecting the author rights is the central aim and core of the publishing business. Peertechz dedicates itself in making it easier for people to share and build upon the work of others while maintaining consistency with the rules of copyright. Peertechz licensing terms are formulated to facilitate reuse of the manuscripts published in journals to take maximum advantage of Open Access publication and for the purpose of disseminating knowledge.
We support 'libre' open access, which defines Open Access in true terms as free of charge online access along with usage rights. The usage rights are granted through the use of specific Creative Commons license.
Peertechz accomplice with- [CC BY 4.0]
Explanation
'CC' stands for Creative Commons license. 'BY' symbolizes that users have provided attribution to the creator that the published manuscripts can be used or shared. This license allows for redistribution, commercial and non-commercial, as long as it is passed along unchanged and in whole, with credit to the author.
Please take in notification that Creative Commons user licenses are non-revocable. We recommend authors to check if their funding body requires a specific license.
With this license, the authors are allowed that after publishing with Peertechz, they can share their research by posting a free draft copy of their article to any repository or website.
'CC BY' license observance:
|
License Name |
Permission to read and download |
Permission to display in a repository |
Permission to translate |
Commercial uses of manuscript |
|
CC BY 4.0 |
Yes |
Yes |
Yes |
Yes |
The authors please note that Creative Commons license is focused on making creative works available for discovery and reuse. Creative Commons licenses provide an alternative to standard copyrights, allowing authors to specify ways that their works can be used without having to grant permission for each individual request. Others who want to reserve all of their rights under copyright law should not use CC licenses.
Szpigel B. Optimal Train Scheduling on a Single Line Railway. Operations Research. 1973; 72: 344–351.
Cordeau JF, Toth P, Vigo D. A Survey of Optimization Models on Train Routing and Scheduling. Transportation Science. 1998; 32(4):380–404.
Lusby RM, Larsen J, Ehrgott M, Ryan D. Railway Track Allocation: Models and Methods, Operations Research Spectrum. 2011; 33(4):843–883.
Sotskov Y, Gholami O. Shifting Bottleneck Algorithm for Train Scheduling in a Single-Track Railway, Proccedings of the 14th IFAC Symposium on Information Control Problems, Part 1, Bucharest / Romania. 2012; 87– 92.
Gholami O, Sotskov YN, Werner F. Job-Shop Scheduling with Objectives Appropriate for Train Scheduling in a Single-Track Railway, Proceedings of 2nd International Conference on Simulation and Modelling, Technologies and Applications - SIMULTECH 2012, Rome / Italy, 28 - 31 July 2012: 425–430.
Gholami O, Sotskov YN, Werner F. Fast Edge-Orientation Algorithms for Job-Shop Scheduling Problems with Applications to Train Scheduling. International Journal of Operational Research / Nepal. 2013; 2:19–32.
Lange J, Werner F. Approaches to Modeling Train Scheduling Problems as Job-Shops with Blocking Constraints. Journal of Scheduling. 2018; 21:191–207. DOI: 10.1007/s10951-017-0526-0.
Lange J, Werner F. A Permutation-Based Neighborhood for the Blocking Job-shop Problem with Total Tardiness Minimization. In Kliewer, N. Ehmke JF. Borndo¨rfer, R. (eds.), Operations Research Proceedings 2017. Springer, 2018: 581 – 586;
Lange J, Werner F. A Permutation-Based Heuristic Method for the Blocking Job Shop Scheduling Problem. IFAC-PapersOnLine. 2019; 52:1403–1408. DOI: 10.1016 /j.ifacol. 2019.11.395.
Lawrence S. Supplement to Resource Constrained Project Scheduling: an Experimental Investigation of Heuristic Scheduling Techniques, CSIA, Carnegie Mellon University, Pittsburgh, PA, 1984.
Lange J, Werner F. On Neighborhood Structures and Repair Techniques for Blocking Job Shop Problems. Algorithms. 2019; 12(11): 242.
Lange J. Solution Techniques for the Blocking Job Shop Problem with Total Tardiness Minimization, Ph.D. thesis, Otto-von-Guericke Universita¨t Magdeburg, 2019.
Gafarov E, Werner F. Two-Machine Job-Shop Scheduling with Equal Processing Times on Each Machine; Mathematics. 2019; 7(3): 301.
Gafarov ER, Dolgui A, Lazarev AA. Two-Station Single-Track Railway Scheduling Problem with Trains of Equal Speed, Computers and Industrial Engineering. 2015; 85: 260–267.
Zinder Y, Lazarev A, Musatova A, Tarasov I. Scheduling the Two-Way Traffic on a Single-Track Railway with a Siding. Automation and Remote Control. 2018; 79: 506-523.
Dal Sasso V, Lamorgese L, Mannino C, Tancredi A, Ventura P. Easy Cases of Deadlock Detection in Train Scheduling. Operations Research. 2022; 70(4).