Useful Structures and How to Find Them: Hardness and Approximation Results for Various Variants of the Parallel Task Scheduling Problem ; Nützliche Strukturen und wie sie zu finden sind: Nicht Approximierbarkeit und Approximationen für diverse Varianten des Parallel Task Scheduling Problems
You can manage bookmarks using lists, please log in to your user account for this.
Media type:
Text;
Doctoral Thesis;
Electronic Thesis;
E-Book
Title:
Useful Structures and How to Find Them: Hardness and Approximation Results for Various Variants of the Parallel Task Scheduling Problem ; Nützliche Strukturen und wie sie zu finden sind: Nicht Approximierbarkeit und Approximationen für diverse Varianten des Parallel Task Scheduling Problems
Contributor:
Rau, Malin
[Author]
Published:
MACAU: Open Access Repository of Kiel University, 2019
Footnote:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Description:
In this thesis, we consider the Parallel Task Scheduling problem and several variants. This problem and its variations have diverse applications in theory and practice; for example, they appear as sub-problems in higher dimensional problems. In the Parallel Task Scheduling problem, we are given a set of jobs and a set of identical machines. Each job is a parallel task; i.e., it needs a fixed number of identical machines to be processed. A schedule assigns to each job a set of machines it is processed on and a starting time. It is feasible if at each point in time each machine processes at most one job. In a variant of this problem, called Strip Packing, the identical machines are arranged in a total order, and jobs can only allocate neighboring machines with regard to this total order. In this case, we speak of Contiguous Parallel Task Scheduling as well. In another variant, called Single Resource Constraint Scheduling, we are given an additional constraint on how many jobs can be processed at the same time. For these variants of the Parallel Task Scheduling problem, we consider an extension, where the set of machines is grouped into identical clusters. When scheduling a job, we are allowed to allocate machines from only one cluster to process the job. For all these considered problems, we close some gaps between inapproximation or hardness result and the best possible algorithm. For Parallel Task Scheduling we prove that it is strongly NP-hard if we are given precisely 4 machines. Before it was known that it is strongly NP-hard if we are given at least 5 machines, and there was an (exact) pseudo-polynomial time algorithm for up to 3 machines. For Strip Packing, we present an algorithm with approximation ratio (5/4 +ε) and prove that there is no approximation with ratio less than 5/4 unless P = NP. Concerning Single Resource Constraint Scheduling, it is not possible to find an algorithm with ratio smaller than 3/2, unless P = NP, and we present an algorithm with ratio (3/2 +ε). For the extensions to identical ...