On Speed Scaling Scheduling of Parallel Jobs with Preemption

详细信息    查看全文

• 关键词：Speed scaling ; Scheduling ; Parallel jobs ; NP ; hardness ; Approximation algorithm
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9869
• 期：1
• 页码：309-321
• 全文大小：216 KB
• 参考文献：1.Albers, S., Antoniadis, A., Greiner, G.: On multi-processor speed scaling with migration: extended abstract. In: 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2011), pp. 279–288. ACM (2011)
  2.Albers, S., Müller, F., Schmelzer, S.: Speed scaling on parallel processors. In: 19th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2007), pp. 289–298. ACM (2007)
  3.Angel, E., Bampis, E., Kacem, F., Letsios, D.: Speed scaling on parallel processors with migration. In: Kaklamanis, C., Papatheodorou, T., Spirakis, P.G. (eds.) Euro-Par 2012. LNCS, vol. 7484, pp. 128–140. Springer, Heidelberg (2012)CrossRef
  4.Bampis, E., Kononov, A., Letsios, D., Lucarelli, G., Sviridenko, M.: Energy efficient scheduling and routing via randomized rounding. In: FSTTCS, pp. 449–460 (2013)
  5.Bingham, B.D., Greenstreet, M.R.: Energy optimal scheduling on multiprocessors with migration. In: International Symposium on Parallel and Distributed Processing with Applications (ISPA 2008), pp. 153–161. IEEE (2008)
  6.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, Heidelberg (2015)
  7.Drozdowski, M.: On complexity of multiprocessor tasks scheduling. Bull. Pol. Acad. Sci. Tech. Sci. 43(3), 381–392 (1995)MATH
  8.Drozdowski, M.: Scheduling for Parallel Processing, p. 386. Springer, London (2009)
  9.Gerards, M.E.T., Hurink, J.L., Hölzenspies, P.K.F.: A survey of offline algorithms for energy minimization under deadline constraints. J. Sched. 19, 3–19 (2016)MathSciNet CrossRef MATH
  10.Greiner, G., Nonner, T., Souza, A.: The bell is ringing in speed-scaled multiprocessor scheduling. In: 21st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2009), pp. 11–18. ACM (2009)
  11.Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimizations, 2nd, p. 362. Springer, Heidelberg (1993)
  12.Jansen, K., Porkolab, L.: Preemptive parallel task scheduling in O(n)+poly(m) time. In: Lee, D.T., Teng, S.-H. (eds.) ISAAC 2000. LNCS, vol. 1969, pp. 398–409. Springer, Heidelberg (2000)CrossRef
  13.Jansen, K., Porkolab, L.: Preemptive scheduling with dedicated processors: applications of fractional graph coloring. J. Sched. 7, 35–48 (2004)MathSciNet CrossRef MATH
  14.Yao, F., Demers, A., Shenker, S.: A scheduling model for reduced CPU energy. In: 36th Annual Symposium on Foundation of Computer Science (FOCS 1995), pp. 374–382 (1995)
  
• 作者单位：Alexander Kononov (18)
  Yulia Kovalenko (18)
  
  18. Sobolev Institute of Mathematics, 4, Akad. Koptyug Avenue, 630090, Novosibirsk, Russia
  
• 丛书名：Discrete Optimization and Operations Research
• ISBN：978-3-319-44914-2
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9869

文摘

Parallel jobs require more than one processor at the same time. We study speed scaling scheduling of parallel jobs with preemption. We propose “almost-exact” algorithms for problems with rigid jobs and single mode two-processor jobs. Based on configuration linear programs, our algorithms obtain an \(OPT + \varepsilon \) solution for any fixed \(\varepsilon > 0\).