Document Open Access Logo

Approximation Algorithms for Demand Strip Packing

Authors Waldo Gálvez , Fabrizio Grandoni, Afrouz Jabal Ameli, Kamyar Khodamoradi

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2021.20.pdf
  • Filesize: 0.93 MB
  • 24 pages

Document Identifiers

Author Details

Waldo Gálvez
  • Technische Universität München, Germany
Fabrizio Grandoni
  • IDSIA, USI-SUPSI, Lugano, Switzerland
Afrouz Jabal Ameli
  • IDSIA, USI-SUPSI, Lugano, Switzerland
Kamyar Khodamoradi
  • Universitä Würzburg, Germany

Funding

  • Gálvez, Waldo: Supported by the European Research Council, Grant Agreement No. 691672, project APEG.
  • Grandoni, Fabrizio: Partially supported by the SNF Excellence Grant 200020B_182865.
  • Ameli, Afrouz Jabal: Partially supported by the SNF Excellence Grant 200020B_182865.
  • Khodamoradi, Kamyar: Partially supported by Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) - Project number 399223600. This project was carried out in part when the author was a postdoctoral researcher at IDSIA, USI-SUPSI, Switzerland.

Cite As Get BibTex

Waldo Gálvez, Fabrizio Grandoni, Afrouz Jabal Ameli, and Kamyar Khodamoradi. Approximation Algorithms for Demand Strip Packing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 20:1-20:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.20

Abstract

In the Demand Strip Packing problem (DSP), we are given a time interval and a collection of tasks, each characterized by a processing time and a demand for a given resource (such as electricity, computational power, etc.). A feasible solution consists of a schedule of the tasks within the mentioned time interval. Our goal is to minimize the peak resource consumption, i.e. the maximum total demand of tasks executed at any point in time. 
It is known that DSP is NP-hard to approximate below a factor 3/2, and standard techniques for related problems imply a (polynomial-time) 2-approximation. Our main result is a (5/3+ε)-approximation algorithm for any constant ε > 0. We also achieve best-possible approximation factors for some relevant special cases.

Subject Classification

ACM Subject Classification
  • Theory of computation → Packing and covering problems
  • Theory of computation → Scheduling algorithms
