- Title
- Scheduling unit time arc shutdowns to maximize network flow over time: complexity results
- Creator
- Boland, Natashia; Kapoor, Reena; Kaur, Simranjit; Kalinowski, Thomas
- Relation
- ARC
- Relation
- Networks Vol. 63, Issue 2, p. 196-202
- Publisher Link
- http://dx.doi.org/10.1002/net.21536
- Publisher
- Wiley-Blackwell Publishing Ltd
- Resource Type
- journal article
- Date
- 2014
- Description
- We study the problem of scheduling maintenance on arcs of a capacitated network 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. Here we identify a number of characteristics that are relevant for the complexity of instance classes. In particular, we discuss instances with restrictions on the set of arcs that have maintenance to be scheduled; series-parallel networks; capacities that are balanced, in the sense that the total capacity of arcs entering a (nonterminal) node equals the total capacity of arcs leaving the node; and identical capacities on all arcs.
- Subject
- network models; complexity theory; maintenance scheduling; mixed integer programming
- Identifier
- http://hdl.handle.net/1959.13/1064288
- Identifier
- uon:17509
- Identifier
- ISSN:0028-3045
- Rights
- This is the peer reviewed version of above article, which has been published in final form at http://dx.doi.org/10.1002/net.21536. This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Use of Self-Archived Versions.
- Language
- eng
- Full Text
- Reviewed
- Hits: 1687
- Visitors: 2439
- Downloads: 400
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | ATTACHMENT02 | Author final version | 398 KB | Adobe Acrobat PDF | View Details Download |