Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Approximation Algorithms for k-Connected Graph Factors Read chapter Read first chapter

2015 | OriginalPaper | Chapter

Scheduling Parallel Jobs Online with Convex and Concave Parallelizability

Authors : Roozbeh Ebrahimi, Samuel McCauley, Benjamin Moseley

Published in: Approximation and Online Algorithms

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Online scheduling of parallelizable jobs has received a significant amount of attention recently. Scalable algorithms are known—that is, algorithms that are (1+\(\varepsilon \))-speed O(1)-competitive for any fixed \(\varepsilon >0\). Previous research has focused on the case where each job’s parallelizability can be expressed as a concave speedup curve. However, there are cases where a job’s speedup curve can be convex. Considering convex speedup curves has received attention in the offline setting, but, to date, there are no positive results in the online model. In this work, we consider scheduling jobs with convex or concave speedup curves for the first time in the online setting. We give a new algorithm that is (1+\(\varepsilon \))-speed O(1)-competitive. There are strong lower bounds on the competitive ratio if the algorithm is not given resource augmentation over the adversary, and thus this is essentially the best positive result one can show for this setting.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter On the Smoothness of Paging Algorithms
next chapter Scheduling with State-Dependent Machine Speed
Footnotes
1
Specifically, [17] gives an \(\varOmega (\log n/m)\) lower bound.
 
Literature
1.
Bansal, N., Krishnaswamy, R., Nagarajan, V.: Better scalable algorithms for broadcast scheduling. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6198, pp. 324–335. Springer, Heidelberg (2010)CrossRef
2.
Beaumont, O., Guermouche, A.: Task scheduling for parallel multifrontal methods. In: Kermarrec, A.-M., Bougé, L., Priol, T. (eds.) Euro-Par 2007. LNCS, vol. 4641, pp. 758–766. Springer, Heidelberg (2007)CrossRef
3.
Blazewicz, J., Kovalyov, M.Y., Machowiak, M., Trystram, D., Weglarz, J.: Preemptable malleable task scheduling problem. IEEE Trans. Comput. 55(4), 486–490 (2006)CrossRef
4.
Blazewicz, J., Machowiak, M., Weglarz, J., Kovalyov, M.Y., Trystram, D.: Scheduling malleable tasks on parallel processors to minimize the makespan. Ann. Oper. Res. 129(1–4), 65–80 (2004)MathSciNetCrossRefMATH
5.
Chadha, J.S., Garg, N., Kumar, A., Muralidhara, V.N.: A competitive algorithm for minimizing weighted flow time on unrelated machines with speed augmentation. In: Proceedings of the 41st Symposium on Theory of Computation (STOC) (2009)
6.
Chan, S.H., Lam, T.W., Lee, L.K., Zhu, J.: Nonclairvoyant sleep management and flow-time scheduling on multiple processors. In: Proceedings of the 25th Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 261–270 (2013)
7.
8.
Edmonds, J., Im, S., Moseley, B.: Online scalable scheduling for the \(\ell _k\)-norms of flow time without conservation of work. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2011)
9.
Edmonds, J., Pruhs, K.: Scalably scheduling processes with arbitrary speedup curves. ACM Trans. Algorithms 8(3), 28:1–28:10 (2012)MathSciNetCrossRef
10.
Fox, K., Im, S., Moseley, B.: Energy efficient scheduling of parallelizable jobs. In: Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 948–957 (2013)
11.
Fox, K., Moseley, B.: Online scheduling on identical machines using SRPT. In: Proceedings of the 22nd ACM Symposium on Discrete Algorithms (SODA) (2011)
12.
Gupta, A., Im, S., Krishnaswamy, R., Moseley, B., Pruhs, K.: Scheduling jobs with varying parallelizability to reduce variance. In: Proceedings of the Twenty-Second Syposium on Parallel Algorithms and Architectures (SPAA), pp. 11–20 (2010)
13.
Im, S., Moseley, B.: Online scalable algorithm for minimizing \(\ell _k\)-norms of weighted flow time on unrelated machines. In: Proceedings of the Twenty-Second Annual ACM Symposium on Discrete Algorithms (SODA), pp. 95–108 (2011)
14.
Im, S., Moseley, B., Pruhs, K.: A tutorial on amortized local competitiveness in online scheduling. SIGACT News 42, 83–97 (2011)CrossRef
15.
Im, S., Moseley, B., Pruhs, K., Torng, E.: Competitively scheduling tasks with intermediate parallelizability. In: Proceedings of the Twenty-Sixth ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 22–29 (2014)
16.
17.
18.
Ludwig, W., Tiwari, P.: Scheduling malleable and nonmalleable parallel tasks. In: Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 167–176 (1994)
19.
Prasanna, G.N.S., Musicus, B.R.: Generalized multiprocessor scheduling and applications to matrix computations. IEEE Trans. Parallel Distrib. Syst. 7(6), 650–664 (1996)CrossRef
20.
Pruhs, K., Sgall, J., Torng, E.: Handbook of Scheduling: Algorithms, Models, and Performance Analysis. CRC Press, Boca Raton (2004). Online Scheduling
Metadata
Title
Scheduling Parallel Jobs Online with Convex and Concave Parallelizability
Authors
Roozbeh Ebrahimi
Samuel McCauley
Benjamin Moseley
Copyright Year
2015
Book
Approximation and Online Algorithms

Print ISBN: 978-3-319-28683-9

Electronic ISBN: 978-3-319-28684-6

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-28684-6_16

Premium Partner

    Image Credits