On the NP-hardness of speed scaling with sleep state

详细信息    查看全文

• 作者：Gunjan Kumar ^{gunjan.kg1024@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Saswata Shannigrahi ; ^{saswata.sh@iitg.ernet.in" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Energy efficient algorithm ; Scheduling algorithm ; NP-hardness
• 刊名：Theoretical Computer Science
• 出版年：2015
• 出版时间：4 October 2015
• 年：2015
• 卷：600
• 期：Complete
• 页码：1-10
• 全文大小：335 K

文摘

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^伪+尾$P(s)=s^{伪}+尾$ where 伪 and 尾   are constants satisfying 伪>1,尾>0$伪>1,尾>0$. No energy is consumed when the processor is in the sleep state. However, C>0$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$P(0)>0$. One example of such a function is the power function P(s)=s^伪+尾,伪>1,尾>0$P(s)=s^{伪}+尾,伪>1,尾>0$.