2019/10/23 by Saman Eskandarzadeh, Eskandarzadeh, Saman, Thomas Kalinowski +3
Engineering · #90C10 #90C27 #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Packing Problems #Scheduling and Optimization Algorithms #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.1910.10348
openalex publication_date 2019/10/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We investigate a novel scheduling problem which is motivated by an application in the Australian railway industry. Given a set of maintenance jobs and a set of train paths over a railway corridor with bidirectional traffic, we seek a schedule of jobs such that a minimum number of train paths are cancelled due to conflict with the job schedule. We show that the problem is NP-complete in general. In a special case of the problem when every job under any schedule just affects one train path, and the speed of trains is bounded from above and below, we show that the problem can be solved in polynomial time. Moreover, in another special case of the problem where the traffic is unidirectional, we show that the problem can be solved in time O(n4).