(In-)Approximability Results for Interval, Resource Restricted, and Low Rank Scheduling

Autor:	Maack, Marten, Pukrop, Simon, Rasmussen, Anna Rodriguez
Jazyk:	angličtina
Rok vydání:	2022
Předmět:	FOS: Computer and information sciences Scheduling Theory of computation → Scheduling algorithms Computer Science - Data Structures and Algorithms Restricted Assignment Theory of computation → Problems reductions and completeness Data Structures and Algorithms (cs.DS) Approximation Inapproximability
Popis:	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. LIPIcs, Vol. 244, 30th Annual European Symposium on Algorithms (ESA 2022), pages 77:1-77:13
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::316e063e8af93f9d64a44db2ed794d82 http://arxiv.org/abs/2203.06171 Zobrazit plný text záznamu