License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2020.5
URN: urn:nbn:de:0030-drops-118663
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11866/
Maack, Marten ;
Jansen, Klaus
Inapproximability Results for Scheduling with Interval and Resource Restrictions
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.
BibTeX - Entry
@InProceedings{maack_et_al:LIPIcs:2020:11866,
author = {Marten Maack and Klaus Jansen},
title = {{Inapproximability Results for Scheduling with Interval and Resource Restrictions}},
booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
pages = {5:1--5:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-140-5},
ISSN = {1868-8969},
year = {2020},
volume = {154},
editor = {Christophe Paul and Markus Bl{\"a}ser},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11866},
URN = {urn:nbn:de:0030-drops-118663},
doi = {10.4230/LIPIcs.STACS.2020.5},
annote = {Keywords: Scheduling, Restricted Assignment, Approximation, Inapproximability, PTAS}
}
|
Keywords: |
|
Scheduling, Restricted Assignment, Approximation, Inapproximability, PTAS |
|
Collection: |
|
37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
04.03.2020 |
