LIPIcs.ESA.2022.77.pdf
- Filesize: 0.73 MB
- 13 pages
Document
(In-)Approximability Results for Interval, Resource Restricted, and Low Rank Scheduling
Authors
Marten Maack 
,
Simon Pukrop ,
-
Part of:
Volume:
30th Annual European Symposium on Algorithms (ESA 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: European Symposium on Algorithms (ESA) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-09-01
File
Document Identifiers
Author Details
- Heinz Nixdorf Institute & Department of Computer Science, Universität Paderborn, Germany
Cite As Get BibTex
Marten Maack, Simon Pukrop, and Anna Rodriguez Rasmussen. (In-)Approximability Results for Interval, Resource Restricted, and Low Rank Scheduling. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 77:1-77:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ESA.2022.77
Abstract
We consider variants of the restricted assignment problem where a set of jobs has to be assigned to a set of machines, for each job a size and a set of eligible machines is given, and the jobs may only be assigned to eligible machines with the goal of makespan minimization. For the variant with interval restrictions, where the machines can be arranged on a path such that each job is eligible on a subpath, we present the first better than 2-approximation and an improved inapproximability result. In particular, we give a (2-1/24)-approximation and show that no better than 9/8-approximation is possible, unless P=NP. Furthermore, we consider restricted assignment with R resource restrictions and rank D unrelated scheduling. In the former problem, a machine may process a job if it can meet its resource requirements regarding R (renewable) resources. In the latter, the size of a job is dependent on the machine it is assigned to and the corresponding processing time matrix has rank at most D. The problem with interval restrictions includes the 1 resource variant, is encompassed by the 2 resource variant, and regarding approximation the R resource variant is essentially a special case of the rank R+1 problem. We show that no better than 3/2, 8/7, and 3/2-approximation is possible (unless P=NP) for the 3 resource, 2 resource, and rank 3 variant, respectively. Both the approximation result for the interval case and the inapproximability result for the rank 3 variant are solutions to open challenges stated in previous works. Lastly, we also consider the reverse objective, that is, maximizing the minimal load any machine receives, and achieve similar results.
Subject Classification
ACM Subject Classification
- Theory of computation → Problems, reductions and completeness
- Theory of computation → Scheduling algorithms
Keywords
- Scheduling
- Restricted Assignment
- Approximation
- Inapproximability
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Aditya Bhaskara, Ravishankar Krishnaswamy, Kunal Talwar, and Udi Wieder. Minimum makespan scheduling with low rank processing times. In Sanjeev Khanna, editor, 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. SIAM, 2013. URL: https://doi.org/10.1137/1.9781611973105.67.
- Deeparnab Chakrabarty, Sanjeev Khanna, and Shi Li. On (1, ε)-restricted assignment makespan minimization. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1087-1101. SIAM, 2015. URL: https://doi.org/10.1137/1.9781611973730.73.
- 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.
- 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.
- 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.
- 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.
- 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.
- Klaus Jansen, Marten Maack, and Roberto Solis-Oba. Structural parameters for scheduling with assignment restrictions. Theor. Comput. Sci., 844:154-170, 2020. URL: https://doi.org/10.1016/j.tcs.2020.08.015.
- 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.
- 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.
- Chung-Lun Li and Xiuli Wang. Scheduling parallel machines with inclusive processing set restrictions and job release times. Eur. J. Oper. Res., 200(3):702-710, 2010. URL: https://doi.org/10.1016/j.ejor.2009.02.011.
- Marten Maack and Klaus Jansen. Inapproximability results for scheduling with interval and resource restrictions. In Christophe Paul and Markus Bläser, editors, 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, March 10-13, 2020, Montpellier, France, volume 154 of LIPIcs, pages 5:1-5:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.STACS.2020.5.
- Marten Maack, Simon Pukrop, and Anna Rodriguez Rasmussen. (in-)approximability results for interval, resource restricted, and low rank scheduling. CoRR, abs/2203.06171, 2022. URL: https://doi.org/10.48550/arXiv.2203.06171.
- 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.
- 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.
- 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.
- 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.
- 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.