nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Active and Busy Time Scheduling Problem: A Survey

verfasst von : Vincent Chau, Minming Li

Erschienen in: Complexity and Approximation

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 present an overview of recent research on the busy time and active time scheduling model, which has its applications in energy efficient scheduling for cloud computing systems, optical network design and computer memories. The major feature of this type of scheduling problems is to aggregate job execution into as few time slots as possible to save energy. The difference between busy time and active time is that the former refers to multiple machines while the latter refers to a single machine. After summarizing the previous results on this topic, we propose a few potential future directions for each model.

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 Core Decomposition, Maintenance and Applications

Nächstes Kapitel A Note on the Position Value for Hypergraph Communication Situations

Alicherry, M., Bhatia, R.: Line system design and a generalized coloring problem. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol. 2832, pp. 19–30. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-39658-1_5CrossRef

Amur, H., Cipar, J., Gupta, V., Ganger, G.R., Kozuch, M.A., Schwan, K.: Robust and flexible power-proportional storage. In: Proceedings of the 1st ACM Symposium on Cloud Computing, pp. 217–228. ACM (2010)

Bampis, E.: Algorithmic issues in energy-efficient computation. In: Kochetov, Y., Khachay, M., Beresnev, V., Nurminski, E., Pardalos, P. (eds.) DOOR 2016. LNCS, vol. 9869, pp. 3–14. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-44914-2_1CrossRef

Baptiste, P.: Scheduling unit tasks to minimize the number of idle periods: a polynomial time algorithm for offline dynamic power management. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, pp. 364–367. Society for Industrial and Applied Mathematics (2006)

Chang, J., Gabow, H.N., Khuller, S.: A model for minimizing active processor time. Algorithmica 70(3), 368–405 (2014). https://doi.org/10.1007/s00453-013-9807-yMathSciNetCrossRefMATH

Chang, J., Khuller, S., Mukherjee, K.: Lp rounding and combinatorial algorithms for minimizing active and busy time. J. Sched. 20(6), 657–680 (2017)MathSciNetCrossRef

Chen, S., Ljubić, I., Raghavan, S.: The regenerator location problem. Netw.: Int. J. 55(3), 205–220 (2010)MathSciNetMATH

Flammini, M., Marchetti-Spaccamela, A., Monaco, G., Moscardelli, L., Zaks, S.: On the complexity of the regenerator placement problem in optical networks. IEEE/ACM Trans. Netw. (TON) 19(2), 498–511 (2011)CrossRef

Flammini, M., et al.: Minimizing total busy time in parallel scheduling with application to optical networks. Theor. Comput. Sci. 411(40–42), 3553–3562 (2010)MathSciNetCrossRef

10.

Fong, K.C.K., Li, M., Li, Y., Poon, S.-H., Wu, W., Zhao, Y.: Scheduling tasks to minimize active time on a processor with unlimited capacity. In: Gopal, T.V., Jäger, G., Steila, S. (eds.) TAMC 2017. LNCS, vol. 10185, pp. 247–259. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-55911-7_18CrossRef

11.

Gerards, M.E., Hurink, J.L., Hölzenspies, P.K.: A survey of offline algorithms for energy minimization under deadline constraints. J. sched. 19(1), 3–19 (2016)MathSciNetCrossRef

12.

Irani, S., Pruhs, K.R.: Algorithmic problems in power management. ACM Sigact News 36(2), 63–76 (2005)CrossRef

13.

Khandekar, R., Schieber, B., Shachnai, H., Tamir, T.: Minimizing busy time in multiple machine real-time scheduling. In: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2010)

14.

Koehler, F., Khuller, S.: Optimal batch schedules for parallel machines. In: Dehne, F., Solis-Oba, R., Sack, J.-R. (eds.) WADS 2013. LNCS, vol. 8037, pp. 475–486. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40104-6_41CrossRef

15.

Koehler, F., Khuller, S.: Busy Time scheduling on a bounded number of machines (Extended Abstract). Algorithms and Data Structures. LNCS, vol. 10389, pp. 521–532. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-62127-2_44CrossRef

16.

Kumar, S., Khuller, S.: Brief announcement: a greedy 2 approximation for the active time problem. In: SPAA, pp. 347–349 (2018)

17.

Kumar, V., Rudra, A.: Approximation algorithms for wavelength assignment. In: Sarukkai, S., Sen, S. (eds.) FSTTCS 2005. LNCS, vol. 3821, pp. 152–163. Springer, Heidelberg (2005). https://doi.org/10.1007/11590156_12CrossRef

18.

Mertzios, G.B., Shalom, M., Voloshin, A., Wong, P.W., Zaks, S.: Optimizing busy time on parallel machines. Theor. Comput. Sci. 562, 524–541 (2015)MathSciNetCrossRef

19.

Oprescu, A.M., Kielmann, T.: Bag-of-tasks scheduling under budget constraints. In: 2010 IEEE Second International Conference on Cloud Computing Technology and Science, pp. 351–359. IEEE (2010)

20.

Ren, R., Tang, X.: Online flexible job scheduling for minimum span. In: Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 55–66. ACM (2017)

21.

Saradhi, C.V., et al.: A framework for regenerator site selection based on multiple paths. In: 2010 Conference on Optical Fiber Communication (OFC/NFOEC), Collocated National Fiber Optic Engineers Conference, pp. 1–3. IEEE (2010)

22.

Shalom, M., Voloshin, A., Wong, P.W., Yung, F.C., Zaks, S.: Online optimization of busy time on parallel machines. Theor. Comput. Sci. 560, 190–206 (2014)MathSciNetCrossRef

23.

Shi, W., Hong, B.: Resource allocation with a budget constraint for computing independent tasks in the cloud. In: 2010 IEEE Second International Conference on Cloud Computing Technology and Science, pp. 327–334. IEEE (2010)

24.

Winkler, P., Zhang, L.: Wavelength assignment and generalized interval graph coloring. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 830–831. Society for Industrial and Applied Mathematics (2003)

Titel: Active and Busy Time Scheduling Problem: A Survey
verfasst von: Vincent Chau
Minming Li
Verlag: Springer International Publishing
Buch: Complexity and Approximation
Print ISBN: 978-3-030-41671-3

Electronic ISBN: 978-3-030-41672-0

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-41672-0_13

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"