  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)$.
