TY - GEN

T1 - Generalized machine activation problems

AU - Li, Jian

AU - Khuller, Samir

PY - 2011

Y1 - 2011

N2 - In this paper we consider a generalization of the machine activation problem introduced recently ["Energy efficient scheduling via partial shutdown" by Khuller, Li and Saha (ACM-SIAM 2010 Symp. on Discrete Algorithms)] where the unrelated parallel machine scheduling problem is studied with machine activation cost. This is the standard unrelated parallel machine scheduling problem with a machine dependent activation cost that is incurred, if any job is assigned to the machine. The problem asks for a choice of machines to activate, and a schedule of all jobs on the active machines subject to the makespan constraint. The goal is to minimize the total activation cost. Our main generalization consists of a general activation cost model, where the activation cost for a machine is a non-decreasing function of its load. We develop a greedy algorithm that yields a fractional assignment of jobs, such that at least n - ε jobs are assigned fractionally and the total cost is at most 1 + ln(n/ε) times the optimum. Combining with standard rounding methods yields improved bounds for several machine activation problems. In addition, we study the machine activation problem with d linear constraints (these could model makespan constraints, as well as other types of constraints). Our method yields a schedule with machine activation cost of O(1/εlogn) times the optimum and a constraint violation by a factor of 2d + ε. This result matches our previous bound for the case d = 1. As a by-product, our method also yields a In n + 1 approximation factor for the non-metric universal facility location problem for which the cost of opening a facility is an arbitrary noii-decreasing function of the number of clients assigned to it. This gives an affirmative answer to the open question posed in earlier work on universal facility location.

AB - In this paper we consider a generalization of the machine activation problem introduced recently ["Energy efficient scheduling via partial shutdown" by Khuller, Li and Saha (ACM-SIAM 2010 Symp. on Discrete Algorithms)] where the unrelated parallel machine scheduling problem is studied with machine activation cost. This is the standard unrelated parallel machine scheduling problem with a machine dependent activation cost that is incurred, if any job is assigned to the machine. The problem asks for a choice of machines to activate, and a schedule of all jobs on the active machines subject to the makespan constraint. The goal is to minimize the total activation cost. Our main generalization consists of a general activation cost model, where the activation cost for a machine is a non-decreasing function of its load. We develop a greedy algorithm that yields a fractional assignment of jobs, such that at least n - ε jobs are assigned fractionally and the total cost is at most 1 + ln(n/ε) times the optimum. Combining with standard rounding methods yields improved bounds for several machine activation problems. In addition, we study the machine activation problem with d linear constraints (these could model makespan constraints, as well as other types of constraints). Our method yields a schedule with machine activation cost of O(1/εlogn) times the optimum and a constraint violation by a factor of 2d + ε. This result matches our previous bound for the case d = 1. As a by-product, our method also yields a In n + 1 approximation factor for the non-metric universal facility location problem for which the cost of opening a facility is an arbitrary noii-decreasing function of the number of clients assigned to it. This gives an affirmative answer to the open question posed in earlier work on universal facility location.

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

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

U2 - 10.1137/1.9781611973082.7

DO - 10.1137/1.9781611973082.7

M3 - Conference contribution

AN - SCOPUS:79955733336

SN - 9780898719932

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 80

EP - 94

BT - Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011

PB - Association for Computing Machinery

ER -