File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Tradeoff between energy and throughput for online deadline scheduling

TitleTradeoff between energy and throughput for online deadline scheduling
Authors
Issue Date2011
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
The 8th International Workshop on Approximation and Online Algorithms (WAOA), Liverpool, UK, 9-10 September 2010. In Lecture Notes in Computer Science, v. 6534, p. 58-70 How to Cite?
AbstractWe consider dynamic speed scaling on a single processor and study the tradeoff between throughput and energy for deadline scheduling. Specifically, we assume each job is associated with a user-defined value (or importance) and a deadline. We allow scheduling algorithms to discard some of the jobs (i.e., not finishing them) and the objective is to minimize the total energy usage plus the total value of jobs discarded. We give new online algorithms under both the unbounded-speed and bounded-speed models. When the maximum speed is unbounded, we give an O(1)-competitive algorithm. This algorithm relies on a key notion called the profitable speed, which is the maximum speed beyond which processing a job costs more energy than the value of the job. When the processor has a bounded maximum speed T, we show that no O(1)-competitive algorithm exists and more precisely, the competitive ratio grows with the penalty ratio of the input, which is defined as the ratio between the maximum profitable speed of a job to the maximum speed T. On the positive side, we give an algorithm with a competitive ratio whose dependency on the penalty ratio almost matches the lower bound. © 2011 Springer-Verlag.
DescriptionLecture Notes in Computer Science, vol. 6534 entitled: Approximation and Online Algorithms: 8th international workshop, WAOA 2010, Liverpool, UK, September 9-10, 2010: revised papers
Persistent Identifierhttp://hdl.handle.net/10722/139981
ISBN
ISSN
2023 SCImago Journal Rankings: 0.606
References

 

DC FieldValueLanguage
dc.contributor.authorChan, HLen_HK
dc.contributor.authorLam, TWen_HK
dc.contributor.authorLi, Ren_HK
dc.date.accessioned2011-09-23T06:04:20Z-
dc.date.available2011-09-23T06:04:20Z-
dc.date.issued2011en_HK
dc.identifier.citationThe 8th International Workshop on Approximation and Online Algorithms (WAOA), Liverpool, UK, 9-10 September 2010. In Lecture Notes in Computer Science, v. 6534, p. 58-70en_HK
dc.identifier.isbn9783642183171-
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/139981-
dc.descriptionLecture Notes in Computer Science, vol. 6534 entitled: Approximation and Online Algorithms: 8th international workshop, WAOA 2010, Liverpool, UK, September 9-10, 2010: revised papers-
dc.description.abstractWe consider dynamic speed scaling on a single processor and study the tradeoff between throughput and energy for deadline scheduling. Specifically, we assume each job is associated with a user-defined value (or importance) and a deadline. We allow scheduling algorithms to discard some of the jobs (i.e., not finishing them) and the objective is to minimize the total energy usage plus the total value of jobs discarded. We give new online algorithms under both the unbounded-speed and bounded-speed models. When the maximum speed is unbounded, we give an O(1)-competitive algorithm. This algorithm relies on a key notion called the profitable speed, which is the maximum speed beyond which processing a job costs more energy than the value of the job. When the processor has a bounded maximum speed T, we show that no O(1)-competitive algorithm exists and more precisely, the competitive ratio grows with the penalty ratio of the input, which is defined as the ratio between the maximum profitable speed of a job to the maximum speed T. On the positive side, we give an algorithm with a competitive ratio whose dependency on the penalty ratio almost matches the lower bound. © 2011 Springer-Verlag.en_HK
dc.languageengen_US
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en_HK
dc.rightsThe original publication is available at www.springerlink.comen_US
dc.titleTradeoff between energy and throughput for online deadline schedulingen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailChan, HL:hlchan@cs.hku.hken_HK
dc.identifier.emailLam, TW:twlam@cs.hku.hken_HK
dc.identifier.authorityChan, HL=rp01310en_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/978-3-642-18318-8_6en_HK
dc.identifier.scopuseid_2-s2.0-79551529491en_HK
dc.identifier.hkuros192202en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-79551529491&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume6534en_HK
dc.identifier.spage59en_HK
dc.identifier.epage70en_HK
dc.publisher.placeGermanyen_HK
dc.identifier.scopusauthoridChan, HL=7403402384en_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridLi, R=36918615800en_HK
dc.identifier.issnl0302-9743-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats