File Download
Supplementary
-
Citations:
- Appears in Collections:
Conference Paper: Competitive online algorithms for multiple-machine power management and weighted flow time
Title | Competitive online algorithms for multiple-machine power management and weighted flow time |
---|---|
Authors | |
Keywords | Sleep management Weighted flow time Energy efficiency Potential analysis |
Issue Date | 2013 |
Publisher | Australian Computer Society, Inc.. |
Citation | The 19th Computing: the Australasian Theory Symposium (CATS'13), Adelaide, Australia, 29 January-1 February 2013. In Conference Proceedings, 2013, v. 141, p. 11-20 How to Cite? |
Abstract | We consider online job scheduling together with power management on multiple machines. In this model, jobs with arbitrary sizes and weights arrive online, and each machine consumes different amount of energy when it is processing a job, idling or sleeping. A scheduler has to maintain a good balance of the states of the machines to avoid energy wastage, while giving an efficient schedule of the jobs. We consider a recently well-studied objective of minimizing the total weighted flow time of the jobs plus the total energy usage. For the special case where all jobs have the same weight, competitive algorithms have been obtained (Lam et al. 2009, Chan et al. 2011). This paper gives a non-trivial potential analysis of a weighted generalization of the power management algorithm in (Chan et al. 2011), coupled with a classic scheduling algorithm HDF. This leads to the first competitive result for minimizing weighted flow time plus energy. The result can be extended to the dynamic speed scaling model where the scheduler can vary the speed of individual machines to process the jobs and the energy usage depends on the speed of the machines. |
Persistent Identifier | http://hdl.handle.net/10722/189627 |
ISBN |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chan, HL | en_US |
dc.contributor.author | Chan, SH | en_US |
dc.contributor.author | Lam, TW | en_US |
dc.contributor.author | Lee, LK | en_US |
dc.contributor.author | Li, R | en_US |
dc.contributor.author | Liu, CM | en_US |
dc.date.accessioned | 2013-09-17T14:50:24Z | - |
dc.date.available | 2013-09-17T14:50:24Z | - |
dc.date.issued | 2013 | en_US |
dc.identifier.citation | The 19th Computing: the Australasian Theory Symposium (CATS'13), Adelaide, Australia, 29 January-1 February 2013. In Conference Proceedings, 2013, v. 141, p. 11-20 | en_US |
dc.identifier.isbn | 978-1-921770-26-5 | - |
dc.identifier.uri | http://hdl.handle.net/10722/189627 | - |
dc.description.abstract | We consider online job scheduling together with power management on multiple machines. In this model, jobs with arbitrary sizes and weights arrive online, and each machine consumes different amount of energy when it is processing a job, idling or sleeping. A scheduler has to maintain a good balance of the states of the machines to avoid energy wastage, while giving an efficient schedule of the jobs. We consider a recently well-studied objective of minimizing the total weighted flow time of the jobs plus the total energy usage. For the special case where all jobs have the same weight, competitive algorithms have been obtained (Lam et al. 2009, Chan et al. 2011). This paper gives a non-trivial potential analysis of a weighted generalization of the power management algorithm in (Chan et al. 2011), coupled with a classic scheduling algorithm HDF. This leads to the first competitive result for minimizing weighted flow time plus energy. The result can be extended to the dynamic speed scaling model where the scheduler can vary the speed of individual machines to process the jobs and the energy usage depends on the speed of the machines. | - |
dc.language | eng | en_US |
dc.publisher | Australian Computer Society, Inc.. | - |
dc.relation.ispartof | Proceedings of the Nineteenth Computing: the Australasian Theory Symposium | en_US |
dc.subject | Sleep management | - |
dc.subject | Weighted flow time | - |
dc.subject | Energy efficiency | - |
dc.subject | Potential analysis | - |
dc.title | Competitive online algorithms for multiple-machine power management and weighted flow time | en_US |
dc.type | Conference_Paper | en_US |
dc.identifier.email | Chan, HL: hlchan@cs.hku.hk | en_US |
dc.identifier.email | Chan, SH: shchan@cs.hku.hk | en_US |
dc.identifier.email | Lam, TW: hresltk@hkucc.hku.hk | en_US |
dc.identifier.email | Lee, LK: lklee@cs.hku.hk | en_US |
dc.identifier.email | Li, R: rbli@cs.hku.hk | - |
dc.identifier.email | Liu, CM: cmliu@cs.hku.hk | - |
dc.identifier.authority | Chan, HL=rp01310 | en_US |
dc.identifier.authority | Lam, TW=rp00135 | en_US |
dc.identifier.authority | Lee, LK=rp00140 | en_US |
dc.description.nature | link_to_OA_fulltext | - |
dc.identifier.hkuros | 222382 | en_US |
dc.identifier.volume | 141 | - |
dc.identifier.spage | 11 | - |
dc.identifier.epage | 20 | - |
dc.publisher.place | Australia | - |
dc.customcontrol.immutable | sml 131011 | - |