File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Improved multi-processor scheduling for flow time and energy

TitleImproved multi-processor scheduling for flow time and energy
Authors
KeywordsCompetitive analysis
Dynamic speed scaling
Energy minimization
Multi processor scheduling
Online scheduling algorithm
Issue Date2012
PublisherSpringer New York LLC. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=1094-6136
Citation
Journal of Scheduling, 2012, v. 15 n. 1, p. 105-116 How to Cite?
AbstractEnergy usage has been an important concern in recent research on online scheduling. In this paper, we study the tradeoff between flow time and energy (Albers and Fujiwara in ACM Trans. Algorithms 3(4), 2007; Bansal et al. in Proceedings of ACM-SIAM Symposium on Discrete Algorithms, pp. 805-813, 2007b, Bansal et al. in Proceedings of International Colloquium on Automata, Languages and Programming, pp. 409-420, 2008; Lam et al. in Proceedings of European Symposium on Algorithms, pp. 647-659, 2008b) in the multi-processor setting. Our main result is an enhanced analysis of a simple non-migratory online algorithm called CRR (classified round robin) on m ≥ 2 processors, showing that its flow time plus energy is within O(1) times of the optimal non-migratory offline algorithm, when the maximum allowable speed is slightly relaxed. The result still holds even if the comparison is made against the optimal migratory offline algorithm. This improves previous analysis that CRR is O(log P)-competitive where P is the ratio of the maximum job size to the minimum job size. © Springer Science+Business Media, LLC 2009.
Persistent Identifierhttp://hdl.handle.net/10722/152503
ISSN
2015 Impact Factor: 1.023
2015 SCImago Journal Rankings: 1.053
ISI Accession Number ID
Funding AgencyGrant Number
HKU7176104
EPSRCEP/E028276/1
Funding Information:

T.W. Lam is partially supported by HKU Grant 7176104.

References

 

DC FieldValueLanguage
dc.contributor.authorLam, TWen_US
dc.contributor.authorLee, LKen_US
dc.contributor.authorTo, IKKen_US
dc.contributor.authorWong, PWHen_US
dc.date.accessioned2012-06-26T06:39:44Z-
dc.date.available2012-06-26T06:39:44Z-
dc.date.issued2012en_US
dc.identifier.citationJournal of Scheduling, 2012, v. 15 n. 1, p. 105-116en_US
dc.identifier.issn1094-6136en_US
dc.identifier.urihttp://hdl.handle.net/10722/152503-
dc.description.abstractEnergy usage has been an important concern in recent research on online scheduling. In this paper, we study the tradeoff between flow time and energy (Albers and Fujiwara in ACM Trans. Algorithms 3(4), 2007; Bansal et al. in Proceedings of ACM-SIAM Symposium on Discrete Algorithms, pp. 805-813, 2007b, Bansal et al. in Proceedings of International Colloquium on Automata, Languages and Programming, pp. 409-420, 2008; Lam et al. in Proceedings of European Symposium on Algorithms, pp. 647-659, 2008b) in the multi-processor setting. Our main result is an enhanced analysis of a simple non-migratory online algorithm called CRR (classified round robin) on m ≥ 2 processors, showing that its flow time plus energy is within O(1) times of the optimal non-migratory offline algorithm, when the maximum allowable speed is slightly relaxed. The result still holds even if the comparison is made against the optimal migratory offline algorithm. This improves previous analysis that CRR is O(log P)-competitive where P is the ratio of the maximum job size to the minimum job size. © Springer Science+Business Media, LLC 2009.en_US
dc.languageengen_US
dc.publisherSpringer New York LLC. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=1094-6136en_US
dc.relation.ispartofJournal of Schedulingen_US
dc.rightsThe original publication is available at www.springerlink.com-
dc.subjectCompetitive analysisen_US
dc.subjectDynamic speed scalingen_US
dc.subjectEnergy minimizationen_US
dc.subjectMulti processor schedulingen_US
dc.subjectOnline scheduling algorithmen_US
dc.titleImproved multi-processor scheduling for flow time and energyen_US
dc.typeArticleen_US
dc.identifier.emailLam, TW: hresltk@hkucc.hku.hken_US
dc.identifier.emailLee, LK: lklee@cs.hku.hken_US
dc.identifier.emailTo, IKK: isaacto@liverpool.ac.uk-
dc.identifier.emailWong, PWH: pwong@liverpool.ac.uk-
dc.identifier.authorityLam, TW=rp00135en_US
dc.identifier.authorityLee, LK=rp00140en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1007/s10951-009-0145-5en_US
dc.identifier.scopuseid_2-s2.0-84861229683en_US
dc.identifier.hkuros206254-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-84861229683&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume15en_US
dc.identifier.issue1en_US
dc.identifier.spage105en_US
dc.identifier.epage116en_US
dc.identifier.isiWOS:000300489600010-
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridWong, PWH=9734871500en_US
dc.identifier.scopusauthoridTo, IKK=23398547200en_US
dc.identifier.scopusauthoridLee, LK=12646190100en_US
dc.identifier.scopusauthoridLam, TW=7202523165en_US
dc.identifier.citeulike6302391-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats