Approximation algorithms for unrelated machine scheduling with an energy budget

Lin Chen, Wenchang Luo, Guochuan Zhang

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

2 Scopus citations

Abstract

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 [smin, 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.

Original languageEnglish
Title of host publicationFrontiers in Algorithmics and Algorithmic Aspects in Information and Management - Joint International Conference, FAW-AAIM 2011, Proceedings
Pages244-254
Number of pages11
DOIs
StatePublished - 2011
Event5th International Frontiers in Algorithmics Workshop and the 7th International Conference on Algorithmic Aspects in Information and Management, FAW-AAIM 2011 - Jinhua, China
Duration: May 28 2011May 31 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6681 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference5th International Frontiers in Algorithmics Workshop and the 7th International Conference on Algorithmic Aspects in Information and Management, FAW-AAIM 2011
CountryChina
CityJinhua
Period05/28/1105/31/11

Keywords

  • Approximation algorithm
  • Rounding
  • Unrelated machine scheduling

Fingerprint Dive into the research topics of 'Approximation algorithms for unrelated machine scheduling with an energy budget'. Together they form a unique fingerprint.

  • Cite this

    Chen, L., Luo, W., & Zhang, G. (2011). Approximation algorithms for unrelated machine scheduling with an energy budget. In Frontiers in Algorithmics and Algorithmic Aspects in Information and Management - Joint International Conference, FAW-AAIM 2011, Proceedings (pp. 244-254). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6681 LNCS). https://doi.org/10.1007/978-3-642-21204-8_27