Please use this identifier to cite or link to this item:
Title: Scheduling arc maintenance jobs in a network to maximize total flow over time
Contributor(s): Boland, Natashia (author); Kalinowski, Thomas  (author)orcid ; Waterer, Hamish (author); Zheng, Lanbo (author)
Publication Date: 2014-01-30
Early Online Version: 2012-07-02
Open Access: Yes
DOI: 10.1016/j.dam.2012.05.027Open Access Link
Handle Link:
Abstract: We consider the problem of scheduling a set of maintenance jobs on the arcs of a network so that the total flow over the planning time horizon is maximized. A maintenance job causes an arc outage for its duration, potentially reducing the capacity of the network. The problem can be expected to have applications across a range of network infrastructures critical to modern life. For example, utilities such as water, sewerage and electricity all flow over networks. Products are manufactured and transported via supply chain networks. Such networks need regular, planned maintenance in order to continue to function. However the coordinated timing of maintenance jobs can have a major impact on the network capacity lost due to maintenance. Here we describe the background to the problem, define it, prove it is strongly NP-hard, and derive four local search-based heuristic methods. These methods integrate exact maximum flow solutions within a local search framework. The availability of both primal and dual solvers, and dual information from the maximum flow solver, is exploited to gain efficiency in the algorithms. The performance of the heuristics is evaluated on both randomly generated instances, and on instances derived from real-world data. These are compared with a state-of-the-art integer programming solver.
Publication Type: Journal Article
Grant Details: ARC/LP0990739
Source of Publication: Discrete Applied Mathematics, 163(1), p. 34-52
Publisher: Elsevier BV
Place of Publication: The Netherlands
ISSN: 0166-218X
Field of Research (FOR): 010303 Optimisation
010206 Operations Research
Peer Reviewed: Yes
HERDC Category Description: C1 Refereed Article in a Scholarly Journal
CC License of All Rights Reserved: Elsevier User License
Appears in Collections:Journal Article
School of Science and Technology

Files in This Item:
1 files
File SizeFormat 
Show full item record
Google Media

Google ScholarTM



Items in Research UNE are protected by copyright, with all rights reserved, unless otherwise indicated.