Shifting bottleneck algorithm for train scheduling in a single-track railway

A problem of train timetabling for a single-track railway is studied using a disjunctive graph model for the corresponding job-shop. The objective is to minimize the total weighted tardiness of the given trains. A shifting bottleneck algorithm is developed and tested to get a close to optimal schedule to the job-shop problem. At each iteration, this algorithm tries to minimize the total weighted tardiness of jobs (trains) with the given release times (departure times of the trains), the due dates, and the processing times on a single machine (single-track section between two stations). Since the latter problem is unary NP-hard, a heuristic procedure is used at each iteration of the shifting bottleneck algorithm. Computational results demonstrate the dependence of the CPU-time on the number of trains and single-track sections.