Keywords
  • Strip Packing
  • Two-Dimensional Packing
  • Approximation Algorithms

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. ACM Trans. Comput. Theory, 9(3):14:1-14:7, 2017. URL: https://doi.org/10.1145/3092026.
  2. Anna Adamaszek and Andreas Wiese. A quasi-ptas for the two-dimensional geometric knapsack problem. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1491-1505. SIAM, 2015. URL: https://doi.org/10.1137/1.9781611973730.98.
  3. Soroush Alamdari, Therese C. Biedl, Timothy M. Chan, Elyot Grant, Krishnam Raju Jampani, Srinivasan Keshav, Anna Lubiw, and Vinayak Pathak. Smart-grid electricity allocation via strip packing with slicing. In 13th International Symposium on Algorithms and Data Structures (WADS), volume 8037, pages 25-36. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-40104-6_3.
  4. Aris Anagnostopoulos, Fabrizio Grandoni, Stefano Leonardi, and Andreas Wiese. A mazing (2+ε)-approximation for unsplittable flow on a path. ACM Transactions on Algorithms, 14(4):55:1-55:23, 2018. URL: https://doi.org/10.1145/3242769.
  5. 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.
  6. Nikhil Bansal, Alberto Caprara, Klaus Jansen, Lars Prädel, and Maxim Sviridenko. A structural lemma in 2-dimensional packing, and its implications on approximability. In Algorithms and Computation, 20th International Symposium (ISAAC), volume 5878, pages 77-86. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-10631-6_10.
  7. Jatin Batra, Naveen Garg, Amit Kumar, Tobias Mömke, and Andreas Wiese. New approximation schemes for unsplittable flow on a path. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 47-58. SIAM, 2015. URL: https://doi.org/10.1137/1.9781611973730.5.
  8. Iwo Bladek, Maciej Drozdowski, Frédéric Guinand, and Xavier Schepler. On contiguous and non-contiguous parallel task scheduling. J. Sched., 18(5):487-495, 2015. URL: https://doi.org/10.1007/s10951-015-0427-z.
  9. Adam L. Buchsbaum, Howard J. Karloff, Claire Kenyon, Nick Reingold, and Mikkel Thorup. OPT versus LOAD in dynamic storage allocation. SIAM Journal on Computing, 33(3):632-646, 2004. URL: https://doi.org/10.1137/S0097539703423941.
  10. Mihai Burcea, Wing-Kai Hon, Hsiang-Hsuan Liu, Prudence W. H. Wong, and David K. Y. Yau. Scheduling for electricity cost in a smart grid. Journal of Scheduling, 19(6):687-699, 2016. URL: https://doi.org/10.1007/s10951-015-0447-8.
  11. Gruia Călinescu, Amit Chakrabarti, Howard J. Karloff, and Yuval Rabani. An improved approximation algorithm for resource allocation. ACM Transactions on Algorithms, 7(4):48:1-48:7, 2011. URL: https://doi.org/10.1145/2000807.2000816.
  12. Edward Grady. Coffman and John L. Bruno. Computer and job-shop scheduling theory / edited by E. G. Coffman, Jr. ; coauthors, J. L. Bruno ... [et al.]. Wiley New York, 1976. Google Scholar
  13. Edward G. Coffman Jr., János Csirik, Gábor Galambos, Silvano Martello, and Daniele Vigo. Bin Packing Approximation Algorithms: Survey and Classification, pages 455-531. Springer New York, 2013. URL: https://doi.org/10.1007/978-1-4419-7997-1_35.
  14. Edward G. Coffman Jr., M. 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.
  15. Max A. Deppert, Klaus Jansen, Arindam Khan, Malin Rau, and Malte Tutas. Peak demand minimization via sliced strip packing. CoRR, abs/2105.07219, 2021. URL: https://arxiv.org/abs/2105.07219.
  16. Pierre-François Dutot, Grégory Mounié, and Denis Trystram. Scheduling parallel tasks approximation algorithms. In Joseph Y.-T. Leung, editor, Handbook of Scheduling - Algorithms, Models, and Performance Analysis. Chapman and Hall/CRC, 2004. Google Scholar
  17. Waldo Gálvez, Fabrizio Grandoni, Afrouz Jabal Ameli, and Kamyar Khodamoradi. Approximation algorithms for demand strip packing. CoRR, abs/2105.08577, 2021. URL: http://arxiv.org/abs/2105.08577.
  18. Waldo Gálvez, Fabrizio Grandoni, Sandy Heydrich, Salvatore Ingala, Arindam Khan, and Andreas Wiese. Approximating geometric knapsack via L-packings. In 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 260-271. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/FOCS.2017.32.
  19. Waldo Gálvez, Fabrizio Grandoni, Sandy Heydrich, Salvatore Ingala, Arindam Khan, and Andreas Wiese. Approximating geometric knapsack via L-packings. CoRR, abs/1711.07710, 2017. URL: http://arxiv.org/abs/1711.07710.
  20. 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), volume 65, pages 9:1-9:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2016.9.
  21. Fabrizio Grandoni, Salvatore Ingala, and Sumedha Uniyal. Improved approximation algorithms for unsplittable flow on a path with time windows. In Approximation and Online Algorithms - 13th International Workshop, (WAOA), volume 9499, pages 13-24. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-28684-6_2.
  22. Fabrizio Grandoni, Tobias Mömke, Andreas Wiese, and Hang Zhou. A (5/3 + ε)-approximation for unsplittable flow on a path: placing small tasks into boxes. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 607-619. ACM, 2018. URL: https://doi.org/10.1145/3188745.3188894.
  23. 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.
  24. Rolf Harren and Rob van Stee. Improved absolute approximation ratios for two-dimensional packing problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop (APPROX), volume 5687, pages 177-189. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-03685-9_14.
  25. 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, 64(1):120-140, 2020. URL: https://doi.org/10.1007/s00224-019-09910-6.
  26. 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. ACM, 2012. URL: https://doi.org/10.1145/2312005.2312048.
  27. Klaus Jansen and Malin Rau. Closing the gap for pseudo-polynomial strip packing. In 27th Annual European Symposium on Algorithms (ESA), volume 144, pages 62:1-62:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.62.
  28. Klaus Jansen and Malin Rau. Improved approximation for two dimensional strip packing with polynomial bounded width. Theoretical Computer Science, 789:34-49, 2019. URL: https://doi.org/10.1016/j.tcs.2019.04.002.
  29. 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.
  30. 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.
  31. Mohammad M. Karbasioun, Gennady Shaikhet, Evangelos Kranakis, and Ioannis Lambadaris. Power strip packing of malleable demands in smart grid. In Proceedings of IEEE International Conference on Communications, (ICC), pages 4261-4265. IEEE, 2013. URL: https://doi.org/10.1109/ICC.2013.6655233.
  32. 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.
  33. Joseph Y.-T. Leung, Tommy W. Tam, C. S. Wong, Gilbert H. Young, and Francis Y. L. Chin. Packing squares into a square. Journal of Parallel and Distributed Computing, 10(3):271-275, 1990. URL: https://doi.org/10.1016/0743-7315(90)90019-L.
  34. Fu-Hong Liu, Hsiang-Hsuan Liu, and Prudence W. H. Wong. Greedy is optimal for online restricted assignment and smart grid scheduling for unit size jobs. In Approximation and Online Algorithms - 17th International Workshop (WAOA), volume 11926, pages 217-231. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-39479-0_15.
  35. Fu-Hong Liu, Hsiang-Hsuan Liu, and Prudence W. H. Wong. Non-preemptive scheduling in a smart grid model and its implications on machine minimization. Algorithmica, 82(12):3415-3457, 2020. URL: https://doi.org/10.1007/s00453-020-00733-3.
  36. Tobias Mömke and Andreas Wiese. A (2+ε)-approximation algorithm for the storage allocation problem. In Automata, Languages, and Programming - 42nd International Colloquium (ICALP), volume 9134, pages 973-984. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-47672-7_79.
  37. Tobias Mömke and Andreas Wiese. Breaking the barrier of 2 for the storage allocation problem. In 47th International Colloquium on Automata, Languages, and Programming (ICALP), volume 168, pages 86:1-86:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.86.
  38. Giorgi Nadiradze and Andreas Wiese. On approximating strip packing with a better ratio than 3/2. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1491-1510. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch102.
  39. Anshu Ranjan, Pramod P. Khargonekar, and Sartaj Sahni. Offline first fit scheduling in smart grids. In 2015 IEEE Symposium on Computers and Communication (ISCC), pages 758-763. IEEE Computer Society, 2015. URL: https://doi.org/10.1109/ISCC.2015.7405605.
  40. Ingo Schiermeyer. Reverse-fit: A 2-optimal algorithm for packing rectangles. In Jan van Leeuwen, editor, Algorithms (ESA) - Second Annual European Symposium, volume 855, pages 290-299. Springer, 1994. URL: https://doi.org/10.1007/BFb0049416.
  41. 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.
  42. 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.
  43. Shaojie Tang, Qiuyuan Huang, Xiang-Yang Li, and Dapeng Wu. Smoothing the energy consumption: Peak demand reduction in smart grid. In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM), pages 1133-1141. IEEE, 2013. URL: https://doi.org/10.1109/INFCOM.2013.6566904.
  44. Sean Yaw and Brendan Mumey. Scheduling non-preemptible jobs to minimize peak demand. Algorithms, 10(4):122, 2017. URL: https://doi.org/10.3390/a10040122.
  45. Sean Yaw, Brendan Mumey, Erin McDonald, and Jennifer Lemke. Peak demand scheduling in the smart grid. In 2014 IEEE International Conference on Smart Grid Communications (SmartGridComm), pages 770-775. IEEE, 2014. URL: https://doi.org/10.1109/SmartGridComm.2014.7007741.
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