File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Non-clairvoyant scheduling for weighted flow time and energy on speed bounded processors

TitleNon-clairvoyant scheduling for weighted flow time and energy on speed bounded processors
Authors
KeywordsOnline algorithms
Non-clairvoyant scheduling
Speed scaling
Energy
Flow time
Issue Date2011
PublisherDepartment of Computer Science, The University of Chicago. The Journal's web site is located at http://cjtcs.cs.uchicago.edu
Citation
CATS 2010, Computing: The Australasian Theory Symposium, Brisbane, Australia, 18-21 January 2010. In Chicago Journal of Theoretical Computer Science, 2011, p. article no. 1 How to Cite?
AbstractWe consider the online scheduling problem of minimizing total weighted flow time plus energy in the dynamic speed scaling model, where a processor can scale its speed dynamically between 0 and some maximum speed T. In the past few years this problem has been studied extensively under the clairvoyant setting, which requires the size of a job to be known at release time [1, 4, 5, 8, 15, 18–20]. For the non-clairvoyant setting, despite its practical importance, the progress is relatively limited. Only recently an online algorithm LAPS is known to be O(1)-competitive for minimizing (unweighted) flow time plus energy in the infinite speed model (i.e., T = ¥) [11, 12]. This paper makes two contributions to the non-clairvoyant scheduling. First, we resolve the open problem that the unweighted result of LAPS can be extended to the more realistic model with bounded maximum speed. Second, we show that another non-clairvoyant algorithm WRR is O(1)-competitive when weighted flow time is concerned. Note that WRR is not as efficient as LAPS for scheduling unweighted jobs as WRR has a much bigger constant hidden in its competitive ratio.
Persistent Identifierhttp://hdl.handle.net/10722/140791
ISSN
2002 Impact Factor: 0.0

 

DC FieldValueLanguage
dc.contributor.authorChan, SHen_US
dc.contributor.authorLam, TWen_US
dc.contributor.authorLee, LKen_US
dc.contributor.authorTing, HFen_US
dc.contributor.authorZhang, Pen_US
dc.date.accessioned2011-09-23T06:19:23Z-
dc.date.available2011-09-23T06:19:23Z-
dc.date.issued2011en_US
dc.identifier.citationCATS 2010, Computing: The Australasian Theory Symposium, Brisbane, Australia, 18-21 January 2010. In Chicago Journal of Theoretical Computer Science, 2011, p. article no. 1en_US
dc.identifier.issn1073-0486-
dc.identifier.urihttp://hdl.handle.net/10722/140791-
dc.description.abstractWe consider the online scheduling problem of minimizing total weighted flow time plus energy in the dynamic speed scaling model, where a processor can scale its speed dynamically between 0 and some maximum speed T. In the past few years this problem has been studied extensively under the clairvoyant setting, which requires the size of a job to be known at release time [1, 4, 5, 8, 15, 18–20]. For the non-clairvoyant setting, despite its practical importance, the progress is relatively limited. Only recently an online algorithm LAPS is known to be O(1)-competitive for minimizing (unweighted) flow time plus energy in the infinite speed model (i.e., T = ¥) [11, 12]. This paper makes two contributions to the non-clairvoyant scheduling. First, we resolve the open problem that the unweighted result of LAPS can be extended to the more realistic model with bounded maximum speed. Second, we show that another non-clairvoyant algorithm WRR is O(1)-competitive when weighted flow time is concerned. Note that WRR is not as efficient as LAPS for scheduling unweighted jobs as WRR has a much bigger constant hidden in its competitive ratio.-
dc.languageengen_US
dc.publisherDepartment of Computer Science, The University of Chicago. The Journal's web site is located at http://cjtcs.cs.uchicago.eduen_US
dc.relation.ispartofChicago Journal of Theoretical Computer Scienceen_US
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.subjectOnline algorithms-
dc.subjectNon-clairvoyant scheduling-
dc.subjectSpeed scaling-
dc.subjectEnergy-
dc.subjectFlow time-
dc.titleNon-clairvoyant scheduling for weighted flow time and energy on speed bounded processorsen_US
dc.typeArticleen_US
dc.identifier.emailLam, TW: hresltk@hkucc.hku.hken_US
dc.identifier.emailTing, HF: hfting@cs.hku.hken_US
dc.identifier.authorityLam, TW=rp00135en_US
dc.identifier.authorityTing, HF=rp00177en_US
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.4086/cjtcs.2011.001-
dc.identifier.hkuros192203en_US
dc.identifier.spagearticle no. 1en_US
dc.identifier.epagearticle no. 1en_US
dc.publisher.placeUnited States-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats