Paper Info
Title
Scheduling trains as a blocking parallel-machine job shop scheduling problem
Abstract
In this paper, the train scheduling problem is modelled as a blocking parallel-machine job shop scheduling (BPMJSS) problem. In the model, trains, single-track sections and multiple-track sections, respectively, are synonymous with jobs, single machines and parallel machines, and an operation is regarded as the movement/traversal of a train across a section. Due to the lack of buffer space, the real-life case should consider blocking or hold-while-wait constraints, which means that a track section cannot release and must hold the train until next section on the routing becomes available. Based on literature review and our analysis, it is very hard to find a feasible complete schedule directly for BPMJSS problems. Firstly, a parallel-machine job-shop-scheduling (PMJSS) problem is solved by an improved shifting bottleneck procedure (SBP) algorithm without considering blocking conditions. Inspired by the proposed SBP algorithm, feasibility satisfaction procedure (FSP) algorithm is developed to solve and analyse the BPMJSS problem, by an alternative graph model that is an extension of the classical disjunctive graph models. The proposed algorithms have been implemented and validated using real-world data from Queensland Rail. Sensitivity analysis has been applied by considering train length, upgrading track sections, increasing train speed and changing bottleneck sections. The outcomes show that the proposed methodology would be a very useful tool for the real-life train scheduling problems.
Year
DOI
Venue
2009
10.1016/j.cor.2008.12.012
Computers & Operations Research
Keywords
DocType
Volume
next section,bottleneck section,parallel-machine job shop scheduling,train length,real-life train scheduling problem,multiple-track section,train speed,scheduling train,track section,train scheduling problem,bpmjss problem,blocking,job shop scheduling
Journal
36
Issue
ISSN
Citations 
10
Computers and Operations Research
15
PageRank 
References 
Authors
0.79
9
2
Name
Order
Citations
PageRank
Shi Qiang Liu1645.40
Erhan Kozan231532.28