On Cloud Assisted, Restricted, and Resource Constrained Scheduling / submitted by Simon Pukrop ; [Reviewers Prof. Dr. Friedhelm Meyer auf der Heide; Paderborn University, Prof. Dr. Klaus Jansen; Kiel University]. Paderborn, 2023
Inhalt
- 1 Introduction
- 1.1 What is Scheduling, and Why Bother?
- 1.2 On Problems, Languages, and Efficient Encodings
- 1.3 P vs. NP and NP-Hardness
- 1.4 Approximation Algorithms and Schemes
- 1.5 Formal Scheduling Notation
- 1.6 Contents of this Thesis
- 2 Server Cloud Scheduling
- 2.1 Introduction
- 2.2 Chains and Fully Parallel Task Graphs
- 2.3 The Extended Chain Model (SCS e)
- 2.3.1 A Preliminary Problem: Single Machine Weighted Number of Tardy Jobs
- 2.3.2 Strong NP-Hardness of Scheduling Extended Chains
- 2.3.3 A (2+)-approximation (Makespan) on the Extended Chain
- 2.3.4 Cases with FPTAS
- 2.4 Constant Cardinality Source and Sink Dividing Cut (SCS )
- 2.5 Strong NP-Hardness
- 2.5.1 No Delays and Two Sizes
- 2.5.2 Unit Size and Unit Delay (SCS 1)
- 2.5.3 Inapproximability of the General Case
- 2.6 Algorithms for SCS 1 and Instances Without Delays
- 2.6.1 A 3-Approximation (Makespan) for SCS 1
- 2.6.2 A 1+2-Approximation (Cost) for SCS 1 with Resource Augmentation
- 2.6.3 A 2-Approximation (Makespan) on Identical Machines and no Delays
- 2.7 Generalizations of Server Cloud Scheduling
- 2.8 Approximating the Pareto Front
- 2.9 Future Work
- 3 Restricted Assignment Interval
- 3.1 Introduction
- 3.1.1 Problem Definition
- 3.1.2 Relation Between the Models and the State of the Art
- 3.1.3 Our Results
- 3.1.4 Further Related Work
- 3.2 A (2-124)-Approximation
- 3.2.1 Preliminaries.
- 3.2.2 Linear Program.
- 3.2.3 Integrality Gap of the Linear Program
- 3.2.4 The Rounding Algorithm.
- 3.3 A Summary of Our Complexity Results
- 3.4 Future Work
- 4 Many Shared Resources
- 4.1 Introduction
- 4.1.1 Problem Definition
- 4.1.2 State of the Art and Motivation
- 4.1.3 Our Results
- 4.1.4 Further Related Work
- 4.1.5 Preliminaries
- 4.2 A 5/3-approximation
- 4.3 A 3/2-approximation
- 4.4 A Summary of Our Work on Approximation Schemes
- 4.5 Inapproximability Results
- 4.6 Future Work
- Bibliography