Alexander Kononov

Abstract.  Scheduling problems has long been in the center of interest from the researchers in Computer Science, Business Analytics, Operations Research and Engineering due to a wide range of applications such as timetabling, transportation, air traffic control etc. The classical scheduling problems usually try to optimize various performance metrics such as schedule length (makespan), or number of jobs completed by their due date etc., subject to various capacity or resource constraints such as number of concurrent jobs that a processor can handle or bandwidth constraints.

In today's world, energy is one of the most important resources and energy conservation is a major concern today. It has been realized recently that energy is not just a regular resource similar to processor capacity. We address one of the main mechanisms for reducing the energy consumption in modern computer systems which is based on the use of speed scalable processors. This relatively new technique saves energy by utilizing the full speed/frequency spectrum of a processor and applying low speeds whenever possible. The dependence of energy consumption on performance of the system is highly non-linear and as a result new techniques to assign tasks to processors and execute them in the optimal or near-optimal manner are required.

We are given a set of jobs, each one specified by its release date, its deadline and its processing volume (work), and a single (or a set of) speed-scalable processor(s). We adopt the standard model in speed-scaling in which if a processor runs at speed s then the energy consumption is s^α per time unit, where α> 1. Our goal is to find a schedule respecting the release dates and the deadlines of the jobs so that the total energy consumption is minimized.

Dynamic speed scaling leads to many interesting complicated scheduling problems. At any time a scheduler has to decide not only which job to execute but also which speed to use. Consequently, there has been considerable research interest in the design and analysis of efficient scheduling algorithms. We survey recent research that has appeared in the theoretical computer science literature on algorithmic problems related to off-line energy-efficient scheduling problems.