TY - JOUR

T1 - New online algorithm for dynamic speed scaling with sleep state

AU - Kumar, Gunjan

AU - Shannigrahi, Saswata

PY - 2015/8/16

Y1 - 2015/8/16

N2 - We consider an energy-efficient scheduling problem where n jobs J1, J2, . . ., Jn need to be executed such that the total energy usage by these jobs is minimized while ensuring that each job is finished within its deadline. The processor executing these jobs can be in either active or sleep state at any point of time. The speed of the processor in an active state can be arbitrary. If the processor is running at a speed s≥0, the required power P(s) is assumed to be equal to sα+g where α>1, g>0 are constants. On the other hand, the required power is zero when the processor is in the sleep state. However, L>0 amount of wake-up energy is needed to wake-up the processor from the sleep state to the active state. In this paper, we work in an online setting where a job is known only at its arrival time, along with its processing volume and deadline. In such a setting, the currently best-known algorithm by Han et al. (2010) [3] provides a competitive ratio max{4, 2+αα} of energy usage. We present a new online algorithm SqOA which provides a competitive ratio max{4, 2+(2-1/α)α2α-1} of energy usage. For α≥2.34, the competitive ratio of our algorithm is better than that of any other existing algorithm for this problem.

AB - We consider an energy-efficient scheduling problem where n jobs J1, J2, . . ., Jn need to be executed such that the total energy usage by these jobs is minimized while ensuring that each job is finished within its deadline. The processor executing these jobs can be in either active or sleep state at any point of time. The speed of the processor in an active state can be arbitrary. If the processor is running at a speed s≥0, the required power P(s) is assumed to be equal to sα+g where α>1, g>0 are constants. On the other hand, the required power is zero when the processor is in the sleep state. However, L>0 amount of wake-up energy is needed to wake-up the processor from the sleep state to the active state. In this paper, we work in an online setting where a job is known only at its arrival time, along with its processing volume and deadline. In such a setting, the currently best-known algorithm by Han et al. (2010) [3] provides a competitive ratio max{4, 2+αα} of energy usage. We present a new online algorithm SqOA which provides a competitive ratio max{4, 2+(2-1/α)α2α-1} of energy usage. For α≥2.34, the competitive ratio of our algorithm is better than that of any other existing algorithm for this problem.

KW - Energy efficient algorithm

KW - Online algorithm

KW - Scheduling algorithm

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

U2 - 10.1016/j.tcs.2015.05.045

DO - 10.1016/j.tcs.2015.05.045

M3 - Article

AN - SCOPUS:84944898197

VL - 593

SP - 79

EP - 87

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -