File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Tradeoff between energy and throughput for online deadline scheduling

TitleTradeoff between energy and throughput for online deadline scheduling
Authors
KeywordsBounded-speed
Competitive algorithms
Competitive analysis
Competitive ratio
Deadline scheduling
Issue Date2011
PublisherElsevier Inc.. The Journal's web site is located at http://www.elsevier.com/wps/find/journaldescription.cws_home/724189/description#description
Citation
Sustainable Computing: informatics and systems, 2011, v. 1 n. 3, p. 189-195 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 a scheduling algorithm to discard some of the jobs (i.e., not finishing them by their deadlines), 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 can exist 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 Elsevier Inc. All rights reserved.
Persistent Identifierhttp://hdl.handle.net/10722/152007
ISSN
2023 Impact Factor: 3.8
2023 SCImago Journal Rankings: 1.014
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorChan, HLen_US
dc.contributor.authorLam, TWen_US
dc.contributor.authorLi, Ren_US
dc.date.accessioned2012-06-26T06:32:22Z-
dc.date.available2012-06-26T06:32:22Z-
dc.date.issued2011en_US
dc.identifier.citationSustainable Computing: informatics and systems, 2011, v. 1 n. 3, p. 189-195en_US
dc.identifier.issn2210-5379en_US
dc.identifier.urihttp://hdl.handle.net/10722/152007-
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 a scheduling algorithm to discard some of the jobs (i.e., not finishing them by their deadlines), 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 can exist 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 Elsevier Inc. All rights reserved.en_US
dc.languageengen_US
dc.publisherElsevier Inc.. The Journal's web site is located at http://www.elsevier.com/wps/find/journaldescription.cws_home/724189/description#description-
dc.relation.ispartofSustainable Computing: informatics and systemsen_US
dc.subjectBounded-speeden_US
dc.subjectCompetitive algorithmsen_US
dc.subjectCompetitive analysisen_US
dc.subjectCompetitive ratioen_US
dc.subjectDeadline schedulingen_US
dc.titleTradeoff between energy and throughput for online deadline schedulingen_US
dc.typeArticleen_US
dc.identifier.emailChan, HL: hlchan@cs.hku.hken_US
dc.identifier.emailLam, TW: hresltk@hkucc.hku.hken_US
dc.identifier.emailLi, R: rbli@cs.hku.hk-
dc.identifier.authorityChan, HL=rp01310en_US
dc.identifier.authorityLam, TW=rp00135en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1016/j.suscom.2011.05.002en_US
dc.identifier.scopuseid_2-s2.0-80052588140en_US
dc.identifier.hkuros212274-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-80052588140&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume1en_US
dc.identifier.issue3en_US
dc.identifier.spage189en_US
dc.identifier.epage195en_US
dc.identifier.isiWOS:000209575400004-
dc.publisher.placeUnited States-
dc.identifier.scopusauthoridLi, R=36918615800en_US
dc.identifier.scopusauthoridLam, TW=7202523165en_US
dc.identifier.scopusauthoridChan, HL=7403402384en_US
dc.identifier.issnl2210-5379-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats