File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Online deadline scheduling with bounded energy efficiency

TitleOnline deadline scheduling with bounded energy efficiency
Authors
Issue Date2007
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2007, v. 4484 LNCS, p. 416-427 How to Cite?
AbstractExisting work on scheduling with energy concern has focused on minimizing the energy for completing all jobs or achieving maximum throughput [19, 2, 7, 13, 14]. That is, energy usage is a secondary concern when compared to throughput and the schedules targeted may be very poor in energy efficiency. In this paper, we attempt to put energy efficiency as the primary concern and study how to maximize throughput subject to a user-defined threshold of energy efficiency. We first show that all deterministic online algorithms have a competitive ratio at least Δ, where Δ is the max-min ratio of job size. Nevertheless, allowing the online algorithm to have a slightly poorer energy efficiency leads to constant (i.e., independent of Δ) competitive online algorithm. On the other hand, using randomization, we can reduce the competitive ratio to O(log Δ) without relaxing the efficiency threshold. Finally we consider a special case where no jobs are "demanding" and give a deterministic online algorithm with constant competitive ratio for this case. © Springer-Verlag Berlin Heidelberg 2007.
Persistent Identifierhttp://hdl.handle.net/10722/93419
ISSN
2023 SCImago Journal Rankings: 0.606
References

 

DC FieldValueLanguage
dc.contributor.authorChan, JWTen_HK
dc.contributor.authorLam, TWen_HK
dc.contributor.authorMak, KSen_HK
dc.contributor.authorWong, PWHen_HK
dc.date.accessioned2010-09-25T15:00:35Z-
dc.date.available2010-09-25T15:00:35Z-
dc.date.issued2007en_HK
dc.identifier.citationLecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2007, v. 4484 LNCS, p. 416-427en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/93419-
dc.description.abstractExisting work on scheduling with energy concern has focused on minimizing the energy for completing all jobs or achieving maximum throughput [19, 2, 7, 13, 14]. That is, energy usage is a secondary concern when compared to throughput and the schedules targeted may be very poor in energy efficiency. In this paper, we attempt to put energy efficiency as the primary concern and study how to maximize throughput subject to a user-defined threshold of energy efficiency. We first show that all deterministic online algorithms have a competitive ratio at least Δ, where Δ is the max-min ratio of job size. Nevertheless, allowing the online algorithm to have a slightly poorer energy efficiency leads to constant (i.e., independent of Δ) competitive online algorithm. On the other hand, using randomization, we can reduce the competitive ratio to O(log Δ) without relaxing the efficiency threshold. Finally we consider a special case where no jobs are "demanding" and give a deterministic online algorithm with constant competitive ratio for this case. © Springer-Verlag Berlin Heidelberg 2007.en_HK
dc.languageengen_HK
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.titleOnline deadline scheduling with bounded energy efficiencyen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailLam, TW:twlam@cs.hku.hken_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.scopuseid_2-s2.0-35448942649en_HK
dc.identifier.hkuros128192en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-35448942649&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume4484 LNCSen_HK
dc.identifier.spage416en_HK
dc.identifier.epage427en_HK
dc.publisher.placeGermanyen_HK
dc.identifier.scopusauthoridChan, JWT=16021445200en_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridMak, KS=54970721600en_HK
dc.identifier.scopusauthoridWong, PWH=9734871500en_HK
dc.identifier.issnl0302-9743-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats