Approximation algorithms for unrelated machine scheduling with an energy budget

Lin Chen; Wenchang Luo; Guochuan Zhang

doi:10.1007/978-3-642-21204-8_27

Approximation algorithms for unrelated machine scheduling with an energy budget

Lin Chen, Wenchang Luo, Guochuan Zhang

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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

Original language	English
Title of host publication	Frontiers in Algorithmics and Algorithmic Aspects in Information and Management - Joint International Conference, FAW-AAIM 2011, Proceedings
Pages	244-254
Number of pages	11
DOIs	https://doi.org/10.1007/978-3-642-21204-8_27
State	Published - 2011
Event	5th 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 2011 → May 31 2011

Publication series

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

Conference

Conference	5th International Frontiers in Algorithmics Workshop and the 7th International Conference on Algorithmic Aspects in Information and Management, FAW-AAIM 2011
Country/Territory	China
City	Jinhua
Period	05/28/11 → 05/31/11

Keywords

Approximation algorithm
Rounding
Unrelated machine scheduling

Access to Document

10.1007/978-3-642-21204-8_27

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

Chen, Lin ; Luo, Wenchang ; Zhang, Guochuan. / Approximation algorithms for unrelated machine scheduling with an energy budget. Frontiers in Algorithmics and Algorithmic Aspects in Information and Management - Joint International Conference, FAW-AAIM 2011, Proceedings. 2011. pp. 244-254 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{ed4b68ffd1ea4945accbcba74a5b7daf,

title = "Approximation algorithms for unrelated machine scheduling with an energy budget",

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.",

keywords = "Approximation algorithm, Rounding, Unrelated machine scheduling",

author = "Lin Chen and Wenchang Luo and Guochuan Zhang",

year = "2011",

doi = "10.1007/978-3-642-21204-8_27",

language = "English",

isbn = "9783642212031",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "244--254",

booktitle = "Frontiers in Algorithmics and Algorithmic Aspects in Information and Management - Joint International Conference, FAW-AAIM 2011, Proceedings",

note = "5th International Frontiers in Algorithmics Workshop and the 7th International Conference on Algorithmic Aspects in Information and Management, FAW-AAIM 2011 ; Conference date: 28-05-2011 Through 31-05-2011",

}

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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6681 LNCS, pp. 244-254, 5th International Frontiers in Algorithmics Workshop and the 7th International Conference on Algorithmic Aspects in Information and Management, FAW-AAIM 2011, Jinhua, China, 05/28/11. https://doi.org/10.1007/978-3-642-21204-8_27

Approximation algorithms for unrelated machine scheduling with an energy budget. / Chen, Lin; Luo, Wenchang; Zhang, Guochuan.
Frontiers in Algorithmics and Algorithmic Aspects in Information and Management - Joint International Conference, FAW-AAIM 2011, Proceedings. 2011. p. 244-254 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6681 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Approximation algorithms for unrelated machine scheduling with an energy budget

AU - Chen, Lin

AU - Luo, Wenchang

AU - Zhang, Guochuan

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

KW - Approximation algorithm

KW - Rounding

KW - Unrelated machine scheduling

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

U2 - 10.1007/978-3-642-21204-8_27

DO - 10.1007/978-3-642-21204-8_27

M3 - Conference contribution

AN - SCOPUS:79957930095

SN - 9783642212031

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 244

EP - 254

BT - Frontiers in Algorithmics and Algorithmic Aspects in Information and Management - Joint International Conference, FAW-AAIM 2011, Proceedings

T2 - 5th International Frontiers in Algorithmics Workshop and the 7th International Conference on Algorithmic Aspects in Information and Management, FAW-AAIM 2011

Y2 - 28 May 2011 through 31 May 2011

ER -

Chen L, Luo W, Zhang G. 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. 2011. p. 244-254. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-21204-8_27

Approximation algorithms for unrelated machine scheduling with an energy budget

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this