Two-station single-track railway scheduling problem with trains of equal speed

被引：16

作者：

Gafarov, Evgeny R. ^{[1
]}

Dolgui, Alexandre ^{[2
]}

Lazarev, Alexander A. ^{[1
,3
,4
,5
]}

机构：

[1] Russian Acad Sci, VA Trapeznikov Inst Control Sci, Moscow 117997, Russia

[2] Ecole Natl Super Mines, CNRS UMR6158, LIMOS, F-42023 St Etienne, France

[3] Moscow MV Lomonosov State Univ, Moscow 119991, Russia

[4] Moscow Inst Phys & Technol, Dolgoprudnyi 141700, Moscow Region, Russia

[5] Natl Res Univ, Higher Sch Econ, Int Lab Decis Choice & Anal, Moscow 101000, Russia

来源：

COMPUTERS & INDUSTRIAL ENGINEERING | 2015年 / 85卷

基金：

俄罗斯基础研究基金会;

关键词：

Single machine scheduling; Setup times; Transportation; Train scheduling; Computational complexity; Polynomial time algorithms; SETUP TIMES; WEIGHTED NUMBER; TARDY JOBS; MACHINE; MINIMIZE;

D O I：

10.1016/j.cie.2015.03.014

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

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. (C) 2015 Elsevier Ltd. All rights reserved.

引用

页码：260 / 267

页数：8

共 50 条

[1] A Metric Approach for the Two-Station Single-Track Railway Scheduling Problem
Cheng, T. C. Edwin
Lazarev, Alexander
Lemtyuzhnikova, Darya
IFAC PAPERSONLINE, 2022, 55 (10): : 2875 - 2880
[2] Two-Station Single Track Scheduling Problem
Zinder, Yakov
Lazarev, Alexander A.
Musatova, Elena G.
Tarasov, Ilia A.
Khusnullin, Nail F.
IFAC PAPERSONLINE, 2016, 49 (12): : 231 - 236
[3] The Problem of Scheduling for the Linear Section of a Single-track Railway
Akimova, Elena N.
Gainanov, Damir N.
Golubev, Oleg A.
Kolmogortsev, Ilya D.
Konygin, Anton V.
PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON NUMERICAL ANALYSIS AND APPLIED MATHEMATICS 2015 (ICNAAM-2015), 2016, 1738
[4] Two-directional traffic scheduling problem solution for a single-track railway with siding
A. A. Lazarev
E. G. Musatova
I. A. Tarasov
Automation and Remote Control, 2016, 77 : 2118 - 2131
[5] Two-directional traffic scheduling problem solution for a single-track railway with siding
Lazarev, A. A.
Musatova, E. G.
Tarasov, I. A.
AUTOMATION AND REMOTE CONTROL, 2016, 77 (12) : 2118 - 2131
[6] Scheduling the Two-Way Traffic on a Single-Track Railway with a Siding
Y. Zinder
A. A. Lazarev
E. G. Musatova
I. A. Tarasov
Automation and Remote Control, 2018, 79 : 506 - 523
[7] Scheduling the Two-Way Traffic on a Single-Track Railway with a Siding
Zinder, Y.
Lazarev, A. A.
Musatova, E. G.
Tarasov, I. A.
AUTOMATION AND REMOTE CONTROL, 2018, 79 (03) : 506 - 523
[8] Train Trajectory Optimization of Opposite Trains on Single-Track Railway Lines
Wang, Pengling
Goverde, Rob M. P.
2016 IEEE INTERNATIONAL CONFERENCE ON INTELLIGENT RAIL TRANSPORTATION (ICIRT), 2016, : 29 - 37
[9] An efficient train scheduling algorithm on a single-track railway system
Xiaoming Xu
Keping Li
Lixing Yang
Ziyou Gao
Journal of Scheduling, 2019, 22 : 85 - 105
[10] An efficient train scheduling algorithm on a single-track railway system
Xu, Xiaoming
Li, Keping
Yang, Lixing
Gao, Ziyou
JOURNAL OF SCHEDULING, 2019, 22 (01) : 85 - 105

← 1 2 3 4 5 →