File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1145/2755573.2755582
- Scopus: eid_2-s2.0-84950267583
- WOS: WOS:000569710500022
Supplementary
- Citations:
- Appears in Collections:
Conference Paper: Speed scaling in the non-clairvoyant model
Title | Speed scaling in the non-clairvoyant model |
---|---|
Authors | |
Keywords | Scheduling Energy efficiency Online algorithms |
Issue Date | 2015 |
Publisher | ACM. |
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? |
Abstract | In 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 Identifier | http://hdl.handle.net/10722/218928 |
ISBN | |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Azar, Y | - |
dc.contributor.author | Devanur, NR | - |
dc.contributor.author | Huang, Z | - |
dc.contributor.author | Panigrahi, D | - |
dc.date.accessioned | 2015-09-18T07:01:21Z | - |
dc.date.available | 2015-09-18T07:01:21Z | - |
dc.date.issued | 2015 | - |
dc.identifier.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 | - |
dc.identifier.isbn | 978-1-4503-3588-1 | - |
dc.identifier.uri | http://hdl.handle.net/10722/218928 | - |
dc.description.abstract | In 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.language | eng | - |
dc.publisher | ACM. | - |
dc.relation.ispartof | SPAA '15: Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures | - |
dc.subject | Scheduling | - |
dc.subject | Energy efficiency | - |
dc.subject | Online algorithms | - |
dc.title | Speed scaling in the non-clairvoyant model | - |
dc.type | Conference_Paper | - |
dc.identifier.email | Huang, Z: zhiyi@cs.hku.hk | - |
dc.identifier.authority | Huang, Z=rp01804 | - |
dc.description.nature | link_to_OA_fulltext | - |
dc.identifier.doi | 10.1145/2755573.2755582 | - |
dc.identifier.scopus | eid_2-s2.0-84950267583 | - |
dc.identifier.hkuros | 250453 | - |
dc.identifier.spage | 133 | - |
dc.identifier.epage | 142 | - |
dc.identifier.isi | WOS:000569710500022 | - |
dc.publisher.place | United States | - |