On the NP-hardness of speed scaling with sleep state

DOI10.1016/J.TCS.2015.06.012zbMATH Open1329.68127arXiv1304.7373OpenAlexW844564591MaRDI QIDQ495994FDOQ495994

Authors: Gunjan Kumar, Saswata Shannigrahi

Publication date: 16 September 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: A modern processor can dynamically set it's speed while it's 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 a convex power function

P (s)

having the property that

P (0) > 0

and

for all values of

s

. Moreover,

C > 0

units of energy is 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 their arrival time and deadline, and the goal is to minimize the total energy consumption required to process these jobs. Albers et. al. proved the NP-hardness of this problem by reducing an instance of an 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

P

and

C

. Since

P

and

C

depend on the instance of the partition problem, this proof of the NP-hardness of the speed scaling with sleep state problem doesn't remain valid when