Scheduling for energy minimization on restricted parallel processors

• We propose an optimal scheduling algorithm for the case when all of the tasks have uniform computational work.
• We present a polynomial-time algorithm that achieves a bounded approximation factor when the tasks have arbitrary-size work.
• We evaluate the performance of the approximation algorithm by a set of simulations.

Scheduling for energy conservation has become a major concern in the field of information technology because of the need to reduce energy use and carbon dioxide emissions. Previous work has focused on the assumption that a task can be assigned to any processor. In contrast, we initially study the problem of task scheduling on restricted parallel processors. The restriction takes account of affinities between tasks and processors; that is, a task has its own eligible set of processors. We adopt the Speed Scaling (SS) method to save energy under an execution time constraint (on the makespan CmaxCmax), and the processors can run at arbitrary speeds in [smin,smax][smin,smax]. Our objective is to minimize the overall energy consumption. The energy-efficient scheduling problem, involving task assignment and speed scaling, is inherently complex as it is proved to be NP-complete for general tasks. We formulate the problem as an Integer Programming (IP) problem. Specifically, we devise a polynomial-time optimal scheduling algorithm for the case in which tasks have a uniform size. Our algorithm runs in O(mn3logn)O(mn3logn) time, where mm is the number of processors and nn is the number of tasks. We then present a polynomial-time algorithm that achieves a bounded approximation factor when the tasks have arbitrary-size work. Numerical results demonstrate that our algorithm could provide an energy-efficient solution to the problem of task scheduling on restricted parallel processors.