Document Open Access Logo

Peak Demand Minimization via Sliced Strip Packing

Authors Max A. Deppert , Klaus Jansen , Arindam Khan , Malin Rau , Malte Tutas

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2021.21.pdf
  • Filesize: 0.89 MB
  • 24 pages

Document Identifiers

Author Details

Max A. Deppert
  • Universität Kiel, Germany
Klaus Jansen
  • Universität Kiel, Germany
Arindam Khan
  • Department of Computer Science and Automation, Indian Institute of Science, Bengaluru, India
Malin Rau
  • Universität Hamburg, Germany
Malte Tutas
  • Universität Kiel, Germany

Funding

  • Deppert, Max A.: Research supported by German Research Foundation (DFG) project JA 612/25-1.
  • Jansen, Klaus: Research supported by German Research Foundation (DFG) project JA 612/25-1.
  • Rau, Malin: Research supported by the French research program ENERGUMEN ANR-18-CE25-0008.

Cite AsGet BibTex

Max A. Deppert, Klaus Jansen, Arindam Khan, Malin Rau, and Malte Tutas. Peak Demand Minimization via Sliced Strip Packing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 21:1-21:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.21

Abstract

We study the Nonpreemptive Peak Demand Minimization (NPDM) problem, where we are given a set of jobs, specified by their processing times and energy requirements. The goal is to schedule all jobs within a fixed time period such that the peak load (the maximum total energy requirement at any time) is minimized. This problem has recently received significant attention due to its relevance in smart-grids. Theoretically, the problem is related to the classical strip packing problem (SP). In SP, a given set of axis-aligned rectangles must be packed into a fixed-width strip, such that the height of the strip is minimized. NPDM can be modeled as strip packing with slicing and stacking constraint: each rectangle may be cut vertically into multiple slices and the slices may be packed into the strip as individual pieces. The stacking constraint forbids solutions where two slices of the same rectangle are intersected by the same vertical line. Nonpreemption enforces the slices to be placed in contiguous horizontal locations (but may be placed at different vertical locations). We obtain a (5/3+ε)-approximation algorithm for the problem. We also provide an asymptotic efficient polynomial-time approximation scheme (AEPTAS) which generates a schedule for almost all jobs with energy consumption (1+ε) OPT. The remaining jobs fit into a thin container of height 1. The previous best result for NPDM was a 2.7 approximation based on FFDH [Ranjan et al., 2015]. One of our key ideas is providing several new lower bounds on the optimal solution of a geometric packing, which could be useful in other related problems. These lower bounds help us to obtain approximative solutions based on Steinberg’s algorithm in many cases. In addition, we show how to split schedules generated by the AEPTAS into few segments and to rearrange the corresponding jobs to insert the thin container mentioned above.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • scheduling
  • peak demand minimization
  • approximation

Metrics

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

Related Versions

