File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Speed scaling in the non-clairvoyant model

TitleSpeed scaling in the non-clairvoyant model
Authors
KeywordsScheduling
Energy efficiency
Online algorithms
Issue Date2015
PublisherACM.
Citation
The 27th ACM symposium on Parallelism in Algorithms and Architectures (SPAA '15), Portland, OR., 13-15 June 2015. In Conference Proceedings, 2015, p. 133-142 How to Cite?
AbstractIn recent years, there has been a growing interest in speed scaling algorithms, where a set of jobs need to be scheduled on a machine with variable speed so as to optimize the flow-times of the jobs and the energy consumed by the machine. A series of results have culminated in constant-competitive algorithms for this problem in the clairvoyant model, i.e., when job parameters are revealed on releasing a job (Bansal, Pruhs, and Stein, SODA 2007; Bansal, Chan, and Pruhs, SODA 2009). Our main contribution in this paper is the first constant-competitive speed scaling algorithm in the nonclairvoyant model, which is typically used in the scheduling literature to model practical settings where job volume is revealed only after the job has been completely processed. Unlike in the clairvoyant model, the speed scaling problem in the non-clairvoyant model is non-trivial even for a single job. Our non-clairvoyant algorithm is defined by using the existing clairvoyant algorithm in a novel inductive way, which then leads to an inductive analytical tool that may be of independent interest for other online optimization problems. We also give additional algorithmic results and lower bounds for speed scaling on multiple identical parallel machines.
Persistent Identifierhttp://hdl.handle.net/10722/218928
ISBN

 

DC FieldValueLanguage
dc.contributor.authorAzar, Y-
dc.contributor.authorDevanur, NR-
dc.contributor.authorHuang, Z-
dc.contributor.authorPanigrahi, D-
dc.date.accessioned2015-09-18T07:01:21Z-
dc.date.available2015-09-18T07:01:21Z-
dc.date.issued2015-
dc.identifier.citationThe 27th ACM symposium on Parallelism in Algorithms and Architectures (SPAA '15), Portland, OR., 13-15 June 2015. In Conference Proceedings, 2015, p. 133-142-
dc.identifier.isbn978-1-4503-3588-1-
dc.identifier.urihttp://hdl.handle.net/10722/218928-
dc.description.abstractIn recent years, there has been a growing interest in speed scaling algorithms, where a set of jobs need to be scheduled on a machine with variable speed so as to optimize the flow-times of the jobs and the energy consumed by the machine. A series of results have culminated in constant-competitive algorithms for this problem in the clairvoyant model, i.e., when job parameters are revealed on releasing a job (Bansal, Pruhs, and Stein, SODA 2007; Bansal, Chan, and Pruhs, SODA 2009). Our main contribution in this paper is the first constant-competitive speed scaling algorithm in the nonclairvoyant model, which is typically used in the scheduling literature to model practical settings where job volume is revealed only after the job has been completely processed. Unlike in the clairvoyant model, the speed scaling problem in the non-clairvoyant model is non-trivial even for a single job. Our non-clairvoyant algorithm is defined by using the existing clairvoyant algorithm in a novel inductive way, which then leads to an inductive analytical tool that may be of independent interest for other online optimization problems. We also give additional algorithmic results and lower bounds for speed scaling on multiple identical parallel machines.-
dc.languageeng-
dc.publisherACM.-
dc.relation.ispartofSPAA '15: Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures-
dc.subjectScheduling-
dc.subjectEnergy efficiency-
dc.subjectOnline algorithms-
dc.titleSpeed scaling in the non-clairvoyant model-
dc.typeConference_Paper-
dc.identifier.emailHuang, Z: zhiyi@cs.hku.hk-
dc.identifier.authorityHuang, Z=rp01804-
dc.description.naturelink_to_OA_fulltext-
dc.identifier.doi10.1145/2755573.2755582-
dc.identifier.hkuros250453-
dc.identifier.spage133-
dc.identifier.epage142-
dc.publisher.placeUnited States-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats