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-XzbMATH Open1348.90471arXiv1307.3650OpenAlexW1949683236WikidataQ57955336 ScholiaQ57955336MaRDI QIDQ326488FDOQ326488

Authors: Natashia Boland, Thomas Kalinowski, Simranjit Kaur 

Publication date: 12 October 2016

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

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.

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

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
• Scheduling maintenance jobs in networks

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)

Cites Work

• The design of approximation algorithms
• Paths, Trees, and Flowers
• Title not available (Why is that?)
• Max flows in \(O(nm)\) time, or better
• Scheduling
• A Faster Deterministic Maximum Flow Algorithm
• Restoring infrastructure systems: an integrated network design and scheduling (INDS) problem
• Incremental network design with shortest paths
• Integrated network design and scheduling problems with parallel identical machines: Complexity results and dispatching rules
• Incremental network design with maximum flows
• An introduction to network flows over time
• 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
• Multi-period maintenance scheduling of tree networks with minimum flow disruption
• Continuous and discrete flows over time

Cited In (5)

• Improving the scheduling of railway maintenance projects by minimizing passenger delays subject to event requests of railway operators
• Scheduling maintenance jobs in networks
• 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
• Scheduling unit time arc shutdowns to maximize network flow over time: complexity results

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)