Document Open Access Logo

Closing the Gap for Single Resource Constraint Scheduling

Authors Klaus Jansen , Malin Rau

PDF
Thumbnail PDF

File

LIPIcs.ESA.2021.53.pdf
  • Filesize: 0.8 MB
  • 15 pages

Document Identifiers

Author Details

Klaus Jansen
  • Universität Kiel, Germany
Malin Rau
  • Universität Hamburg, Germany

Funding

Research was supported by German Research Foundation (DFG) project JA 612 / 20-1.

Cite As Get BibTex

Klaus Jansen and Malin Rau. Closing the Gap for Single Resource Constraint Scheduling. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 53:1-53:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ESA.2021.53

Abstract

In the problem called single resource constraint scheduling, we are given m identical machines and a set of jobs, each needing one machine to be processed as well as a share of a limited renewable resource R. A schedule of these jobs is feasible if, at each point in the schedule, the number of machines and resources required by jobs processed at this time is not exceeded. It is NP-hard to approximate this problem with a ratio better than 3/2. On the other hand, the best algorithm so far has an absolute approximation ratio of 2+ε. In this paper, we present an algorithm with absolute approximation ratio (3/2+ε), which closes the gap between inapproximability and best algorithm with exception of a negligible small ε.

Subject Classification

ACM Subject Classification
  • Theory of computation → Packing and covering problems
  • Theory of computation → Scheduling algorithms
Keywords
  • resource constraint scheduling
  • approximation algorithm

Metrics

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

Related Versions

