Maintenance scheduling in a railway corricdor

10/23/2019
by   Saman Eskandarzadeh, et al.
0

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(n^4).

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset