We define a collection of new problems referred to as ``machine activation''#R##N#problems. The  central framework we introduce considers a collection of M#R##N#machines (unrelated  or related), with machine $i$ having an activation#R##N#cost of $a_i$.#R##N#There is also a collection of N jobs that need to be performed, and#R##N#$p_{ij}$ is the processing time of job $j$ on machine $i$.#R##N#Standard scheduling models assume that the set of machines is fixed#R##N#and all machines are available. We assume that there is an activation cost#R##N#budget of $A$#R##N#-- we would like to select a subset S of the machines to activate#R##N#with total cost $a(S)le A$ and find a schedule for the jobs on the#R##N#machines in $S$ minimizing the makespan. In this work we develop#R##N#bi-criteria approximation algorithms for this problem based on both#R##N#LP rounding and a greedy approach.
['Samir Khuller', 'Jian Li', 'Barna Saha']
Energy Efficient Scheduling via Partial Shutdown