References

  1. Anna Adamaszek, Tomasz Kociumaka, Marcin Pilipczuk, and Michal Pilipczuk. Hardness of approximation for strip packing. TOCT, 9(3):14:1-14:7, 2017. URL: https://doi.org/10.1145/3092026.
  2. Noga Alon, Yossi Azar, Gerhard J Woeginger, and Tal Yadid. Approximation schemes for scheduling on parallel machines. Journal of Scheduling, 1(1):55-66, 1998. Google Scholar
  3. Brenda S. Baker, Donna J. Brown, and Howard P. Katseff. A 5/4 algorithm for two-dimensional packing. Journal of Algorithms, 2(4):348-368, 1981. URL: https://doi.org/10.1016/0196-6774(81)90034-1.
  4. Brenda S. Baker, Edward G. Coffman Jr., and Ronald L. Rivest. Orthogonal packings in two dimensions. SIAM Journal on Computing, 9(4):846-855, 1980. URL: https://doi.org/10.1137/0209064.
  5. Marin Bougeret, Pierre-François Dutot, Klaus Jansen, Christina Robenek, and Denis Trystram. Approximation algorithms for multiple strip packing and scheduling parallel jobs in platforms. Discrete Mathematics, Algorithms and Applications, 3(4):553-586, 2011. URL: https://doi.org/10.1142/S1793830911001413.
  6. Edward G. Coffman Jr., Michael R. Garey, David S. Johnson, and Robert Endre Tarjan. Performance bounds for level-oriented two-dimensional packing algorithms. SIAM Journal on Computing, 9(4):808-826, 1980. URL: https://doi.org/10.1137/0209062.
  7. Jianzhong Du and Joseph Y.-T. Leung. Complexity of scheduling parallel task systems. SIAM Journal on Discrete Mathematics, 2(4):473-487, 1989. URL: https://doi.org/10.1137/0402042.
  8. Leah Epstein and Asaf Levin. AFPTAS results for common variants of bin packing: A new method for handling the small items. SIAM Journal on Optimization, 20(6):3121-3145, 2010. URL: https://doi.org/10.1137/090767613.
  9. Waldo Gálvez, Fabrizio Grandoni, Salvatore Ingala, and Arindam Khan. Improved pseudo-polynomial-time approximation for strip packing. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pages 9:1-9:14, 2016. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2016.9.
  10. Michael R. Garey and Ronald L. Graham. Bounds for multiprocessor scheduling with resource constraints. SIAM Journal on Computing, 4(2):187-200, 1975. URL: https://doi.org/10.1137/0204015.
  11. Michael R. Garey and David S. Johnson. Complexity results for multiprocessor scheduling under resource constraints. SIAM Journal on Computing, 4(4):397-411, 1975. Google Scholar
  12. Igal Golan. Performance bounds for orthogonal oriented two-dimensional packing algorithms. SIAM Journal on Computing, 10(3):571-582, 1981. URL: https://doi.org/10.1137/0210042.
  13. Ronald L Graham. Bounds on multiprocessing timing anomalies. SIAM journal on Applied Mathematics 17.2, pages 416-429, 1969. Google Scholar
  14. Alexander Grigoriev, Maxim Sviridenko, and Marc Uetz. Machine scheduling with resource dependent processing times. Mathematical programming, 110(1):209-228, 2007. Google Scholar
  15. Rolf Harren, Klaus Jansen, Lars Prädel, and Rob van Stee. A (5/3 + ε)-approximation for strip packing. Computational Geometry, 47(2):248-267, 2014. URL: https://doi.org/10.1016/j.comgeo.2013.08.008.
  16. Rolf Harren and Rob van Stee. Improved absolute approximation ratios for two-dimensional packing problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques,, volume 5687 of Lecture Notes in Computer Science, pages 177-189. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-03685-9_14.
  17. Sören Henning, Klaus Jansen, Malin Rau, and Lars Schmarje. Complexity and inapproximability results for parallel task scheduling and strip packing. Theory of Computing Systems, 2019. URL: https://doi.org/10.1007/s00224-019-09910-6.
  18. Dorit S. Hochbaum and David B. Shmoys. Using dual approximation algorithms for scheduling problems theoretical and practical results. Journal of the ACM (JACM), 34(1):144-162, 1987. Google Scholar
  19. Klaus Jansen. A (3/2+ε) approximation algorithm for scheduling moldable and non-moldable parallel tasks. In 24th ACM Symposium on Parallelism in Algorithms and Architectures, (SPAA), pages 224-235, 2012. URL: https://doi.org/10.1145/2312005.2312048.
  20. Klaus Jansen, Kim-Manuel Klein, and José Verschae. Closing the gap for makespan scheduling via sparsification techniques. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, pages 72:1-72:13, 2016. URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.72.
  21. Klaus Jansen, Marten Maack, and Malin Rau. Approximation schemes for machine scheduling with resource (in-)dependent processing times. ACM Trans. Algorithms, 15(3):31:1-31:28, 2019. URL: https://doi.org/10.1145/3302250.
  22. Klaus Jansen and Lorant Porkolab. Linear-time approximation schemes for scheduling malleable parallel tasks. Algorithmica, 32(3):507-520, 2002. URL: https://doi.org/10.1007/s00453-001-0085-8.
  23. Klaus Jansen and Malin Rau. Improved approximation for two dimensional strip packing with polynomial bounded width. Theor. Comput. Sci., 789:34-49, 2019. URL: https://doi.org/10.1016/j.tcs.2019.04.002.
  24. Klaus Jansen and Malin Rau. Linear time algorithms for multiple cluster scheduling and multiple strip packing. CoRR, abs/1902.03428, 2019. URL: http://arxiv.org/abs/1902.03428.
  25. Klaus Jansen and Roberto Solis-Oba. Rectangle packing with one-dimensional resource augmentation. Discrete Optimization, 6(3):310-323, 2009. URL: https://doi.org/10.1016/j.disopt.2009.04.001.
  26. Klaus Jansen and Ralf Thöle. Approximation algorithms for scheduling parallel jobs. SIAM Journal on Computing, 39(8):3571-3615, 2010. URL: https://doi.org/10.1137/080736491.
  27. Berit Johannes. Scheduling parallel jobs to minimize the makespan. Journal of Scheduling, 9(5):433-452, 2006. URL: https://doi.org/10.1007/s10951-006-8497-6.
  28. Hans Kellerer. An approximation algorithm for identical parallel machine scheduling with resource dependent processing times. Operations Research Letters, 36(2):157-159, 2008. Google Scholar
  29. Claire Kenyon and Eric Rémila. A near-optimal solution to a two-dimensional cutting stock problem. Mathematics of Operations Research, 25(4):645-656, 2000. URL: https://doi.org/10.1287/moor.25.4.645.12118.
  30. Giorgi Nadiradze and Andreas Wiese. On approximating strip packing with a better ratio than 3/2. In 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1491-1510, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch102.
  31. Martin Niemeier and Andreas Wiese. Scheduling with an orthogonal resource constraint. Algorithmica, 71(4):837-858, 2015. URL: https://doi.org/10.1007/s00453-013-9829-5.
  32. Ingo Schiermeyer. Reverse-fit: A 2-optimal algorithm for packing rectangles. In 2nd Annual European Symposium on Algorithms (ESA) - Algorithms, pages 290-299, 1994. URL: https://doi.org/10.1007/BFb0049416.
  33. Daniel Dominic Sleator. A 2.5 times optimal algorithm for packing in two dimensions. Information Processing Letters, 10(1):37-40, 1980. URL: https://doi.org/10.1016/0020-0190(80)90121-0.
  34. A. Steinberg. A strip-packing algorithm with absolute performance bound 2. SIAM Journal on Computing, 26(2):401-409, 1997. URL: https://doi.org/10.1137/S0097539793255801.
  35. Maxim Sviridenko. A note on the kenyon-remila strip-packing algorithm. Inf. Process. Lett., 112(1-2):10-12, 2012. URL: https://doi.org/10.1016/j.ipl.2011.10.003.
  36. John Turek, Joel L. Wolf, and Philip S. Yu. Approximate algorithms scheduling parallelizable tasks. In 4th annual ACM symposium on Parallel algorithms and architectures (SPAA), pages 323-332, 1992. URL: https://doi.org/10.1145/140901.141909.
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