Document Open Access Logo

Inapproximability Results for Scheduling with Interval and Resource Restrictions

Authors Marten Maack , Klaus Jansen

PDF
Thumbnail PDF

File

LIPIcs.STACS.2020.5.pdf
  • Filesize: 0.54 MB
  • 18 pages

Document Identifiers

Author Details

Marten Maack
  • Department of Computer Science, Kiel University, Kiel, Germany
Klaus Jansen
  • Department of Computer Science, Kiel University, Kiel, Germany

Funding

  • Maack, Marten: German Academic Exchange Service (DAAD) scholarship
  • Jansen, Klaus: German Research Foundation (DFG) project JA 612/15-2

Acknowledgements

We thank Malin Rau and Lars Rohwedder for helpfull discussions on the problem.

Cite As Get BibTex

Marten Maack and Klaus Jansen. Inapproximability Results for Scheduling with Interval and Resource Restrictions. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 5:1-5:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.STACS.2020.5

Abstract

In the restricted assignment problem, the input consists of a set of machines and a set of jobs each with a processing time and a subset of eligible machines. The goal is to find an assignment of the jobs to the machines minimizing the makespan, that is, the maximum summed up processing time any machine receives. Herein, jobs should only be assigned to those machines on which they are eligible. It is well-known that there is no polynomial time approximation algorithm with an approximation guarantee of less than 1.5 for the restricted assignment problem unless P=NP. In this work, we show hardness results for variants of the restricted assignment problem with particular types of restrictions.
For the case of interval restrictions - where the machines can be totally ordered such that jobs are eligible on consecutive machines - we show that there is no polynomial time approximation scheme (PTAS) unless P=NP. The question of whether a PTAS for this variant exists was stated as an open problem before, and PTAS results for special cases of this variant are known.
Furthermore, we consider a variant with resource restriction where the sets of eligible machines are of the following form: There is a fixed number of (renewable) resources, each machine has a capacity, and each job a demand for each resource. A job is eligible on a machine if its demand is at most as big as the capacity of the machine for each resource. For one resource, this problem has been intensively studied under several different names and is known to admit a PTAS, and for two resources the variant with interval restrictions is contained as a special case. Moreover, the version with multiple resources is closely related to makespan minimization on parallel machines with a low rank processing time matrix. We show that there is no polynomial time approximation algorithm with a rate smaller than 48/47 ≈ 1.02 or 1.5 for scheduling with resource restrictions with 2 or 4 resources, respectively, unless P=NP. All our results can be extended to the so called Santa Claus variants of the problems where the goal is to maximize the minimal processing time any machine receives.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Scheduling algorithms
Keywords
  • Scheduling
  • Restricted Assignment
  • Approximation
  • Inapproximability
  • PTAS

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, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 937-947, 2013. URL: https://doi.org/10.1137/1.9781611973105.67.
  2. Andreas Brandstädt and Vadim V. Lozin. On the linear structure and clique-width of bipartite permutation graphs. Ars Comb., 67, 2003. Google Scholar
  3. Deeparnab Chakrabarty and Kirankumar Shiragur. Graph balancing with two edge types. CoRR, abs/1604.06918, 2016. URL: http://arxiv.org/abs/1604.06918.
  4. Lin Chen, Klaus Jansen, and Guochuan Zhang. On the optimality of exact and approximation algorithms for scheduling problems. J. Comput. Syst. Sci., 96:1-32, 2018. URL: https://doi.org/10.1016/j.jcss.2018.03.005.
  5. Lin Chen, Dániel Marx, Deshi Ye, and Guochuan Zhang. Parameterized and approximation results for scheduling with a low rank processing time matrix. In 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, March 8-11, 2017, Hannover, Germany, pages 22:1-22:14, 2017. URL: https://doi.org/10.4230/LIPIcs.STACS.2017.22.
  6. Lin Chen, Deshi Ye, and Guochuan Zhang. An improved lower bound for rank four scheduling. Oper. Res. Lett., 42(5):348-350, 2014. URL: https://doi.org/10.1016/j.orl.2014.06.003.
  7. Tomás Ebenlendr, Marek Krcál, and Jirí Sgall. Graph balancing: A special case of scheduling unrelated parallel machines. Algorithmica, 68(1):62-80, 2014. URL: https://doi.org/10.1007/s00453-012-9668-9.
  8. Leah Epstein and Asaf Levin. Scheduling with processing set restrictions: Ptas results for several variants. International Journal of Production Economics, 133(2):586-595, 2011. URL: https://doi.org/10.1016/j.ijpe.2011.04.024.
  9. Pinar Heggernes and Dieter Kratsch. Linear-time certifying recognition algorithms and forbidden induced subgraphs. Nord. J. Comput., 14(1-2):87-108, 2007. Google Scholar
  10. Dorit S. Hochbaum and David B. Shmoys. Using dual approximation algorithms for scheduling problems theoretical and practical results. J. ACM, 34(1):144-162, 1987. URL: https://doi.org/10.1145/7531.7535.
  11. Ellis Horowitz and Sartaj Sahni. Exact and approximate algorithms for scheduling nonidentical processors. J. ACM, 23(2):317-327, 1976. URL: https://doi.org/10.1145/321941.321951.
  12. Chien-Chung Huang and Sebastian Ott. A combinatorial approximation algorithm for graph balancing with light hyper edges. In 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, pages 49:1-49:15, 2016. URL: https://doi.org/10.4230/LIPIcs.ESA.2016.49.
  13. Klaus Jansen, Marten Maack, and Roberto Solis-Oba. Structural parameters for scheduling with assignment restrictions. In Algorithms and Complexity - 10th International Conference, CIAC 2017, Athens, Greece, May 24-26, 2017, Proceedings, pages 357-368, 2017. URL: https://doi.org/10.1007/978-3-319-57586-5_30.
  14. Klaus Jansen and Lars Rohwedder. Local search breaks 1.75 for graph balancing. CoRR, abs/1811.00955, 2018. URL: http://arxiv.org/abs/1811.00955.
  15. Kamyar Khodamoradi. Algorithms for Scheduling and Routing Problems. PhD thesis, Simon Fraser University, 2016. Google Scholar
  16. Kamyar Khodamoradi, Ramesh Krishnamurti, Arash Rafiey, and Georgios Stamoulis. PTAS for ordered instances of resource allocation problems. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2013, December 12-14, 2013, Guwahati, India, pages 461-473, 2013. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2013.461.
  17. Kamyar Khodamoradi, Ramesh Krishnamurti, Arash Rafiey, and Georgios Stamoulis. PTAS for ordered instances of resource allocation problems with restrictions on inclusions. CoRR, abs/1610.00082, 2016. URL: http://arxiv.org/abs/1610.00082.
  18. Kangbok Lee, Joseph Y.-T. Leung, and Michael L. Pinedo. Makespan minimization in online scheduling with machine eligibility. Annals OR, 204(1):189-222, 2013. URL: https://doi.org/10.1007/s10479-012-1271-6.
  19. Jan Karel Lenstra, David B. Shmoys, and Éva Tardos. Approximation algorithms for scheduling unrelated parallel machines. Math. Program., 46:259-271, 1990. URL: https://doi.org/10.1007/BF01585745.
  20. Joseph Y-T Leung and Chung-Lun Li. Scheduling with processing set restrictions: A survey. International Journal of Production Economics, 116(2):251-262, 2008. URL: https://doi.org/10.1016/j.ijpe.2008.09.003.
  21. Joseph Y-T Leung and Chung-Lun Li. Scheduling with processing set restrictions: A literature update. International Journal of Production Economics, 175:1-11, 2016. URL: https://doi.org/10.1016/j.ijpe.2014.09.038.
  22. Marten Maack and Klaus Jansen. Inapproximability results for scheduling with interval and resource restrictions. CoRR, abs/1907.03526, 2019. URL: http://arxiv.org/abs/1907.03526.
  23. Gabriella Muratore, Ulrich M. Schwarz, and Gerhard J. Woeginger. Parallel machine scheduling with nested job assignment restrictions. Oper. Res. Lett., 38(1):47-50, 2010. URL: https://doi.org/10.1016/j.orl.2009.09.010.
  24. Jinwen Ou, Joseph Y-T Leung, and Chung-Lun Li. Scheduling parallel machines with inclusive processing set restrictions. Naval Research Logistics (NRL), 55(4):328-338, 2008. URL: https://doi.org/10.1002/nav.20286.
  25. Thomas J. Schaefer. The complexity of satisfiability problems. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing, May 1-3, 1978, San Diego, California, USA, pages 216-226, 1978. URL: https://doi.org/10.1145/800133.804350.
  26. Petra Schuurman and Gerhard J Woeginger. Polynomial time approximation algorithms for machine scheduling: Ten open problems. Journal of Scheduling, 2(5):203-213, 1999. URL: https://doi.org/10.1002/(SICI)1099-1425(199909/10)2:5<203::AID-JOS26>3.0.CO;2-5.
  27. Ulrich M. Schwarz. Approximation algorithms for scheduling and two-dimensional packing problems. PhD thesis, University of Kiel, 2010. URL: http://eldiss.uni-kiel.de/macau/receive/dissertation_diss_00005147.
  28. Ulrich M. Schwarz. A PTAS for scheduling with tree assignment restrictions. CoRR, abs/1009.4529, 2010. URL: http://arxiv.org/abs/1009.4529.
  29. Georgios Stamoulis. Private communication, 2019. Google Scholar
  30. Ola Svensson. Santa claus schedules jobs on unrelated machines. SIAM J. Comput., 41(5):1318-1341, 2012. URL: https://doi.org/10.1137/110851201.
  31. Craig A. Tovey. A simplified np-complete satisfiability problem. Discrete Applied Mathematics, 8(1):85-89, 1984. URL: https://doi.org/10.1016/0166-218X(84)90081-7.
  32. Chao Wang and René Sitters. On some special cases of the restricted assignment problem. Inf. Process. Lett., 116(11):723-728, 2016. URL: https://doi.org/10.1016/j.ipl.2016.06.007.
  33. David P. Williamson and David B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011. URL: http://www.cambridge.org/de/knowledge/isbn/item5759340/?site_locale=de_DE.
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