Arc shutdown scheduling in a capacitated network to maximize flow over time

Research Doctorate - Doctor of Philosophy (PhD)In this research we focus on a problem in the class of network flow problems in which arc capacities vary over time, and the times at which the arc capacities change need to be decided in order to optimize a given objective. In the problem we study, the arc capacities are affected by maintenance jobs, which need to be scheduled within given time windows, and the objective is to maximize the total flow through the network in a given time horizon. Many real world complex problems can be viewed as networks with arc capacities, for example, rail networks, or supply chains, in which system throughput needs to be maximized. Arcs in such a network represent important components of the corresponding system, which must undergo regular preventive maintenance, shutting down the arc for the duration of the activity. But every maintenance activity incurs some impact on the flow carried by the network, as the arc becomes unavailable during its maintenance. Careful coordination of these jobs can often reduce the overall impact on the flow significantly. This motivated us to study the problem of scheduling arc shutdown jobs in a capacitated network so as to maximize the total flow through it in a given time horizon. We assume that each shut down job has a given processing time, release date and deadline; and require that the jobs must be processed in a non-preemptive manner. Assuming that we have enough resources to do all shut down jobs together, at the same time, we present a detailed analysis of how the complexity of a simplified variant of the problem depends on different network and job characteristics. A number of instance classes are identified and their complexity is discussed. Next, a bound is imposed on the number of jobs that can be done at any given time in this simplified variant, and its effect on the complexity of identified instance classes is investigated. Several classes that were polynomial solvable become NP-complete with the introduction of the bound. Scheduling shutdown jobs between given release dates and deadlines so as to maximize the total flow over time also presents an intriguing case to study the role of time discretization. We prove that with integer problem data, and no flow storage 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. 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