Scheduling for energy minimization on restricted parallel processors

Abstract

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 Cmax), and the processors can run at arbitrary speeds in [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) time, where m is the number of processors and n 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.