Kling, Peter: Energy-efficient scheduling algorithms. 2014
Inhalt
- List of Theorems
- List of Figures
- List of Listings
- Preface
- Introduction
- Preliminaries
- Basics: Approximation & Online Algorithms
- The First Speed Scaling Model
- Survey of Relevant Speed Scaling Results
- Profitable Deadline Scheduling
- Related Work & Contribution
- Model & Preliminaries
- An Online Greedy Primal-Dual Algorithm
- Analysis
- Structure of an Optimal Infeasible Solution
- A Job-centric Formulation of the Dual Function
- Balancing the Different Cost Components
- Deriving the Tight Competitive Ratio
- Conclusion & Outlook
- Slow Down & Sleep for Profit
- Related Work & Contribution
- Model & Preliminaries
- Lower Bound for Rejection-Oblivious Algorithms
- Algorithm & Analysis
- The Speed-Bounded Case
- Conclusion & Outlook
- Trading Energy for Responsiveness
- Related Work & Contribution
- Model & Preliminaries
- Overview
- Structural Properties via Primal-Dual Formulation
- Computing an Optimal Schedule
- Correctness of the Algorithm
- The Running Time
- Conclusion & Outlook
- Sharing Scalable Resources
- Related Work & Contribution
- Model & Notation
- Preliminaries
- Problem Complexity
- Analysis of Balanced Schedules
- Lower Bounds for Optimal Schedules
- Deriving a (2-1/m)-Approximation
- Tight Approximation via a Greedy Algorithm
- Conclusion & Outlook
- Bibliography