Paper Info
Title
Scheduling Trains with Priorities: A No-Wait Blocking Parallel-Machine Job-Shop Scheduling Model
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.
Year
DOI
Venue
2011
10.1287/trsc.1100.0332
Transportation Science
Keywords
Field
DocType
scheduling model,tune-up procedure,nonprioritised train,next section,blocking-time-determination procedure,prioritised train,no-wait blocking parallel-machine job-shop,scheduling trains,best-starting-time-determination procedure,no-wait condition,fine-tune procedure,conflict-checking procedure,conflict-eliminating procedure,algorithms,mathematical models,blocking,methodology,job shop scheduling
Mathematical optimization,Job shop scheduling,Scheduling (computing),Heuristic (computer science),Computer science,Job shop,Schedule,Train,Operations management,Recursion,Traverse
Journal
Volume
Issue
ISSN
45
2
0041-1655
Citations 
PageRank 
References 
11
0.57
17
Authors
2
Name
Order
Citations
PageRank
Shi Qiang Liu1645.40
Erhan Kozan231532.28