Energy Efficient Scheduling via Partial Shutdown
Samir Khuller, Jian Li, Barna Saha · 2010
Motivated by issues of saving energy in data centers we define a collection of new problems referred to as “machine activation ” problems. The central framework we introduce considers a collection of m machines (unrelated or related) with each machine i having an activation cost of ai. There is also a collection of n jobs that need to be performed, and pi,j is the processing time of job j on machine i. Standard scheduling models assume that the set of machines is fixed and all machines are available. However, in our setting, we assume that there is an activation cost budget of A – we would like to select a subset S of the machines to activate with total cost a(S) ≤ A and find a schedule for the n jobs on the machines in S minimizing the makespan (or any other metric). We consider both the unrelated machines setting, as well as the setting of scheduling uniformly related parallel machines, where machine i has activation cost ai and speed si, and the processing time of job j on machine i is pi,j = pj si where pj is the processing requirement of job j. For the general unrelated machine activation problem, our main results are that if there is a schedule with makespan T and activation cost A then we can obtain a schedule with makespan (2+)T and activation cost 2(1+ 1)(ln n