algorithm so that C machines can be optimally utilized by a set of batch tasks. We further derive four algorithmic results in obvious or non-obvious ways: (i) a greedy algorithm for social welfare maximization with a pseudo-polynomial time complexity of $O(knd^2\max\{d, n\})$ that achieves an approximation ratio of $\frac{s-1}{s}$, (ii) the first dynamic programming algorithm for social welfare maximization with a pseudo-polynomial time complexity of $O(\max\{nC^d, n \log n\})$, (iii) the first exact algorithm for machine minimization with a pseudo-polynomial time complexity of $O(nd \log(kn))$, and (iv) a $(1+\epsilon)$-approximation algorithm with a pseudo-polynomial time complexity of $O(nkd \log(kn) \log(n/\epsilon))$ for minimizing the maximum weighted completion time of all tasks. Here, $d$ is the maximum deadline of tasks while $k$ is the maximum parallelism bound of tasks.

**Acknowledgements** The work of Patrick Loiseau has been partially supported by MIAI @ Grenoble Alpes (ANR-19-P3IA-0003), by the French National Research Agency (ANR) through grant ANR-20-CE23-0007 and through the “Investissements d’avenir” program (ANR-15-IDEX-02); and by the Alexander von Humboldt Foundation.

**Compliance with Ethical Standards Conflict of Interest** The authors declare that they have no conflict of interest.

**Data Availability** Data sharing not applicable to this article as no datasets were generated or analysed during the current study.

## References

1. G. Brassard, and P. Bratley. Fundamentals of Algorithmics. Prentice-Hall, Inc., 1996.

2. X. Wu, P. Loiseau, and E. Hyytiä. “Towards Designing Cost-Optimal Policies to Utilize IaaS Clouds with Online Learning.” *IEEE Transactions on Parallel and Distributed Systems* (2019).

3. G. C. Fox. "Data intensive applications on clouds." In *Proceedings of the second international workshop on Data intensive computing in the clouds*, pp. 1-2. ACM, 2011.

