nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

Scheduling Maintenance Jobs in Networks

verfasst von : Fidaa Abed, Lin Chen, Yann Disser, Martin Groß, Nicole Megow, Julie Meißner, Alexander T. Richter, Roman Rischke

Erschienen in: Algorithms and Complexity

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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, 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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel New Algorithmic Results for Bin Packing and Scheduling

Nächstes Kapitel Paths to Trees and Cacti

Bley, A., Karch, D., D’Andreagiovanni, F.: WDM fiber replacement scheduling. Electron. Notes Discret. Math. 41, 189–196 (2013). http://www.sciencedirect.com/science/article/pii/S1571065313000954 CrossRef

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. 32(3), 885–905 (2016)MathSciNetCrossRefMATH

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). http://www.sciencedirect.com/science/article/pii/S0305054815001288 MathSciNetCrossRefMATH

Boland, N., Kalinowski, T., Waterer, H., Zheng, L.: Scheduling arc maintenance jobs in a network to maximize total flow over time. Discret. Appl. Math. 163, 34–52 (2014). http://dx.doi.org/10.1016/j.dam.2012.05.027 MathSciNetCrossRefMATH

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). doi:10.1007/978-0-85729-778-5_10 CrossRef

Canetti, R., Irani, S.: Bounding the power of preemption in randomized scheduling. SIAM J. Comput. 27(4), 993–1015 (1998). http://dx.doi.org/10.1137/S0097539795283292 MathSciNetCrossRefMATH

Chang, J., Khuller, S., Mukherjee, K.: LP rounding and combinatorial algorithms for minimizing active and busy time. In: Blelloch, G.E., Sanders, P. (eds.) Proceedings of the 26th SPAA, pp. 118–127. ACM, New York (2014). http://doi.acm.org/10.1145/2612669.2612689

Chang, J., Khuller, S., Mukherjee, K.: Active and busy time minimization. In: Proceedings of the 12th MAPSP, pp. 247–249 (2015). http://feb.kuleuven.be/mapsp.2015/Proceedings%20MAPSP%202015.pdf

Cohen-Addad, V., Li, Z., Mathieu, C., Milis, I.: Energy-efficient algorithms for non-preemptive speed-scaling. In: Bampis, E., Svensson, O. (eds.) WAOA 2014. LNCS, vol. 8952, pp. 107–118. Springer, Cham (2015). doi:10.1007/978-3-319-18263-6_10

10.

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). http://dx.doi.org/10.1287/moor.1110.0520 MathSciNetCrossRefMATH

11.

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. Theor. Comput. Sci. 411(40–42), 3553–3562 (2010). http://www.sciencedirect.com/science/article/pii/S0304397510002926 MathSciNetCrossRefMATH

12.

Ha, S.: Compile-time scheduling of dataflow program graphs with dynamic constructs. Ph.D. thesis, University of California, Berkeley (1992). http://www.eecs.berkeley.edu/Pubs/TechRpts/1992/ERL-92-43.pdf

13.

Kalinowski, T., Matsypura, D., Savelsbergh, M.W.: Incremental network design with maximum flows. Eur. J. Oper. Res. 242(1), 51–62 (2015). http://www.sciencedirect.com/science/article/pii/S0377221714008078 MathSciNetCrossRefMATH

14.

Khandekar, R., Schieber, B., Shachnai, H., Tamir, T.: Real-time scheduling to minimize machine busy times. J. Sched. 18(6), 561–573 (2015). http://dx.doi.org/10.1007/s10951-014-0411-z MathSciNetCrossRefMATH

15.

Mertzios, G.B., Shalom, M., Voloshin, A., Wong, P.W.H., Zaks, S.: Optimizing busy time on parallel machines. In: Proceedings of the 26th IPDPS, pp. 238–248. IEEE (2012). http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6267839

16.

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. Eur. J. Oper. Res. 223(3), 794–806 (2012). http://www.sciencedirect.com/science/article/pii/S0377221712005310 MathSciNetCrossRefMATH

17.

Parsons, E.W., Sevcik, K.C.: Multiprocessor scheduling for high-variability service time distributions. In: Feitelson, D.G., Rudolph, L. (eds.) JSSPP 1995. LNCS, vol. 949, pp. 127–145. Springer, Heidelberg (1995). doi:10.1007/3-540-60153-8_26 CrossRef

18.

Schulz, A.S., Skutella, M.: Scheduling unrelated machines by randomized rounding. SIAM J. Discret. Math. 15(4), 450–469 (2002). http://dx.doi.org/10.1137/S0895480199357078 MathSciNetCrossRefMATH

19.

Soper, A.J., Strusevich, V.A.: Power of preemption on uniform parallel machines. In: Proceedings of the 17th APPROX. LIPIcs, vol. 28, pp. 392–402. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2014). http://drops.dagstuhl.de/opus/volltexte/2014/4711

Titel: Scheduling Maintenance Jobs in Networks
verfasst von: Fidaa Abed
Lin Chen
Yann Disser
Martin Groß
Nicole Megow
Julie Meißner
Alexander T. Richter
Roman Rischke
Verlag: Springer International Publishing
Buch: Algorithms and Complexity
Print ISBN: 978-3-319-57585-8

Electronic ISBN: 978-3-319-57586-5

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-57586-5_3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner