  We investigate the problem of scheduling the maintenance of edges in a
network, motivated by the goal of minimizing outages in transportation or
telecommunication networks. We focus on maintaining connectivity between two
nodes over time; for the special case of path networks, this is related to the
problem of minimizing the busy time of machines.
  We show that the problem can be solved in polynomial time in arbitrary
networks if preemption is allowed. If preemption is restricted to integral time
points, the problem is NP-hard and in the non-preemptive case we give strong
non-approximability results. Furthermore, we give tight bounds on the power of
preemption, that is, the maximum ratio of the values of non-preemptive and
preemptive optimal solutions.
  Interestingly, the preemptive and the non-preemptive problem can be solved
efficiently on paths, whereas we show that mixing both leads to a weakly
NP-hard problem that allows for a simple 2-approximation.
