Please use this identifier to cite or link to this item:
https://hdl.handle.net/1959.11/26782
Title: | Scheduling network maintenance jobs with release dates and deadlines to maximize total flow over time: Boundsand solution strategies | Contributor(s): | Boland, Natashia (author); Kalinowski, Thomas (author) ; Kaur, Simranjit (author) | Publication Date: | 2015-12 | Early Online Version: | 2015-06-06 | DOI: | 10.1016/j.cor.2015.05.011 | Handle Link: | https://hdl.handle.net/1959.11/26782 | Abstract: | We consider a problem that marries network flows and scheduling, motivated by the need to schedule maintenance activities in infrastructure networks, such as rail or general logistics networks. Network elements must undergo regular preventive maintenance, shutting down the arc for the duration of the activity. Careful coordination of these arc maintenance jobs can dramatically reduce the impact of such shutdown jobs on the flow carried by the network. Scheduling such jobs between given release dates and deadlines so as to maximize the total flow over time presents an intriguing case to study the role of time discretization. Here we prove that if the problem data is integer, and no flow can be stored at nodes, we can restrict attention to integer job start times. However if flow can be stored, fractional start times may be needed. This makes traditional strong integer programming scheduling models difficult to apply. Here we formulate an exact integer programming model for the continuous time problem, as well as integer programming models based on time discretization that can provide dual bounds, and that can – with minor modifications – also yield primal bounds. The resulting bounds are demonstrated to have small gaps on test instances, and offer a good trade-off for bound quality against computing time. | Publication Type: | Journal Article | Grant Details: | ARC/LP110200524 | Source of Publication: | Computers & Operations Research, v.64, p. 113-129 | Publisher: | Pergamon Press | Place of Publication: | United Kingdom | ISSN: | 1873-765X 0305-0548 |
Fields of Research (FoR) 2008: | 010303 Optimisation | Fields of Research (FoR) 2020: | 490304 Optimisation | 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 |
---|---|
Appears in Collections: | Journal Article School of Science and Technology |
Files in This Item:
File | Description | Size | Format |
---|
SCOPUSTM
Citations
9
checked on Apr 6, 2024
Page view(s)
1,312
checked on Mar 8, 2023
Download(s)
4
checked on Mar 8, 2023
Items in Research UNE are protected by copyright, with all rights reserved, unless otherwise indicated.