Scheduling trains as a blocking parallel-machine job shop scheduling problem

• Published in: Computers & operations research 2009-10, Vol.36 (10), p.2840-2852
• Main Authors: Liu, Shi Qiang, Kozan, Erhan
• Format: Article
• Language: English
• Subjects: Algorithms; Applied sciences; Blocking; Bottlenecks; Exact sciences and technology; Ground, air and sea transportation, marine construction; Inventory control, production control. Distribution; Job shop scheduling; Job shops; Operational research and scientific management; Operational research. Management science; Parallel machine; Production scheduling; Railway transportation and traffic; Scheduling; Scheduling, sequencing; Sensitivity analysis; Studies; Train scheduling
• ISSN: 0305-0548; 1873-765X; 0305-0548
• DOI: 10.1016/j.cor.2008.12.012

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.