Document Open Access Logo

Malleable Scheduling Beyond Identical Machines

Authors Dimitris Fotakis , Jannik Matuschke , Orestis Papadigenopoulos

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2019.17.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Author Details

Dimitris Fotakis
  • School of Electrical and Computer Engineering, National Technical University of Athens, Greece
Jannik Matuschke
  • Research Center for Operations Management, KU Leuven, Belgium
Orestis Papadigenopoulos
  • Department of Computer Science, The University of Texas at Austin, USA

Acknowledgements

Part of this work was carried out while the authors participated in the program "Real-Time Decision Making" at the Simons Institute for the Theory of Computing, Berkeley, CA.

Cite As Get BibTex

Dimitris Fotakis, Jannik Matuschke, and Orestis Papadigenopoulos. Malleable Scheduling Beyond Identical Machines. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.17

Abstract

In malleable job scheduling, jobs can be executed simultaneously on multiple machines with the processing time depending on the number of allocated machines. Jobs are required to be executed non-preemptively and in unison, in the sense that they occupy, during their execution, the same time interval over all the machines of the allocated set. In this work, we study generalizations of malleable job scheduling inspired by standard scheduling on unrelated machines. Specifically, we introduce a general model of malleable job scheduling, where each machine has a (possibly different) speed for each job, and the processing time of a job j on a set of allocated machines S depends on the total speed of S for j. For machines with unrelated speeds, we show that the optimal makespan cannot be approximated within a factor less than e/(e-1), unless P = NP. On the positive side, we present polynomial-time algorithms with approximation ratios 2e/(e-1) for machines with unrelated speeds, 3 for machines with uniform speeds, and 7/3 for restricted assignments on identical machines. Our algorithms are based on deterministic LP rounding and result in sparse schedules, in the sense that each machine shares at most one job with other machines. We also prove lower bounds on the integrality gap of 1+phi for unrelated speeds (phi is the golden ratio) and 2 for uniform speeds and restricted assignments. To indicate the generality of our approach, we show that it also yields constant factor approximation algorithms (i) for minimizing the sum of weighted completion times; and (ii) a variant where we determine the effective speed of a set of allocated machines based on the L_p norm of their speeds.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Scheduling algorithms
Keywords
  • malleable
  • jobs
  • moldable
  • machines
  • unrelated
  • uniform
  • parallel
  • speeds
  • approximation
  • scheduling

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. G. M. Amdahl. Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities. IEEE Solid-State Circuits Society Newsletter, 12(3):19-20, Summer 2007. Google Scholar
  2. J. Blazewicz, M. Y. Kovalyov, M. Machowiak, D. Trystram, and J. Weglarz. Preemptable Malleable Task Scheduling Problem. IEEE Trans. Comput., 55(4):486-490, April 2006. Google Scholar
  3. R. P. Brent. The Parallel Evaluation of General Arithmetic Expressions. J. ACM, 21(2):201-206, April 1974. Google Scholar
  4. J. Correa, A. Marchetti-Spaccamela, J. Matuschke, L. Stougie, O. Svensson, V. Verdugo, and J. Verschae. Strong LP formulations for scheduling splittable jobs on unrelated machines. Mathematical Programming, 154(1-2):305-328, 2015. Google Scholar
  5. J. Du and J. Leung. Complexity of Scheduling Parallel Task Systems. SIAM Journal on Discrete Mathematics, 2(4):473-487, 1989. Google Scholar
  6. P. Dutot, G. Mounié, and D. Trystram. Scheduling Parallel Tasks: Approximation Algorithms. In Joseph T. Leung, editor, Handbook of Scheduling: Algorithms, Models, and Performance Analysis, chapter 26, pages 26-1-26-24. CRC Press, 2004. Google Scholar
  7. M. Garey and R. Graham. Bounds for Multiprocessor Scheduling with Resource Constraints. SIAM Journal on Computing, 4(2):187-200, 1975. Google Scholar
  8. R. Graham. Bounds on Multiprocessing Timing Anomalies. SIAM Journal on Applied Mathematics, 17(2):416-429, 1969. Google Scholar
  9. L. A. Hall, A. S. Schulz, D. B. Shmoys, and J. Wein. Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms. Math. Oper. Res., 22(3):513-544, August 1997. Google Scholar
  10. C. Hanen and A. Munier. An approximation algorithm for scheduling dependent tasks on m processors with small communication delays. Discrete Applied Mathematics, 108(3):239-257, 2001. Google Scholar
  11. D. S. Hochbaum and D. B. Shmoys. Using dual approximation algorithms for scheduling problems: Theoretical and practical results. In 26th Annual Symposium on Foundations of Computer Science, FOCS '85, pages 79-89, October 1985. Google Scholar
  12. K. Jansen and F. Land. Scheduling Monotone Moldable Jobs in Linear Time. In 2018 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2018, Vancouver, BC, Canada, May 21-25, 2018, pages 172-181, 2018. Google Scholar
  13. K. Jansen and L. Porkolab. Linear-Time Approximation Schemes for Scheduling Malleable Parallel Tasks. Algorithmica, 32(3):507-520, March 2002. Google Scholar
  14. K. Jansen and H. Zhang. An Approximation Algorithm for Scheduling Malleable Tasks Under General Precedence Constraints. ACM Trans. Algorithms, 2(3):416-434, July 2006. Google Scholar
  15. Klaus Jansen and Ralf Thöle. Approximation algorithms for scheduling parallel jobs. SIAM Journal on Computing, 39(8):3571-3615, 2010. Google Scholar
  16. J. K. Lenstra, D. B. Shmoys, and É. Tardos. Approximation algorithms for scheduling unrelated parallel machines. Mathematical Programming, 46(1):259-271, January 1990. Google Scholar
  17. Konstantin Makarychev and Debmalya Panigrahi. Precedence-Constrained Scheduling of Malleable Jobs with Preemption. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, pages 823-834, 2014. Google Scholar
  18. G. Mounié, C. Rapine, and D. Trystram. Efficient Approximation Algorithms for Scheduling Malleable Tasks. In Proceedings of the Eleventh Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA '99, Saint-Malo, France, June 27-30, 1999, pages 23-32, 1999. Google Scholar
  19. G. Mounié, C. Rapine, and D. Trystram. A 3/2-Approximation Algorithm for Scheduling Independent Monotonic Malleable Tasks. SIAM J. Comput., 37(2):401-412, 2007. Google Scholar
  20. C. H. Papadimitriou and M. Yannakakis. Towards an Architecture-independent Analysis of Parallel Algorithms. SIAM J. Comput., 19(2):322-328, April 1990. Google Scholar
  21. D. A. Patterson and J. L. Hennessy. Computer Organization and Design, Fifth Edition: The Hardware/Software Interface. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 5th edition, 2013. Google Scholar
  22. V. J. Rayward-Smith. UET Scheduling with Unit Interprocessor Communication Delays. Discrete Appl. Math., 18(1):55-71, November 1987. Google Scholar
  23. G. N. Srinivasa Prasanna and B. R. Musicus. Generalised Multiprocessor Scheduling Using Optimal Control. In Proceedings of the Third Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA '91, pages 216-228, New York, NY, USA, 1991. ACM. Google Scholar
  24. J. Turek, J. L. Wolf, and P. S. Yu. Approximate Algorithms Scheduling Parallelizable Tasks. In Proceedings of the Fourth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA '92, pages 323-332, New York, NY, USA, 1992. ACM. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact