Document Open Access Logo

Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines

Authors Martin Koutecký , Johannes Zink

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2020.18.pdf
  • Filesize: 0.69 MB
  • 17 pages

Document Identifiers

Author Details

Martin Koutecký
  • Computer Science Institute, Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic
Johannes Zink
  • Institut für Informatik, Universität Würzburg, Germany

Funding

  • Koutecký, Martin: M. Koutecký was partially supported by Charles University project UNCE/SCI/004, by the project 19-27871X of GA ČR, and by an Israel Science Foundation grant 308/18.

Acknowledgements

We thank the organizers of the HOMONOLO 2019 workshop for providing a warm and stimulating research environment, which gave birth to the initial ideas of this paper. We also thank the anonymous reviewers for their helpful remarks.

Cite As Get BibTex

Martin Koutecký and Johannes Zink. Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ISAAC.2020.18

Abstract

The task of scheduling jobs to machines while minimizing the total makespan, the sum of weighted completion times, or a norm of the load vector, are among the oldest and most fundamental tasks in combinatorial optimization. Since all of these problems are in general NP-hard, much attention has been given to the regime where there is only a small number k of job types, but possibly the number of jobs n is large; this is the few job types, high-multiplicity regime. Despite many positive results, the hardness boundary of this regime was not understood until now.
We show that makespan minimization on uniformly related machines (Q|HM|C_max) is NP-hard already with 6 job types, and that the related Cutting Stock problem is NP-hard already with 8 item types. For the more general unrelated machines model (R|HM|C_max), we show that if either the largest job size p_max, or the number of jobs n are polynomially bounded in the instance size |I|, there are algorithms with complexity |I|^poly(k). Our main result is that this is unlikely to be improved, because Q||C_max is W[1]-hard parameterized by k already when n, p_max, and the numbers describing the speeds are polynomial in |I|; the same holds for R|HM|C_max (without speeds) when the job sizes matrix has rank 2. Our positive and negative results also extend to the objectives 𝓁₂-norm minimization of the load vector and, partially, sum of weighted completion times ∑ w_j C_j.
Along the way, we answer affirmatively the question whether makespan minimization on identical machines (P||C_max) is fixed-parameter tractable parameterized by k, extending our understanding of this fundamental problem. Together with our hardness results for Q||C_max this implies that the complexity of P|HM|C_max is the only remaining open case.

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
  • Theory of computation → Scheduling algorithms
Keywords
  • Scheduling
  • cutting stock
  • hardness
  • parameterized complexity

Metrics

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

Related Versions

