×

Scheduling maintenance jobs in networks. (English) Zbl 1407.68539

Summary: 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, that is, the maximum ratio of the values of non-preemptive and preemptive optimal solutions.
Interestingly, the preemptive and the non-preemptive problem can be solved efficiently on paths, whereas we show that mixing both leads to a weakly NP-hard problem that allows for a simple 2-approximation.

MSC:

68W25 Approximation algorithms
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
90B25 Reliability, availability, maintenance, inspection in operations research
90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] 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, J. Comb. Optim., 1-21, (2015)
[2] Boland, N.; Kalinowski, T.; Waterer, H.; Zheng, L., Scheduling arc maintenance jobs in a network to maximize total flow over time, Discrete Appl. Math., 163, 34-52, (2014) · Zbl 1297.90031
[3] Nurre, S. G.; Cavdaroglu, B.; Mitchell, J. E.; Sharkey, T. C.; Wallace, W. A., Restoring infrastructure systems: an integrated network design and scheduling (INDS) problem, European J. Oper. Res., 223, 3, 794-806, (2012) · Zbl 1292.90189
[4] Bley, A.; Karch, D.; D’Andreagiovanni, F., WDM fiber replacement scheduling, Electron. Notes Discrete Math., 41, 189-196, (2013)
[5] Flammini, M.; Monaco, G.; Moscardelli, L.; Shachnai, H.; Shalom, M.; Tamir, T.; Zaks, S., Minimizing total busy time in parallel scheduling with application to optical networks, Theoret. Comput. Sci., 411, 40-42, 3553-3562, (2010) · Zbl 1207.68110
[6] Chang, J.; Khuller, S.; Mukherjee, K., Active and busy time minimization, (Proc. of the 12th MAPSP, (2015)), 247-249
[7] Chang, J.; Khuller, S.; Mukherjee, K., LP rounding and combinatorial algorithms for minimizing active and busy time, (Blelloch, G. E.; Sanders, P., Proc. of the 26th SPAA, (2014), ACM: ACM New York), 118-127
[8] Canetti, R.; Irani, S., Bounding the power of preemption in randomized scheduling, SIAM J. Comput., 27, 4, 993-1015, (1998) · Zbl 0907.68007
[9] Correa, J. R.; Skutella, M.; Verschae, J., The power of preemption on unrelated machines and applications to scheduling orders, Math. Oper. Res., 37, 2, 379-398, (2012) · Zbl 1238.90062
[10] Schulz, A. S.; Skutella, M., Scheduling unrelated machines by randomized rounding, SIAM J. Discrete Math., 15, 4, 450-469, (2002) · Zbl 1055.90040
[11] Soper, A. J.; Strusevich, V. A., Power of preemption on uniform parallel machines, (Proc. of the 17th APPROX. Proc. of the 17th APPROX, LIPIcs. Leibniz Int. Proc. Inform., vol. 28, (2014), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik: Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik Dagstuhl, Germany), 392-402 · Zbl 1360.90133
[12] Cohen-Addad, V.; Li, Z.; Mathieu, C.; Milis, I., Energy-efficient algorithms for non-preemptive speed-scaling, (Bampis, E.; Svensson, O., Proc. of the 12th WAOA. Proc. of the 12th WAOA, Lecture Notes in Comput. Sci., vol. 8952, (2015), Springer International Publishing), 107-118 · Zbl 1457.68025
[13] Parsons, E. W.; Sevcik, K. C., Multiprocessor scheduling for high-variability service time distributions, (Feitelson, D. G.; Rudolph, L., Proc. of the JSSPP. Proc. of the JSSPP, Lecture Notes in Comput. Sci., vol. 949, (1995), Springer Berlin Heidelberg), 127-145
[14] Ha, S., Compile-Time Scheduling of Dataflow Program Graphs with Dynamic Constructs, (1992), University of California: University of California Berkeley, Ph.D. thesis
[15] Khandekar, R.; Schieber, B.; Shachnai, H.; Tamir, T., Real-time scheduling to minimize machine busy times, J. Sched., 18, 6, 561-573, (2015) · Zbl 1333.90046
[16] 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, Comput. Oper. Res., 64, 113-129, (2015) · Zbl 1349.90319
[17] Boland, N. L.; Savelsbergh, M. W.P., Optimizing the hunter valley coal chain, (Gurnani, H.; Mehrotra, A.; Ray, S., Supply Chain Disruptions: Theory and Practice of Managing Risk, (2012), Springer: Springer London), 275-302
[18] Kalinowski, T.; Matsypura, D.; Savelsbergh, M. W., Incremental network design with maximum flows, European J. Oper. Res., 242, 1, 51-62, (2015) · Zbl 1341.90024
[19] Mertzios, G. B.; Shalom, M.; Voloshin, A.; Wong, P. W.H.; Zaks, S., Optimizing busy time on parallel machines, (Proc. of the 26th IPDPS, (2012), IEEE), 238-248
[20] Korte, B.; Vygen, J., Combinatorial Optimization: Theory and Algorithms, (2007), Springer Publishing Company, Incorporated
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.