  We consider a problem that marries network flows and scheduling, motivated by
the need to schedule maintenance activities in infrastructure networks, such as
rail or general logistics networks. Network elements must undergo regular
preventive maintenance, shutting down the arc for the duration of the activity.
Careful coordination of these arc maintenance jobs can dramatically reduce the
impact of such shutdown jobs on the flow carried by the network. Scheduling
such jobs between given release dates and deadlines so as to maximize the total
flow over time presents an intriguing case to study the role of time
discretization. Here we prove that if the problem data is integer, and no flow
can be stored at nodes, we can restrict attention to integer job start times.
However if flow can be stored, fractional start times may be needed. This makes
traditional strong integer programming scheduling models difficult to apply.
Here we formulate an exact integer programming model for the continuous time
problem, as well as integer programming models based on time discretization
that can provide dual bounds, and that can - with minor modifications - also
yield primal bounds. The resulting bounds are demonstrated to have small gaps
on test instances, and offer a good trade-off for bound quality against
computing time.
