Please use this identifier to cite or link to this item:
|Title:||Temperature aware online algorithms for minimizing flow time|
Fung, Stanley P. Y.
|Citation:||Theoretical Computer Science, 2017, 661, pp. 18-34|
|Abstract:||We consider the problem of minimizing the total flow time of a set of unit sized jobs in a discrete time model, subject to a temperature threshold. Each job has its release time and its heat contribution. At each time step the temperature of the processor is determined by its temperature at the previous time step, the job scheduled at this time step and a cooling factor. We show a number of lower bound results, including the case when the heat contributions of jobs are only marginally larger than a trivial threshold. Then we consider a form of resource augmentation by giving the online algorithm a higher temperature threshold, and show that the Hottest First algorithm can be made 1-competitive, while other common algorithms like Coolest First cannot. Finally we give some results in the offline case.|
|Embargo on file until:||22-Nov-2017|
|Rights:||Creative Commons “Attribution Non-Commercial No Derivatives” licence CC BY-NC-ND, further details of which can be found via the following link: http://creativecommons.org/licenses/by-nc-nd/4.0/ Archived with reference to SHERPA/RoMEO and publisher website.|
|Description:||A preliminary version of this paper appeared in the 10th Annual Conference on the Theory and Applications of Models of Computation (TAMC), 2013.|
|Appears in Collections:||Published Articles, Dept. of Computer Science|
Files in This Item:
|flowtime-j2.pdf||Post-review (final submitted author manuscript)||357.24 kB||Adobe PDF||View/Open|
Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.