Please use this identifier to cite or link to this item:
https://hdl.handle.net/1959.11/26779
Title: | Scheduling arc maintenance jobs in a network to maximize total flow over time | Contributor(s): | Boland, Natashia (author); Kalinowski, Thomas (author) ; 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.027 | Handle Link: | https://hdl.handle.net/1959.11/26779 | 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, North-Holland | Place of Publication: | Netherlands | ISSN: | 1872-6771 0166-218X |
Fields of Research (FoR) 2008: | 010303 Optimisation 010206 Operations Research |
Fields of Research (FoR) 2020: | 490304 Optimisation 490108 Operations research |
Socio-Economic Objective (SEO) 2008: | 970101 Expanding Knowledge in the Mathematical Sciences | Socio-Economic Objective (SEO) 2020: | 280118 Expanding knowledge in the mathematical sciences | 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:
File | Size | Format |
---|
Items in Research UNE are protected by copyright, with all rights reserved, unless otherwise indicated.