TY - JOUR

T1 - On the NP-hardness of speed scaling with sleep state

AU - Kumar, Gunjan

AU - Shannigrahi, Saswata

PY - 2015/10/4

Y1 - 2015/10/4

N2 - A modern processor can dynamically set its speed while it is active, and can make a transition to sleep state when required. When the processor is operating at a speed s, the energy consumed per unit time is given by the power function P(s)=sα+β where α and β are constants satisfying α>1, β>0. No energy is consumed when the processor is in the sleep state. However, C>0 units of energy are required to make a transition from the sleep state to the active state. The jobs are specified by their arrival time, deadline and the processing volume.We consider a scheduling problem, called speed scaling with sleep state, where each job has to be scheduled within its arrival time and deadline, and the goal is to minimize the total energy consumption required to process these jobs. Albers and Antoniadis (2012) proved the NP-hardness of this problem by reducing the NP-hard partition problem to an instance of this scheduling problem. The instance of this scheduling problem consists of the arrival time, the deadline and the processing volume for each of the jobs, in addition to some specifically designed P and C that depend on the instance of the partition problem. In this paper, we extend the above proof to show that the speed scaling with sleep state problem remains NP-hard for any fixed positive number C and any non-decreasing twice-differentiable strictly convex function P satisfying P(0)>0. One example of such a function is the power function P(s)=sα+β, α>1, β>0.

AB - A modern processor can dynamically set its speed while it is active, and can make a transition to sleep state when required. When the processor is operating at a speed s, the energy consumed per unit time is given by the power function P(s)=sα+β where α and β are constants satisfying α>1, β>0. No energy is consumed when the processor is in the sleep state. However, C>0 units of energy are required to make a transition from the sleep state to the active state. The jobs are specified by their arrival time, deadline and the processing volume.We consider a scheduling problem, called speed scaling with sleep state, where each job has to be scheduled within its arrival time and deadline, and the goal is to minimize the total energy consumption required to process these jobs. Albers and Antoniadis (2012) proved the NP-hardness of this problem by reducing the NP-hard partition problem to an instance of this scheduling problem. The instance of this scheduling problem consists of the arrival time, the deadline and the processing volume for each of the jobs, in addition to some specifically designed P and C that depend on the instance of the partition problem. In this paper, we extend the above proof to show that the speed scaling with sleep state problem remains NP-hard for any fixed positive number C and any non-decreasing twice-differentiable strictly convex function P satisfying P(0)>0. One example of such a function is the power function P(s)=sα+β, α>1, β>0.

KW - Energy efficient algorithm

KW - NP-hardness

KW - Scheduling algorithm

UR - http://www.scopus.com/inward/record.url?scp=84941261197&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2015.06.012

DO - 10.1016/j.tcs.2015.06.012

M3 - Article

AN - SCOPUS:84941261197

VL - 600

SP - 1

EP - 10

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -