We improve complexity bounds for energy-efficient non-preemptive scheduling problems for both the single processor and multiprocessor cases. As energy conservation has become a major concern, traditional scheduling problems have been revisited in the past few years to take into account the energy consumption. We consider the speed scaling setting introduced by Yao et al. [20] where a set of jobs, each with a release date, deadline and work volume, are to be scheduled on a set of identical processors. The processors may change speed as a function of time and the energy they consume is the αth power of their speed integrated over time. The objective is then to find a feasible non-preemptive schedule which minimizes the total energy used. We show that for an arbitraxily number of processors and jobs with equal work volumes there is a 2(1 + ε)(5(1 + ε))~(α-1)B_α = O_α(1) approximation algorithm, where B_α is the generalized Bell number. This is the first constant factor algorithm for the multi-processor case, and this also extends to arbitrary processor-dependent work volumes, up to losing a factor of (((1+r)r)/2)~α in the approximation, where r is the maximum ratio between two work volumes. For the single processor case, we introduce a new linear programming formulation of speed scaling, using a new constraint capturing non-preemption, and prove that its integrality gap is at most 12~(α-1). With our new constraint we improve on the previously known unbounded integrality gap of at least Ω(n~(α-1)). Finally, we deal with the inapproximabilty of speed scaling and we prove that the multiprocessor case is APX-hard, even in the special case where all release dates and deadlines are equal and r is 4.
展开▼
