Power-aware Scheduling With Discrete Voltages

This paper considers parallel machine scheduling with energy constraints:There are m identical machines sharing a total amount of energy E,each of which can run at p different speeds{s1,s2,...,sp},and a machine with speed sκcan process sκworkloads in unit time while consuming sκα(α≥2)energy.We are also given n jobs,and every job has a non-negative workloadωi and a release timeγi.The goal is to assign jobs and speeds to the given machines so as to minimize theCmax or∑iFi while meeting the energy constraints.This paper first deals with the case when jobs have identical release times.Based on the LP, we find the optimal solution for (?) and we also find two approximation algorithms with ratio(?) Furthermore,we consider the case when jobs have dffer-ent release times.We first analyze the structure of the optimal solution for (?) then we formulate the LP model and get the opti-mal solution.