Energy-Efficient Scheduling with Time and Processors Eligibility Restrictions

While previous work on energy-efficient algorithms focused on assumption that tasks can be assigned to any processor, we initially study the problem of task scheduling on restricted parallel processors. The objective is to minimize the overall energy consumption while speed scaling (SS) method is used to reduce energy consumption under the execution time constraint (Makespan C-max). In this work, we discuss the speed setting in the continuous model that processors can run at arbitrary speed in [s(min), s(max)]. The energy-efficient scheduling problem, involving task assignment and speed scaling, is inherently complicated as it is proved to be NP-Complete. We formulate the problem as an Integer Programming (IP) problem. Specifically, we devise a polynomial time optimal scheduling algorithm for the case tasks have an uniform size. Our algorithm runs in O(mn(3) logn) time, where m is the number of processors and n is the number of tasks. We then present a polynomial time algorithm that achieves an approximation factor of 2(alpha-1) (2 - 1/m(alpha)) (alpha is the power parameter) when the tasks have arbitrary size work.