Scheduling with scarce resources / vorgelegt von Sören Riechers ; [Betreuer: Prof. Dr. Friedhelm Meyer auf der Heide (Universität Paderborn), Gutachter: Prof. Dr. Friedhelm Meyer auf der Heide (Universität Paderborn), Prof. Dr. Petra Berenbrink (Universität Hamburg), Weitere Mitglieder der Promotionskommission: Prof. Dr. Eyke Hüllermeier (Universität Paderborn), Jun.-Prof. Dr. Alexander Skopalik (Universität Paderborn), Dr. Ulf-Peter Schröder (Universität Paderborn)]. Paderborn, 2017
Content
- Preface
- Introduction
- Approximation and Online Algorithms
- Outline of the Thesis
- Overview of the Different Models
- Related Work
- Own Publications
- Assigning a Sharable Resource in a Multiprocessor System
- Preliminaries
- Model & Notation
- Contribution
- Graphical Representation
- Structural Properties
- Warm-up: Round Robin Approximation
- Problem Complexity
- Optimal Algorithms
- Balanced Schedules
- Scheduling with a Sharable Communication Channel
- Preliminaries
- Complexity
- Communication Graphs of Degree Two
- Communication Graphs with Arbitrary Degree
- Scheduling with a Sharable Resource
- Scheduling with a Bounded Speed Limit
- Preliminaries
- Balance for Optimality
- Scheduling via Variational Calculus
- Characterizing Optimal Solutions
- Extracting Structural Properties
- Exact Polynomial-Time Algorithm
- Conclusion & Outlook
- List of Figures
- Bibliography