4. T. Gunarathne, T.-L. Wu, J. Qiu, & G. Fox. "Cloud computing paradigms for pleasingly parallel biomedical applications." *In Proceedings of the 19th ACM International Symposium on High Performance Distributed Computing (HPDC'10)*, pp. 460-469. ACM, 2010.

5. P.-F. Dutot, G. Mounié, & D. Trystram, "Scheduling parallel tasks: approximation algorithms," in Handbook of Scheduling: Algorithms, Models, and Performance Analysis, J. Y.-T. Leung (Eds.), CRC Press, Boca Raton, 2004.

6. N. Jain, I. Menache, J. Naor, & J. Yaniv. "A Truthful Mechanism for Value-Based Scheduling in Cloud Computing." *In the 4th International Symposium on Algorithmic Game Theory*, pp. 178-189, Springer, 2011.

7. N. Jain, I. Menache, J. Naor, & J. Yaniv. "Near-optimal scheduling mechanisms for deadline-sensitive jobs in large computing clusters." *In Proceedings of the twenty-fourth annual ACM symposium on Parallelism in algorithms and architectures*, pp. 255-266. ACM, 2012.

8. V. Nagarajan, J. Wolf, A. Balmin, & K. Hildrum. "Malleable scheduling for flows of jobs and applications to MapReduce." *Journal of Scheduling*, 2019, vol. 22, no 4, p. 393-411.

9. B. Lucier, I. Menache, J. Naor, & J. Yaniv. "Efficient online scheduling for deadline-sensitive jobs." *In Proceedings of the twenty-fifth annual ACM symposium on Parallelism in algorithms and architectures*, pp. 305-314. ACM, 2013.

10. Y. Azar, I. Kalp-Shaltiel, B. Lucier, I. Menache, J. Naor, & J. Yaniv. "Truthful online scheduling with commitments." *In Proceedings of the Sixteenth ACM Conference on Economics and Computation*, pp. 715-732. ACM, 2015.

11. P. Bodík, I. Menache, J. Naor, & J. Yaniv. "Brief announcement: deadline-aware scheduling of big-data processing jobs." *In Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures*, pp. 211-213. ACM, 2014.
algorithm so that C machines can be optimally utilized by a set of batch tasks. We further derive four algorithmic results in obvious or non-obvious ways: (i) a greedy algorithm for social welfare maximization with a pseudo-polynomial time complexity of $O(knd^2\max\{d, n\})$ that achieves an approximation ratio of $\frac{s-1}{s}$, (ii) the first dynamic programming algorithm for social welfare maximization with a pseudo-polynomial time complexity of $O(\max\{nC^d, n \log n\})$, (iii) the first exact algorithm for machine minimization with a pseudo-polynomial time complexity of $O(nd \log(kn))$, and (iv) a $(1+\epsilon)$-approximation algorithm with a pseudo-polynomial time complexity of $O(nkd \log(kn) \log(n/\epsilon))$ for minimizing the maximum weighted completion time of all tasks. Here, $d$ is the maximum deadline of tasks while $k$ is the maximum parallelism bound of tasks.

**Acknowledgements** The work of Patrick Loiseau has been partially supported by MIAI @ Grenoble Alpes (ANR-19-P3IA-0003), by the French National Research Agency (ANR) through grant ANR-20-CE23-0007 and through the “Investissements d’avenir” program (ANR-15-IDEX-02); and by the Alexander von Humboldt Foundation.

**Compliance with Ethical Standards Conflict of Interest** The authors declare that they have no conflict of interest.

**Data Availability** Data sharing not applicable to this article as no datasets were generated or analysed during the current study.

## References

1. G. Brassard, and P. Bratley. Fundamentals of Algorithmics. Prentice-Hall, Inc., 1996.

2. X. Wu, P. Loiseau, and E. Hyytiä. “Towards Designing Cost-Optimal Policies to Utilize IaaS Clouds with Online Learning.” *IEEE Transactions on Parallel and Distributed Systems* (2019).

3. G. C. Fox. “Data intensive applications on clouds.” *In Proceedings of the second international workshop on Data intensive computing in the clouds*, pp. 1-2. ACM, 2011.

4. T. Gunarathne, T.-L. Wu, J. Qiu, & G. Fox. “Cloud computing paradigms for pleasingly parallel biomedical applications.” *In Proceedings of the 19th ACM International Symposium on High Performance Distributed Computing* (HPDC’10), pp. 460-469. ACM, 2010.

5. P.-F. Dutot, G. Mounié, & D. Trystram, “Scheduling parallel tasks: approximation algorithms,” in Handbook of Scheduling: Algorithms, Models, and Performance Analysis, J. Y.-T. Leung (Eds.), CRC Press, Boca Raton, 2004.

6. N. Jain, I. Menache, J. Naor, & J. Yaniv. “A Truthful Mechanism for Value-Based Scheduling in Cloud Computing.” *In the 4th International Symposium on Algorithmic Game Theory*, pp. 178-189, Springer, 2011.

7. N. Jain, I. Menache, J. Naor, & J. Yaniv. “Near-optimal scheduling mechanisms for deadline-sensitive jobs in large computing clusters.” *In Proceedings of the twenty-fourth annual ACM symposium on Parallelism in algorithms and architectures*, pp. 255-266. ACM, 2012.

8. V. Nagarajan, J. Wolf, A. Balmin, & K. Hildrum. “Malleable scheduling for flows of jobs and applications to MapReduce.” *Journal of Scheduling*, 2019, vol. 22, no 4, p. 393-411.

9. B. Lucier, I. Menache, J. Naor, & J. Yaniv. “Efficient online scheduling for deadline-sensitive jobs.” *In Proceedings of the twenty-fifth annual ACM symposium on Parallelism in algorithms and architectures*, pp. 305-314. ACM, 2013.

10. Y. Azar, I. Kalp-Shaltiel, B. Lucier, I. Menache, J. Naor, & J. Yaniv. “Truthful online scheduling with commitments.” *In Proceedings of the Sixteenth ACM Conference on Economics and Computation*, pp. 715-732. ACM, 2015.

11. P. Bodík, I. Menache, J. Naor, & J. Yaniv. “Brief announcement: deadline-aware scheduling of big-data processing jobs.” *In Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures*, pp. 211-213. ACM, 2014.
12. Eugene L. Lawler. "A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs." *Annals of Operations Research* 26, no. 1 (1990): 125-133.

13. D. Karger, C. Stein, & J. Wein. "Scheduling Algorithms." In *CRC Handbook of Computer Science*. 1997.

14. James R. Jackson. "Scheduling a Production Line to Minimize Maximum Tardiness." *Management Science Research Project Research Report* 43, University of California, Los Angeles, 1955.

15. W. A. Horn. "Some Simple Scheduling Algorithms." *Naval Research Logistics Quarterly*, 21:177-185, 1974.

16. E. L. Lawler, & J. M. Moore. "A Functional Equation and Its Application to Resource Allocation and Sequencing Problems." *Management Science* 16, no. 1 (1969): 77-84.

17. J. A. Stankovic, M. Spuri, K. Ramamritham, and G. Buttazzo, "Deadline Scheduling for Real-Time Systems: EDF and Related Algorithms." *Kluwer Academic*, 1998.

18. T. White. "Hadoop: The definitive guide." *O'Reilly Media, Inc.*, 2012.

19. J., Sudipto Guha, S. Khanna, and J. Naor. "Machine minimization for scheduling jobs with interval constraints." *In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science* (FOCS'04), pp. 81-90. IEEE, 2004.

20. D. P. Williamson and D. B. Shmoys. "The Design of Approximation Algorithm." *Cambridge University Press*, 2011.

21. X. Wu, & P. Loiseau. "Algorithms for scheduling deadline-sensitive malleable tasks." *In Proceedings of the 53rd Annual Allerton Conference on Communication, Control, and Computing* (Allerton), pp. 530-537. IEEE, 2015.

22. L. Guo, & H. Shen. "Efficient Approximation Algorithms for the Bounded Flexible Scheduling Problem in Clouds." *IEEE Transactions on Parallel and Distributed Systems* 28, no. 12 (2017): 3511-3520.

23. G. Even, "Recursive greedy methods," in *Handbook of Approximation Algorithms and Metaheuristics*, T. F. Gonzalez, ed., CRC, Boca Raton, FL, 2007, ch. 5.

24. K. Jansen, & M. Rau. "Closing the Gap for Pseudo-Polynomial Strip Packing." *In Proceedings of the 27th Annual European Symposium on Algorithms* (ESA'19), pp. 62:1-62:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.

25. K. Jansen, & M. Rau. "Improved approximation for two dimensional strip packing with polynomial bounded width." *Theoretical Computer Science* (2019).

26. M. Bougeret, P.-F. Dutot, K. Jansen, C. Robenek, & D. Trystram. "Approximation algorithms for multiple strip packing and scheduling parallel jobs in platforms." *Discrete Mathematics, Algorithms and Applications* 3, no. 04 (2011): 553-586.

27. K. Jansen, & F. Land. "Scheduling monotone moldable jobs in linear time." *In 2018 IEEE International Parallel and Distributed Processing Symposium* (IPDPS'18), pp. 172-181. IEEE, 2018.

28. R. Bleuse, S. Hunold, S. Kedad-Sidhoum, F. Monna, G. Mounié, & D. Trystram. "Scheduling independent moldable tasks on multi-cores with GPUs." *IEEE Transactions on Parallel and Distributed Systems* 28, no. 9 (2017): 2689-2702.

29. X. Wu, & P. Loiseau. "Efficient Algorithms for Scheduling Moldable Tasks." *arXiv:1609.08588v8* (2016).

30. X. Wu, & P. Loiseau. "Efficient approximation algorithms for scheduling moldable tasks." *European Journal of Operational Research* 310, no. 1 (2023): 71-83.

31. G. Mounié, C. Rapine, & D. Trystram. "A $\frac{3}{2}$-approximation algorithm for scheduling independent monotonic malleable tasks." *SIAM Journal on Computing* 37, no. 2 (2007): 401-412.

32. P.-F. Dutot, and D. Trystram. "Scheduling on hierarchical clusters using malleable tasks." *In Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures*, pp. 199-208. ACM, 2001.

33. R. Lepère, D. Trystram, & G. J. Woeginger. "Approximation algorithms for scheduling malleable tasks under precedence constraints." *International Journal of Foundations of Computer Science* 13, no. 04 (2002): 613-627.

34. K. Jansen, & L. Porkolab. "Linear-time approximation schemes for scheduling malleable parallel tasks." *Algorithmica* 32, no. 3 (2002): 507-520.

35. W. Ludwig, & P. Tiwari. "Scheduling malleable and nonmalleable parallel tasks." *In Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms*, pp. 167-176. SIAM, 1994.
12. Eugene L. Lawler. "A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs." *Annals of Operations Research* 26, no. 1 (1990): 125-133.

13. D. Karger, C. Stein, & J. Wein. "Scheduling Algorithms." In *CRC Handbook of Computer Science*. 1997.

14. James R. Jackson. "Scheduling a Production Line to Minimize Maximum Tardiness." *Management Science Research Project Research Report* 43, University of California, Los Angeles, 1955.

15. W. A. Horn. "Some Simple Scheduling Algorithms." *Naval Research Logistics Quarterly*, 21:177-185, 1974.

16. E. L. Lawler, & J. M. Moore. "A Functional Equation and Its Application to Resource Allocation and Sequencing Problems." *Management Science* 16, no. 1 (1969): 77-84.

17. J. A. Stankovic, M. Spuri, K. Ramamritham, and G. Buttazzo, "Deadline Scheduling for Real-Time Systems: EDF and Related Algorithms." *Kluwer Academic*, 1998.

18. T. White. "Hadoop: The definitive guide." *O'Reilly Media, Inc.*, 2012.

19. J., Sudipto Guha, S. Khanna, and J. Naor. "Machine minimization for scheduling jobs with interval constraints." *In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04)*, pp. 81-90. IEEE, 2004.

20. D. P. Williamson and D. B. Shmoys. "The Design of Approximation Algorithm." *Cambridge University Press*, 2011.

21. X. Wu, & P. Loiseau. "Algorithms for scheduling deadline-sensitive malleable tasks." *In Proceedings of the 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton)*, pp. 530-537. IEEE, 2015.

22. L. Guo, & H. Shen. "Efficient Approximation Algorithms for the Bounded Flexible Scheduling Problem in Clouds." *IEEE Transactions on Parallel and Distributed Systems* 28, no. 12 (2017): 3511-3520.

23. G. Even, "Recursive greedy methods," in *Handbook of Approximation Algorithms and Metaheuristics*, T. F. Gonzalez, ed., CRC, Boca Raton, FL, 2007, ch. 5.

24. K. Jansen, & M. Rau. "Closing the Gap for Pseudo-Polynomial Strip Packing." *In Proceedings of the 27th Annual European Symposium on Algorithms* (ESA'19), pp. 62:1-62:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.

25. K. Jansen, & M. Rau. "Improved approximation for two dimensional strip packing with polynomial bounded width." *Theoretical Computer Science* (2019).

26. M. Bougeret, P.-F. Dutot, K. Jansen, C. Robenek, & D. Trystram. "Approximation algorithms for multiple strip packing and scheduling parallel jobs in platforms." *Discrete Mathematics, Algorithms and Applications* 3, no. 04 (2011): 553-586.

27. K. Jansen, & F. Land. "Scheduling monotone moldable jobs in linear time." *In 2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS'18)*, pp. 172-181. IEEE, 2018.

28. R. Bleuse, S. Hunold, S. Kedad-Sidhoum, F. Monna, G. Mounié, & D. Trystram. "Scheduling independent moldable tasks on multi-cores with GPUs." *IEEE Transactions on Parallel and Distributed Systems* 28, no. 9 (2017): 2689-2702.

29. X. Wu, & P. Loiseau. "Efficient Algorithms for Scheduling Moldable Tasks." *arXiv:1609.08588v8* (2016).

30. X. Wu, & P. Loiseau. "Efficient approximation algorithms for scheduling moldable tasks." *European Journal of Operational Research* 310, no. 1 (2023): 71-83.

31. G. Mounié, C. Rapine, & D. Trystram. "A $\frac{3}{2}$-approximation algorithm for scheduling independent monotonic malleable tasks." *SIAM Journal on Computing* 37, no. 2 (2007): 401-412.

32. P.-F. Dutot, and D. Trystram. "Scheduling on hierarchical clusters using malleable tasks." *In Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures*, pp. 199-208. ACM, 2001.

33. R. Lepère, D. Trystram, & G. J. Woeginger. "Approximation algorithms for scheduling malleable tasks under precedence constraints." *International Journal of Foundations of Computer Science* 13, no. 04 (2002): 613-627.

34. K. Jansen, & L. Porkolab. "Linear-time approximation schemes for scheduling malleable parallel tasks." *Algorithmica* 32, no. 3 (2002): 507-520.

35. W. Ludwig, & P. Tiwari. "Scheduling malleable and nonmalleable parallel tasks." *In Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms*, pp. 167-176. SIAM, 1994.