Energy Efficient Scheduling via Partial Shutdown

Authors Samir Khuller, Jian Li, Barna Saha



PDF
Thumbnail PDF

File

DagSemProc.10071.5.pdf
  • Filesize: 305 kB
  • 13 pages

Document Identifiers

Author Details

Samir Khuller
Jian Li
Barna Saha

Cite AsGet BibTex

Samir Khuller, Jian Li, and Barna Saha. Energy Efficient Scheduling via Partial Shutdown. In Scheduling. Dagstuhl Seminar Proceedings, Volume 10071, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
https://doi.org/10.4230/DagSemProc.10071.5

Abstract

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 machine $i$ having an activation cost of $a_i$. There is also a collection of N jobs that need to be performed, and $p_{ij}$ 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. 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)le A$ and find a schedule for the jobs on the machines in $S$ minimizing the makespan. In this work we develop bi-criteria approximation algorithms for this problem based on both LP rounding and a greedy approach.
Keywords
  • Unrelated parallel machine scheduling
  • approximation algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail