Two-station single-track railway scheduling problem with trains of equal speed |
| |
| Affiliation: | 1. V.A. Trapeznikov Institute of Control Science of Russian Academy of Sciences, Profsoyuznaya st. 65, 117997 Moscow, Russia;2. Ecole Nationale Superieure des Mines, CNRS UMR6158, LIMOS, F-42023 Saint-Etienne, France;3. Lomonosov Moscow State University, GSP-1, Leninskie Gory, Moscow, 119991, Russia;4. Moscow Institute of Physics and Technology, 9 Institutskiy per., Dolgoprudny, Moscow Region, 141700, Russia;5. International Laboratory of Decision Choice and Analysis, National Research University Higher School of Economics, 20 Myasnsnitskaya st., 101000 Moscow, Russia;1. Penn State Berks, Information Sciences and Technology, Tulpehocken Road, PO Box 7009, Reading, PA 19610, United States;2. Penn State Berks, Management Information Systems, Tulpehocken Road, PO Box 7009, Reading, PA 19610, United States;3. Lehigh University, Industrial and Systems Engineering, 200 West Packer Ave., Mohler Lab, Bethlehem, PA 18015, United States;1. Adana Science and Technology University, Engineering and Natural Sciences Faculty, Industrial Engineering Department, Adana, Turkey;2. Cukurova University, The Faculty of Engineering and Architecture, Industrial Engineering Department, Adana, Turkey;1. College of Metropolitan Transportation, Beijing University of Technology, Beijing 100124, China;2. Department of Civil and Environmental Engineering, University of South Florida, Tampa, FL 33620, USA;3. Key Laboratory of Transport Industry of Big Data Application Technologies for Comprehensive Transport, Beijing Jiaotong University, Beijing 100044, China;4. Beijing Urban Construction Group Co., Ltd., Beijing 100088, China;5. Surface Transportation Division, Leidos, Inc., Reston, VA 20190, USA |
| |
| Abstract: | In this paper, the single-track railway scheduling problem with two stations and several segments of the track is considered. Two subsets of trains are given, where trains from the first subset go from the first station to the second station, and trains from the second subset go in the opposite direction. The speed of trains over each segment is the same. A polynomial time reduction from the problem under consideration to a special case of the single-machine equal-processing-time scheduling problem with setup times is presented. Different polynomial time algorithms are developed for special cases with divers objective functions under various constraints. Moreover, several theoretical results which can be ranked in a series of similar investigations of NP-hardness of equal-processing-time single-machine scheduling problems without precedence relations are obtained. |
| |
| Keywords: | Single machine scheduling Setup times Transportation Train scheduling Computational complexity Polynomial time algorithms |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
