Name
Abstract | ||
|---|---|---|
We 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. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-87744-8_54 | ESA |
Keywords | Field | DocType |
dynamic speed,release time,extra speed,active job,scaling functions,new speed,active job count,existing speed,flow time,new speed function,weighted flow time,non-clairvoyant model,competitive ratio | Online algorithm,Discrete mathematics,Mathematical optimization,Speed scaling,Scheduling (computing),Computer science,Flow time,Real-time computing,Competitive algorithm,Dynamic speed scaling,Competitive analysis | Conference |
Volume | ISSN | Citations |
5193 | 0302-9743 | 46 |
PageRank | References | Authors |
1.98 | 20 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tak-Wah Lam | 1 | 1860 | 164.96 |
| Lap-Kei Lee | 2 | 406 | 21.59 |
| Isaac K. K. To | 3 | 132 | 6.41 |
| Prudence W. Wong | 4 | 75 | 4.46 |