Scheduling arc shut downs in a network to maximize flow over time with a bounded number of jobs per time period

DOI10.1007/S10878-015-9910-XMaRDI QIDQ326488zbMATH OpenOpenAlexWikidataFDO

Authors Natashia Boland, Thomas Kalinowski, Simranjit Kaur

Publication date 12 October 2016

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.3650

zbMATH Keywords

complexity theorymixed integer programmingnetwork modelsmaintenance scheduling

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10) Integer programming (90C10)

Abstract: We study the problem of scheduling maintenance on arcs of a capacitated network so as to maximize the total flow from a source node to a sink node over a set of time periods. Maintenance on an arc shuts down the arc for the duration of the period in which its maintenance is scheduled, making its capacity zero for that period. A set of arcs is designated to have maintenance during the planning period, which will require each to be shut down for exactly one time period. In general this problem is known to be NP-hard, and several special instance classes have been studied. Here we propose an additional constraint which limits the number of maintenance jobs per time period, and we study the impact of this on the complexity.

Recommendations

• Scheduling unit time arc shutdowns to maximize network flow over time: complexity results
• Scheduling arc maintenance jobs in a network to maximize total flow over time
• Scheduling network maintenance jobs with release dates and deadlines to maximize total flow over time: bounds and solution strategies
• Multi-period maintenance scheduling of tree networks with minimum flow disruption

Cites work

• scientific article; zbMATH DE number 432790 (Why is no real title available?)
• A Faster Deterministic Maximum Flow Algorithm
• An introduction to network flows over time
• Continuous and discrete flows over time
• Incremental network design with maximum flows
• Incremental network design with shortest paths
• Integrated network design and scheduling problems with parallel identical machines: Complexity results and dispatching rules
• Max flows in \(O(nm)\) time, or better
• Multi-period maintenance scheduling of tree networks with minimum flow disruption
• Paths, Trees, and Flowers
• Restoring infrastructure systems: an integrated network design and scheduling (INDS) problem
• Scheduling
• Scheduling arc maintenance jobs in a network to maximize total flow over time
• Scheduling unit time arc shutdowns to maximize network flow over time: complexity results
• The design of approximation algorithms

Cited in

(4)

• Scheduling network maintenance jobs with release dates and deadlines to maximize total flow over time: bounds and solution strategies
• Scheduling unit time arc shutdowns to maximize network flow over time: complexity results
• Scheduling arc maintenance jobs in a network to maximize total flow over time
• Improving the scheduling of railway maintenance projects by minimizing passenger delays subject to event requests of railway operators

This page was built for publication: Scheduling arc shut downs in a network to maximize flow over time with a bounded number of jobs per time period

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q326488)