References

  1. Aditya Bhaskara, Ravishankar Krishnaswamy, Kunal Talwar, and Udi Wieder. Minimum makespan scheduling with low rank processing times. In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 937-947. SIAM, 2013. Google Scholar
  2. Lin Chen, Klaus Jansen, and Guochuan Zhang. On the optimality of exact and approximation algorithms for scheduling problems. Journal of Computer and System Sciences, 96:1-32, 2018. Google Scholar
  3. Lin Chen, Dániel Marx, Deshi Ye, and Guochuan Zhang. Parameterized and approximation results for scheduling with a low rank processing time matrix. In Heribert Vollmer and Brigitte Vallée, editors, 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, March 8-11, 2017, Hannover, Germany, volume 66 of LIPIcs, pages 22:1-22:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.STACS.2017.22.
  4. Michele Conforti, Gérard Cornuéjols, Giacomo Zambelli, et al. Integer programming, volume 271. Springer, 2014. Google Scholar
  5. Jana Cslovjecsek, Friedrich Eisenbrand, and Robert Weismantel. N-fold integer programming via LP rounding. arXiv preprint, 2020. URL: http://arxiv.org/abs/2002.07745.
  6. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  7. Friedrich Eisenbrand, Christoph Hunkenschröder, Kim-Manuel Klein, Martin Koutecký, Asaf Levin, and Shmuel Onn. An algorithmic theory of integer programming. CoRR, 2019. URL: http://arxiv.org/abs/1904.01361.
  8. András Frank and Éva Tardos. An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica, 7(1):49-65, 1987. Google Scholar
  9. P. C. Gilmore and R. E. Gomory. A linear programming approach to the cutting-stock problem. Oper. Res., 9:849-859, 1961. Google Scholar
  10. Michel X. Goemans and Thomas Rothvoß. Polynomiality for bin packing with a constant number of item types. In Proc. SODA 2014, pages 830-839, 2014. Google Scholar
  11. Danny Hermelin, Shlomo Karhi, Michael Pinedo, and Dvir Shabtay. New algorithms for minimizing the weighted number of tardy jobs on a single machine. Annals of Operations Research, pages 1-17, 2018. Google Scholar
  12. Danny Hermelin, Matthias Mnich, and Simon Omlor. Single machine batch scheduling to minimize the weighted number of tardy jobs. arXiv preprint, 2019. URL: http://arxiv.org/abs/1911.12350.
  13. Danny Hermelin, Michael Pinedo, Dvir Shabtay, and Nimrod Talmon. On the parameterized tractability of single machine scheduling with rejection. European Journal of Operational Research, 273(1):67-73, 2019. Google Scholar
  14. Klaus Jansen. New algorithmic results for bin packing and scheduling. In Dimitris Fotakis, Aris Pagourtzis, and Vangelis Th. Paschos, editors, Algorithms and Complexity, pages 10-15, Cham, 2017. Springer International Publishing. Google Scholar
  15. Klaus Jansen and Kim-Manuel Klein. About the structure of the integer cone and its application to bin packing. In Proc. SODA 2017, pages 1571-1581, 2017. Google Scholar
  16. Klaus Jansen, Kim-Manuel Klein, Marten Maack, and Malin Rau. Empowering the configuration-IP-new PTAS results for scheduling with setups times. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  17. Klaus Jansen, Stefan Kratsch, Dániel Marx, and Ildikó Schlotter. Bin packing with fixed number of bins revisited. Journal of Computer and System Sciences, 79(1):39-49, 2013. Google Scholar
  18. Klaus Jansen, Alexandra Lassota, and Marten Maack. Approximation algorithms for scheduling with class constraints. arXiv preprint, 2019. URL: http://arxiv.org/abs/1909.11970.
  19. Klaus Jansen, Alexandra Lassota, and Lars Rohwedder. Near-linear time algorithm for n-fold ILPs via color coding. arXiv preprint, 2018. URL: http://arxiv.org/abs/1811.00950.
  20. Dušan Knop and Martin Koutecký. Scheduling meets n-fold integer programming. Journal of Scheduling, 21:493-503, 2018. Google Scholar
  21. Dusan Knop and Martin Koutecký. Scheduling kernels via configuration LP. CoRR, abs/2003.02187, 2020. URL: http://arxiv.org/abs/2003.02187.
  22. Dušan Knop, Martin Koutecký, Asaf Levin, Matthias Mnich, and Shmuel Onn. Multitype integer monoid optimization and applications. arXiv preprint, 2019. URL: http://arxiv.org/abs/1909.07326.
  23. Eugene L. Lawler, Jan Karel Lenstra, Alexander H. G. Rinnooy Kan, and David B. Shmoys. Sequencing and scheduling: Algorithms and complexity. In S. C. Graves, A. H. G. Rinnooy Kan, and P. H. Zipkin, editors, Handbooks in Operations Research and Management Science: Logistics of Production and Inventory, volume 4, pages 445-522, Amsterdam-London-New York-Tokyo, 1993. North-Holland Publishing Company. Google Scholar
  24. Asaf Levin. Approximation schemes for the generalized extensible bin packing problem. arXiv preprint, 2019. URL: http://arxiv.org/abs/1905.09750.
  25. Matthias Mnich and René van Bevern. Parameterized complexity of machine scheduling: 15 open problems. Computers & OR, 100:254-261, 2018. Google Scholar
  26. Matthias Mnich and Andreas Wiese. Scheduling and fixed-parameter tractability. Mathematical Programming, 154(1-2):533-562, 2015. Google Scholar
  27. Wayne E. Smith. Various optimizers for single-stage production. Naval Res. Logist. Quart., 3:59-66, 1956. 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 About DROPS Imprint Privacy Contact