File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Speed scaling functions for flow time scheduling based on active job count

TitleSpeed scaling functions for flow time scheduling based on active job count
Authors
KeywordsCompetitive algorithms
Competitive ratios
Dynamic speed scaling
Energy usages
Flow times
Issue Date2008
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
The 16th Annual European Symposium on Algorithms (ESA 2008), Karlsruhe, Germany, 15-17 September 2008. In Lecture Notes in Computer Science, 2008, v. 5193, p. 647-659 How to Cite?
AbstractWe study online scheduling to minimize flow time plus energy usage in the dynamic speed scaling model. We devise new speed scaling functions that depend on the number of active jobs, replacing the existing speed scaling functions in the literature that depend on the remaining work of active jobs. The new speed functions are more stable and also more efficient. They can support better job selection strategies to improve the competitive ratios of existing algorithms [8,5], and, more importantly, to remove the requirement of extra speed. These functions further distinguish themselves from others as they can readily be used in the non-clairvoyant model (where the size of a job is only known when the job finishes). As a first step, we study the scheduling of batched jobs (i.e., jobs with the same release time) in the non-clairvoyant model and present the first competitive algorithm for minimizing flow time plus energy (as well as for weighted flow time plus energy); the performance is close to optimal. © 2008 Springer-Verlag Berlin Heidelberg.
DescriptionLNCS v. 5193 is Proceedings of the 16th Annual European Symposium, ESA 2008
Session 9B
Persistent Identifierhttp://hdl.handle.net/10722/61200
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252
References

 

DC FieldValueLanguage
dc.contributor.authorLam, TWen_HK
dc.contributor.authorLee, LKen_HK
dc.contributor.authorTo, IKKen_HK
dc.contributor.authorWong, PWHen_HK
dc.date.accessioned2010-07-13T03:33:02Z-
dc.date.available2010-07-13T03:33:02Z-
dc.date.issued2008en_HK
dc.identifier.citationThe 16th Annual European Symposium on Algorithms (ESA 2008), Karlsruhe, Germany, 15-17 September 2008. In Lecture Notes in Computer Science, 2008, v. 5193, p. 647-659en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/61200-
dc.descriptionLNCS v. 5193 is Proceedings of the 16th Annual European Symposium, ESA 2008en_HK
dc.descriptionSession 9B-
dc.description.abstractWe study online scheduling to minimize flow time plus energy usage in the dynamic speed scaling model. We devise new speed scaling functions that depend on the number of active jobs, replacing the existing speed scaling functions in the literature that depend on the remaining work of active jobs. The new speed functions are more stable and also more efficient. They can support better job selection strategies to improve the competitive ratios of existing algorithms [8,5], and, more importantly, to remove the requirement of extra speed. These functions further distinguish themselves from others as they can readily be used in the non-clairvoyant model (where the size of a job is only known when the job finishes). As a first step, we study the scheduling of batched jobs (i.e., jobs with the same release time) in the non-clairvoyant model and present the first competitive algorithm for minimizing flow time plus energy (as well as for weighted flow time plus energy); the performance is close to optimal. © 2008 Springer-Verlag Berlin Heidelberg.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.rightsThe original publication is available at www.springerlink.com-
dc.subjectCompetitive algorithms-
dc.subjectCompetitive ratios-
dc.subjectDynamic speed scaling-
dc.subjectEnergy usages-
dc.subjectFlow times-
dc.titleSpeed scaling functions for flow time scheduling based on active job counten_HK
dc.typeConference_Paperen_HK
dc.identifier.emailLam, TW: hresltk@hkucc.hku.hken_HK
dc.identifier.emailLee, LK: lklee@cs.hku.hken_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.identifier.authorityLee, LK=rp00140en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/978-3-540-87744-8-54en_HK
dc.identifier.scopuseid_2-s2.0-57749203967en_HK
dc.identifier.hkuros163532en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-57749203967&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume5193 LNCSen_HK
dc.identifier.spage647en_HK
dc.identifier.epage659en_HK
dc.publisher.placeGermanyen_HK
dc.description.otherThe 16th Annual European Symposium on Algorithms (ESA 2008), Karlsruhe, Germany, 15-17 September 2008. In Lecture Notes in Computer Science, 2008, v. 5193, p. 647-659-
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridLee, LK=12646190100en_HK
dc.identifier.scopusauthoridTo, IKK=23398547200en_HK
dc.identifier.scopusauthoridWong, PWH=9734871500en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats