Scheduling algorithms for saving energy and balancing load

In this thesis we study problems of scheduling tasks in computing environments. We consider both the modern objective function of minimizing energy consumption, and the classical objective of balancing load across machines. We first investigate offline deadline-based scheduling in the setting of a single variable-speed processor that is equipped with a sleep state. The objective is that of minimizing the total energy consumption. Apart from settling the complexity of the problem by showing its NP-hardness, we provide a lower bound of 2 for general convex power functions, and a particular natural class of schedules called scrit-schedules. We also present an algorithmic framework for designing good approximation algorithms. For general convex power functions our framework improves the best known approximation-factor from 2 to 4/3. This factor can be reduced even further to 137/117 for a specific well-motivated class of power functions. Furthermore, we give tight bounds to show that our framework returns optimal scrit-schedules for the two aforementioned power-function classes. We then focus on the multiprocessor setting where each processor has the ability to vary its speed. Job migration is allowed, and we again consider classical deadline-based scheduling with the objective of energy minimization. We first study the offline problem and show that optimal schedules can be computed efficiently in polynomial time for any convex and non-decreasing power function. Our algorithm relies on repeated maximum flow computations. Regarding the online problem and power functions P(s) = s α , where s is the processor speed and α > 1 a constant, we extend the two well-known single-processor algorithms Optimal Available and Average Rate. We prove that Optimal Available is α α -competitive as in the single-processor case. For Average Rate we show a competitive factor of (2α) α/2 + 1, i.e., compared to the single-processor result the competitive factor increases by an additive constant of 1. With respect to load balancing, we consider offline load balancing on identical machines, with the objective of minimizing the current load, for temporary unit-weight jobs. The problem can be seen as coloring n intervals with k colors, such that for each point on the line, the maximal difference between the number of intervals of any two colors is minimal. We prove that a coloring with maximal difference at most one is always possible, and develop a fast polynomial-time algorithm for generating such a coloring. Regarding the online version of the problem, we show that the maximal difference in the size of color classes can become arbitrary high for any online algorithm. Lastly, we prove that two generalizations of the problem are NP-hard. In the first we generalize from intervals to d-dimensional boxes while in the second we consider multiple-intervals, i.e., specific subsets of disjoint intervals must receive the same color.