publication . Preprint . Article . Other literature type . Part of book or chapter of book . 2017

Scheduling Maintenance Jobs in Networks

Fidaa Abed; Lin Chen; Yann Disser; Martin Groß; Nicole Megow; Julie Meißner; Alexander T. Richter; Roman Rischke;
Open Access English
  • Published: 30 Jan 2017
Abstract
We investigate the problem of scheduling the maintenance of edges in a network, motivated by the goal of minimizing outages in transportation or telecommunication networks. We focus on maintaining connectivity between two nodes over time; for the special case of path networks, this is related to the problem of minimizing the busy time of machines. We show that the problem can be solved in polynomial time in arbitrary networks if preemption is allowed. If preemption is restricted to integral time points, the problem is NP-hard and in the non-preemptive case we give strong non-approximability results. Furthermore, we give tight bounds on the power of preemption, t...
Subjects
arXiv: Computer Science::Operating SystemsComputer Science::Data Structures and Algorithms
free text keywords: Computer Science - Data Structures and Algorithms, 68, F.2.2, Theoretical Computer Science, General Computer Science, Busy time, Time complexity, Scheduling (computing), Preemption, Special case, Mathematical optimization, Computer science, Approximation algorithm, Distributed computing, Mathematics

1. Bley, A., Karch, D., D'Andreagiovanni, F.: WDM fiber replacement scheduling. Electronic Notes in Discrete Mathematics 41, 189-196 (2013), http://www.sciencedirect.com/science/article/pii/S1571065313000954 [OpenAIRE]

2. Boland, N., Kalinowski, T., Kaur, S.: Scheduling arc shut downs in a network to maximize flow over time with a bounded number of jobs per time period. Journal of Combinatorial Optimization pp. 1-21 (2015), http://dx.doi.org/10.1007/s10878-015-9910-x

3. Boland, N., Kalinowski, T., Kaur, S.: Scheduling network maintenance jobs with release dates and deadlines to maximize total flow over time: Bounds and solution strategies. Computers & Operations Research 64, 113-129 (2015), http://www.sciencedirect.com/science/article/pii/S0305054815001288

4. Boland, N., Kalinowski, T., Waterer, H., Zheng, L.: Scheduling arc maintenance jobs in a network to maximize total flow over time. Discrete Applied Mathematics 163, 34-52 (2014), http://dx.doi.org/10.1016/j.dam.2012.05.027

5. Boland, N.L., Savelsbergh, M.W.P.: Optimizing the hunter valley coal chain. In: Gurnani, H., Mehrotra, A., Ray, S. (eds.) Supply Chain Disruptions: Theory and Practice of Managing Risk. pp. 275-302. Springer, London (2012), http://dx.doi.org/10.1007/978-0-85729-778-5_10

6. Canetti, R., Irani, S.: Bounding the power of preemption in randomized scheduling. SIAM Journal on Computing 27(4), 993-1015 (1998), http://dx.doi.org/10.1137/S0097539795283292

Abstract
We investigate the problem of scheduling the maintenance of edges in a network, motivated by the goal of minimizing outages in transportation or telecommunication networks. We focus on maintaining connectivity between two nodes over time; for the special case of path networks, this is related to the problem of minimizing the busy time of machines. We show that the problem can be solved in polynomial time in arbitrary networks if preemption is allowed. If preemption is restricted to integral time points, the problem is NP-hard and in the non-preemptive case we give strong non-approximability results. Furthermore, we give tight bounds on the power of preemption, t...
Subjects
arXiv: Computer Science::Operating SystemsComputer Science::Data Structures and Algorithms
free text keywords: Computer Science - Data Structures and Algorithms, 68, F.2.2, Theoretical Computer Science, General Computer Science, Busy time, Time complexity, Scheduling (computing), Preemption, Special case, Mathematical optimization, Computer science, Approximation algorithm, Distributed computing, Mathematics

1. Bley, A., Karch, D., D'Andreagiovanni, F.: WDM fiber replacement scheduling. Electronic Notes in Discrete Mathematics 41, 189-196 (2013), http://www.sciencedirect.com/science/article/pii/S1571065313000954 [OpenAIRE]

2. Boland, N., Kalinowski, T., Kaur, S.: Scheduling arc shut downs in a network to maximize flow over time with a bounded number of jobs per time period. Journal of Combinatorial Optimization pp. 1-21 (2015), http://dx.doi.org/10.1007/s10878-015-9910-x

3. Boland, N., Kalinowski, T., Kaur, S.: Scheduling network maintenance jobs with release dates and deadlines to maximize total flow over time: Bounds and solution strategies. Computers & Operations Research 64, 113-129 (2015), http://www.sciencedirect.com/science/article/pii/S0305054815001288

4. Boland, N., Kalinowski, T., Waterer, H., Zheng, L.: Scheduling arc maintenance jobs in a network to maximize total flow over time. Discrete Applied Mathematics 163, 34-52 (2014), http://dx.doi.org/10.1016/j.dam.2012.05.027

5. Boland, N.L., Savelsbergh, M.W.P.: Optimizing the hunter valley coal chain. In: Gurnani, H., Mehrotra, A., Ray, S. (eds.) Supply Chain Disruptions: Theory and Practice of Managing Risk. pp. 275-302. Springer, London (2012), http://dx.doi.org/10.1007/978-0-85729-778-5_10

6. Canetti, R., Irani, S.: Bounding the power of preemption in randomized scheduling. SIAM Journal on Computing 27(4), 993-1015 (1998), http://dx.doi.org/10.1137/S0097539795283292

Any information missing or wrong?Report an Issue