Generalized machine activation problems

Jian Li*, Samir Khuller

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

17 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011
PublisherAssociation for Computing Machinery
Pages80-94
Number of pages15
ISBN (Print)9780898719932
DOIs
StatePublished - 2011

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

ASJC Scopus subject areas

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'Generalized machine activation problems'. Together they form a unique fingerprint.

Cite this