[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Complexity and Inapproximability Results for Parallel Task Scheduling and Strip Packing

  • Published:
Theory of Computing Systems Aims and scope Submit manuscript

Abstract

We study Parallel Task Scheduling Pm|sizej|Cmax with a constant number of machines. This problem is known to be strongly NP-complete for each m ≥ 5, while it is solvable in pseudo-polynomial time for each m ≤ 3. We give a positive answer to the long-standing open question whether this problem is strongly NP-complete for m = 4. As a second result, we improve the lower bound of \(\frac {12}{11}\) for approximating pseudo-polynomial Strip Packing to \(\frac {5}{4}\). Since the best known approximation algorithm for this problem has a ratio of \(\frac {5}{4} + \varepsilon \), this result almost closes the gap between approximation ratio and inapproximability result. Both results are proved by a reduction from the strongly NP-complete problem 3-Partition.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

References

  1. Adamaszek, A., Kociumaka, T., Pilipczuk, M., Pilipczuk, M.: Hardness of approximation for strip packing. TOCT 9(3), 14,1–14,7 (2017). https://doi.org/10.1145/3092026

    Article  MathSciNet  MATH  Google Scholar 

  2. Amoura, A.K., Bampis, E., Kenyon, C., Manoussakis, Y.: Scheduling independent multiprocessor tasks. Algorithmica 32(2), 247–261 (2002). https://doi.org/10.1007/s00453-001-0076-9

    Article  MathSciNet  MATH  Google Scholar 

  3. Baker, B.S., Brown, D.J., Howard, P.K.: 5/4 algorithm for two-dimensional packing. J. Algor. 2(4), 348–368 (1981). https://doi.org/10.1016/0196-6774(81)90034-1

    Article  MathSciNet  MATH  Google Scholar 

  4. Baker, B.S., Coffman, E.G. Jr., Rivest, R.L.: Orthogonal packings in two dimensions. SIAM J. Comput. 9(4), 846–855 (1980). https://doi.org/10.1137/0209064

    Article  MathSciNet  MATH  Google Scholar 

  5. Bansal, N., Correa, J/R., Kenyon, C., Sviridenko, M.: Bin packing in multiple dimensions Inapproximability results and approximation schemes. Math. Oper. Res. 31(1), 31–49 (2006). https://doi.org/10.1287/moor.1050.0168 https://doi.org/10.1287/moor.1050.0168

    Article  MathSciNet  Google Scholar 

  6. Bougeret, M., Dutot, P.-F., Jansen, K., Robenek, C., Trystram, D.: Approximation algorithms for multiple strip packing and scheduling parallel jobs in platforms. Discret. Math. Algor. Appl. 3(4), 553–586 (2011). https://doi.org/10.1142/S1793830911001413

    Article  MathSciNet  MATH  Google Scholar 

  7. Christensen, H.I., Khan, A., Pokutta, S., Tetali, P.: Approximation and online algorithms for multidimensional bin packing: A survey. Computer Science Review. https://doi.org/10.1016/j.cosrev.2016.12.001 (2017)

    Article  MathSciNet  Google Scholar 

  8. Coffman, E.G. Jr., Garey, M.R., Johnson, D.S., Tarjan, R.E.: Performance bounds for level-oriented two-dimensional packing algorithms. SIAM J. Comput. 9(4), 808–826 (1980). https://doi.org/10.1137/0209062

    Article  MathSciNet  Google Scholar 

  9. Jianzhong, D, Leung, J.Y.-T.: Complexity of scheduling parallel task systems. SIAM J. Discret. Math. 2(4), 473–487 (1989). https://doi.org/10.1137/0402042

    Article  MathSciNet  MATH  Google Scholar 

  10. Feldmann, A., Sgall, J., Teng, S.-H.: Dynamic scheduling on parallel machines. Theor. Comput. Sci. 130(1), 49–72 (1994). https://doi.org/10.1016/0304-3975(94)90152-X

    Article  MathSciNet  MATH  Google Scholar 

  11. Gȧlvez, W., Grandoni, F., Ingala, S., Khan, A.: Improved pseudo-polynomial-time approximation for strip packing. In: 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pp. 9:1–9:14. https://doi.org/10.4230/LIPIcs.FSTTCS.2016.9 (2016)

  12. Garey, M.R., Graham, R.L.: Bounds for multiprocessor scheduling with resource constraints. SIAM J. Comput. 4(2), 187–200 (1975). https://doi.org/10.1137/0204015

    Article  MathSciNet  MATH  Google Scholar 

  13. Garey, M.R., Johnson, D.S.: Computers and Intractability: A guide to the theory of NP-completeness (1979)

  14. Golan, I.: Performance bounds for orthogonal oriented two-dimensional packing algorithms. SIAM J. Comput. 10(3), 571–582 (1981). https://doi.org/10.1137/0210042

    Article  MathSciNet  MATH  Google Scholar 

  15. Harren, R., Jansen, K., Prȧdel, L., Rob van, S.: A (5/3 + 𝜖)-approximation for strip packing. Comput. Geom. 47 (2), 248–267 (2014). https://doi.org/10.1016/j.comgeo.2013.08.008

    Article  MathSciNet  MATH  Google Scholar 

  16. Harren, R, van Stee, R.: 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, pp 177–189. Springer (2009), https://doi.org/10.1007/978-3-642-03685-9_14

    Chapter  Google Scholar 

  17. Jansen, K.: A (3/2+) approximation algorithm for scheduling moldable and non-moldable parallel tasks. In: 24th ACM Symposium on Parallelism in Algorithms and Architectures, (SPAA), pp. 224–235. https://doi.org/10.1145/2312005.2312048 (2012)

  18. Jansen, K., Land, F.: 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, pp. 172–181. https://doi.org/10.1109/IPDPS.2018.00027 (2018)

  19. Jansen, K., Porkolab, L.: Linear-time approximation schemes for scheduling malleable parallel tasks. Algorithmica 32(3), 507–520 (2002). https://doi.org/10.1007/s00453-001-0085-8

    Article  MathSciNet  MATH  Google Scholar 

  20. Jansen, K., Rau, M.: Closing the gap for pseudo-polynomial strip packing. arXiv:1712.04922 (2017)

  21. Jansen, K., Rau, M.: Improved approximation for two dimensional strip packing with polynomial bounded width. In: WALCOM: Algorithms and Computation, Volume 10167 of LNCS, pp. 409–420. https://doi.org/10.1007/978-3-319-53925-6_32 (2017)

    Chapter  Google Scholar 

  22. Jansen, K., Solis-Oba, R.: Rectangle packing with one-dimensional resource augmentation. Discret. Optim. 6(3), 310–323 (2009). https://doi.org/10.1016/j.disopt.2009.04.001

    Article  MathSciNet  MATH  Google Scholar 

  23. Jansen, K., Thȯle, R.: Approximation algorithms for scheduling parallel jobs. SIAM J. Comput. 39(8), 3571–3615 (2010). https://doi.org/10.1137/080736491

    Article  MathSciNet  MATH  Google Scholar 

  24. Kenyon, C., Rėmila, E.: A near-optimal solution to a two-dimensional cutting stock problem. Math. Oper. Res. 25(4), 645–656 (2000). https://doi.org/10.1287/moor.25.4.645.12118

    Article  MathSciNet  MATH  Google Scholar 

  25. Ludwig, W., Tiwari, P.: Scheduling malleable and nonmalleable parallel tasks. In: 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 167–176 (1994)

  26. Nadiradze, G., Wiese, A.: On approximating strip packing with a better ratio than 3/2. In: 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1491–1510. https://doi.org/10.1137/1.9781611974331.ch102 https://doi.org/10.1137/1.9781611974331.ch102 (2016)

  27. Schiermeyer, I: Reverse-fit: A 2-optimal algorithm for packing rectangles. In: 2nd Annual European Symposium on Algorithms (ESA) - Algorithms, pp. 290–299. https://doi.org/10.1007/BFb0049416 (1994)

    Chapter  Google Scholar 

  28. Sleator, D.D.: A 2.5 times optimal algorithm for packing in two dimensions. Inf. Process. Lett. 10(1), 37–40 (1980). https://doi.org/10.1016/0020-0190(80)90121-0

    Article  MathSciNet  MATH  Google Scholar 

  29. Steinberg, A.: A strip-packing algorithm with absolute performance bound 2. SIAM J. Comput. 26 (2), 401–409 (1997). https://doi.org/10.1137/S0097539793255801

    Article  MathSciNet  MATH  Google Scholar 

  30. Sviridenko, M.: A note on the kenyon-remila strip-packing algorithm. Inf. Process. Lett. 112(1-2), 10–12 (2012). https://doi.org/10.1016/j.ipl.2011.10.003

    Article  MathSciNet  MATH  Google Scholar 

  31. Turek, J., Wolf, J.L., Philip, S.: Approximate algorithms scheduling parallelizable tasks. In: 4th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 323–332. https://doi.org/10.1145/140901.141909 (1992)

Download references

Acknowledgements

The authors would like to thank the anonymous reviewers for their valuable comments and suggestions to improve the quality of the paper. This work was supported by German Research Foundation (DFG) project JA 612 /20-1.

Author information

Authors and Affiliations

  1. Institut für Informatik, Christian-Albrechts-Universität zu Kiel, Kiel, Germany

    Sören Henning, Klaus Jansen, Malin Rau & Lars Schmarje

Authors
  1. Sören Henning
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Klaus Jansen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Malin Rau
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Lars Schmarje
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Malin Rau.

Additional information

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This article is part of the Topical Collection on Computer Science Symposium in Russia (2018)

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

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Henning, S., Jansen, K., Rau, M. et al. Complexity and Inapproximability Results for Parallel Task Scheduling and Strip Packing. Theory Comput Syst 64, 120–140 (2020). https://doi.org/10.1007/s00224-019-09910-6

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00224-019-09910-6

Keywords

Search

Navigation