Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Approximation Algorithms for Unrelated Machine Scheduling with an Energy Budget
verfasst von : Lin Chen, Wenchang Luo, Guochuan Zhang
Erschienen in: Frontiers in Algorithmics and Algorithmic Aspects in Information and Management
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We consider the problem of unrelated parallel machine scheduling when the DVS (dynamic voltage scaling) method is used to conserve energy consumption. Given an energy budget, we present (2 +
ε
)-approximation algorithms for the makespan minimization problem under two different settings, the continuous model in which speeds are allowed to be any real number in [
s
min
,
s
max
] and the discrete model in which only
d
distinct speeds are available. We also show how to derive a 2-approximation algorithm if the energy budget is allowed to be slightly exceeded.