Scheduling Trains with Priorities: A No‐Wait Blocking Parallel‐Machine Job‐Shop Scheduling Model

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.