License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2022.77
URN: urn:nbn:de:0030-drops-170152
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17015/
Maack, Marten ;
Pukrop, Simon ;
Rasmussen, Anna Rodriguez
(In-)Approximability Results for Interval, Resource Restricted, and Low Rank Scheduling
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.
BibTeX - Entry
@InProceedings{maack_et_al:LIPIcs.ESA.2022.77,
author = {Maack, Marten and Pukrop, Simon and Rasmussen, Anna Rodriguez},
title = {{(In-)Approximability Results for Interval, Resource Restricted, and Low Rank Scheduling}},
booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)},
pages = {77:1--77:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-247-1},
ISSN = {1868-8969},
year = {2022},
volume = {244},
editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17015},
URN = {urn:nbn:de:0030-drops-170152},
doi = {10.4230/LIPIcs.ESA.2022.77},
annote = {Keywords: Scheduling, Restricted Assignment, Approximation, Inapproximability}
}
|
Keywords: |
|
Scheduling, Restricted Assignment, Approximation, Inapproximability |
|
Collection: |
|
30th Annual European Symposium on Algorithms (ESA 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
01.09.2022 |