References

  1. Anna Adamaszek, Sariel Har-Peled, and Andreas Wiese. Approximation schemes for independent set and sparse subsets of polygons. J. ACM, 66(4):29:1-29:40, 2019. Google Scholar
  2. Anna Adamaszek, Tomasz Kociumaka, Marcin Pilipczuk, and Michal Pilipczuk. Hardness of approximation for strip packing. ACM Transactions on Computation Theory, 9(3):14:1-14:7, 2017. URL: https://doi.org/10.1145/3092026.
  3. Soroush Alamdari, Therese 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 Workshop on Algorithms and Data Structures, pages 25-36. Springer, 2013. Google Scholar
  4. Brenda S. Baker, Edward G. Coffman Jr., and Ronald L. Rivest. Orthogonal packings in two dimensions. SIAM J. Comput., 9(4):846-855, 1980. URL: https://doi.org/10.1137/0209064.
  5. Nikhil Bansal, Alberto Caprara, and Maxim Sviridenko. A new approximation method for set covering problems, with applications to multidimensional bin packing. SIAM J. Comput., 39(4):1256-1278, 2009. URL: https://doi.org/10.1137/080736831.
  6. Nikhil Bansal, José R. Correa, Claire Kenyon, and Maxim Sviridenko. Bin packing in multiple dimensions: Inapproximability results and approximation schemes. Math. Oper. Res., 31(1):31-49, 2006. URL: https://doi.org/10.1287/moor.1050.0168.
  7. Nikhil Bansal and Arindam Khan. Improved approximation algorithm for two-dimensional bin packing. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 13-25. SIAM, 2014. URL: https://doi.org/10.1137/1.9781611973402.2.
  8. Nikhil Bansal, Andrea Lodi, and Maxim Sviridenko. A tale of two dimensional bin packing. In FOCS, pages 657-666, 2005. Google Scholar
  9. Iwo Błądek, Maciej Drozdowski, Frédéric Guinand, and Xavier Schepler. On contiguous and non-contiguous parallel task scheduling. Journal of Scheduling, 18(5):487-495, 2015. Google Scholar
  10. Marin Bougeret, Pierre François Dutot, Klaus Jansen, Christina Otte, and Denis Trystram. Approximating the non-contiguous multiple organization packing problem. In IFIP International Conference on Theoretical Computer Science, pages 316-327. Springer, 2010. Google Scholar
  11. 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. Discret. Math. Algorithms Appl., 3(4):553-586, 2011. URL: https://doi.org/10.1142/S1793830911001413.
  12. Nilotpal Chakraborty, Arijit Mondal, and Samrat Mondal. Efficient scheduling of nonpreemptive appliances for peak load optimization in smart grid. IEEE Transactions on Industrial Informatics, 14(8):3447-3458, 2017. Google Scholar
  13. Henrik I. Christensen, Arindam Khan, Sebastian Pokutta, and Prasad Tetali. Approximation and online algorithms for multidimensional bin packing: A survey. Computer Science Review, 24:63-79, 2017. Google Scholar
  14. Waldo Gálvez, Fabrizio Grandoni, Afrouz Jabal Ameli, Klaus Jansen, Arindam Khan, and Malin Rau. A tight (3/2+ε) approximation for skewed strip packing. In Jaroslaw Byrka and Raghu Meka, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020, August 17-19, 2020, Virtual Conference, volume 176 of LIPIcs, pages 44:1-44:18, 2020. Google Scholar
  15. 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.
  16. Waldo Gálvez, Fabrizio Grandoni, Sandy Heydrich, Salvatore Ingala, Arindam Khan, and Andreas Wiese. Approximating geometric knapsack via l-packings. In FOCS, pages 260-271, 2017. Google Scholar
  17. Waldo Gálvez, Fabrizio Grandoni, Arindam Khan, Diego Ramirez-Romero, and Andreas Wiese. Improved approximation algorithms for 2-dimensional knapsack: Packing into multiple l-shapes, spirals and more. In SoCG, pages 39:1-39:17, 2021. Google Scholar
  18. 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.
  19. 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 STOC, pages 607-619, 2018. Google Scholar
  20. Rolf Harren, Klaus Jansen, Lars Prädel, and Rob van Stee. A (5/3 + eps)-approximation for 2d strip packing. In Andreas Brieden, Zafer-Korcan Görgülü, Tino Krug, Erik Kropat, Silja Meyer-Nieberg, Goran Mihelcic, and Stefan Wolfgang Pickl, editors, 11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, Munich, Germany, May 29-31, 2012. Extended Abstracts, pages 139-142, 2012. Google Scholar
  21. Rolf Harren and Rob van Stee. Improved absolute approximation ratios for two-dimensional packing problems. In Irit Dinur, Klaus Jansen, Joseph Naor, and José D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009, Berkeley, CA, USA, August 21-23, 2009. Proceedings, 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.
  22. 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.
  23. Klaus Jansen. Scheduling malleable parallel tasks: An asymptotic fully polynomial time approximation scheme. Algorithmica, 39(1):59-81, 2004. Google Scholar
  24. Klaus Jansen. A (3/2+ ε) approximation algorithm for scheduling moldable and non-moldable parallel tasks. In Proceedings of the twenty-fourth annual ACM symposium on Parallelism in algorithms and architectures, pages 224-235, 2012. Google Scholar
  25. Klaus Jansen and Felix 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. IEEE Computer Society, 2018. URL: https://doi.org/10.1109/IPDPS.2018.00027.
  26. Klaus Jansen and Lars Prädel. A new asymptotic approximation algorithm for 3-dimensional strip packing. In 40th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), volume 8327, pages 327-338. Springer, 2014. URL: https://doi.org/10.1007/978-3-319-04298-5_29.
  27. Klaus Jansen and Malin Rau. Closing the gap for pseudo-polynomial strip packing. In ESA, volume 144, pages 62:1-62:14, 2019. Google Scholar
  28. Klaus Jansen and Roberto Solis-Oba. Rectangle packing with one-dimensional resource augmentation. Discret. Optim., 6(3):310-323, 2009. URL: https://doi.org/10.1016/j.disopt.2009.04.001.
  29. Klaus Jansen and Ralf Thöle. Approximation algorithms for scheduling parallel jobs. SIAM J. Comput., 39(8):3571-3615, 2010. URL: https://doi.org/10.1137/080736491.
  30. Klaus Jansen and Guochuan Zhang. Maximizing the total profit of rectangles packed into a rectangle. Algorithmica, 47(3):323-342, 2007. URL: https://doi.org/10.1007/s00453-006-0194-5.
  31. Edward G. Coffman Jr., M. R. Garey, David S. Johnson, and Robert Endre Tarjan. Performance bounds for level-oriented two-dimensional packing algorithms. SIAM J. Comput., 9(4):808-826, 1980. URL: https://doi.org/10.1137/0209062.
  32. Mohammad M Karbasioun, Gennady Shaikhet, Ioannis Lambadaris, and Evangelos Kranakis. Asymptotically optimal scheduling of random malleable demands in smart grid. Discrete Mathematics, Algorithms and Applications, 10(02):1850025, 2018. Google Scholar
  33. Narendra Karmarkar and Richard M. Karp. An efficient approximation scheme for the one-dimensional bin-packing problem. In 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, 3-5 November 1982, pages 312-320. IEEE Computer Society, 1982. Google Scholar
  34. Claire Kenyon and Eric Rémila. A near-optimal solution to a two-dimensional cutting stock problem. Math. Oper. Res., 25(4):645-656, 2000. URL: https://doi.org/10.1287/moor.25.4.645.12118.
  35. Arindam Khan, Arnab Maiti, Amatya Sharma, and Andreas Wiese. On guillotine separable packings for the two-dimensional geometric knapsack problem. In SoCG, pages 48:1-48:17, 2021. Google Scholar
  36. Arindam Khan and Madhusudhan Reddy Pittu. On guillotine separability of squares and rectangles. In APPROX, pages 47:1-47:22, 2020. Google Scholar
  37. Fu-Hong Liu, Hsiang-Hsuan Liu, and Prudence WH Wong. Optimal nonpreemptive scheduling in a smart grid model. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  38. Tobias Mömke and Andreas Wiese. Breaking the barrier of 2 for the storage allocation problem. In ICALP, pages 86:1-86:19, 2020. Google Scholar
  39. Giorgi Nadiradze and Andreas Wiese. On approximating strip packing with a better ratio than 3/2. In 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.
  40. Anshu Ranjan, Pramod Khargonekar, and Sartaj Sahni. Offline preemptive scheduling of power demands to minimize peak power in smart grids. In 2014 IEEE Symposium on Computers and Communications (ISCC), pages 1-6. IEEE, 2014. Google Scholar
  41. Anshu Ranjan, Pramod Khargonekar, and Sartaj Sahni. Offline first fit scheduling in smart grids. In 2015 IEEE Symposium on Computers and Communication (ISCC), pages 758-763. IEEE, 2015. Google Scholar
  42. Anshu Ranjan, Pramod Khargonekar, and Sartaj Sahni. Smart grid power scheduling via bottom left decreasing height packing. In 2016 IEEE Symposium on Computers and Communication (ISCC), pages 1128-1133. IEEE, 2016. Google Scholar
  43. Malin Rau. Useful Structures and How to Find Them: Hardness and Approximation Results for Various Variants of the Parallel Task Scheduling Problem. dissertation, Kiel University, Kiel, Germany, 2019. Google Scholar
  44. Ingo Schiermeyer. Reverse-fit: A 2-optimal algorithm for packing rectangles. In Jan van Leeuwen, editor, Algorithms - ESA '94, Second Annual European Symposium, Utrecht, The Netherlands, September 26-28, 1994, Proceedings, volume 855 of Lecture Notes in Computer Science, pages 290-299. Springer, 1994. URL: https://doi.org/10.1007/BFb0049416.
  45. Pierluigi Siano. Demand response and smart grids—a survey. Renewable and sustainable energy reviews, 30:461-478, 2014. Google Scholar
  46. Daniel Dominic Sleator. A 2.5 times optimal algorithm for packing in two dimensions. Inf. Process. Lett., 10(1):37-40, 1980. URL: https://doi.org/10.1016/0020-0190(80)90121-0.
  47. A. Steinberg. A strip-packing algorithm with absolute performance bound 2. SIAM J. Comput., 26(2):401-409, 1997. URL: https://doi.org/10.1137/S0097539793255801.
  48. Shaojie Tang, Qiuyuan Huang, Xiang-Yang Li, and Dapeng Wu. Smoothing the energy consumption: Peak demand reduction in smart grid. In 32nd IEEE International Conference on Computer Communications (INFOCOM), pages 1133-1141. IEEE, 2013. URL: https://doi.org/10.1109/INFCOM.2013.6566904.
  49. 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. 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 Imprint Privacy Contact