Please use this identifier to cite or link to this item: http://hdl.handle.net/2381/39199
Title: Temperature aware online algorithms for minimizing flow time
Authors: Birks, Martin
Fung, Stanley P. Y.
First Published: 22-Nov-2016
Publisher: Elsevier
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.
DOI Link: 10.1016/j.tcs.2016.10.022
ISSN: 0304-3975
Links: http://www.sciencedirect.com/science/article/pii/S0304397516306004
http://hdl.handle.net/2381/39199
Embargo on file until: 22-Nov-2017
Version: Post-print
Status: Peer-reviewed
Type: Journal Article
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:
File Description SizeFormat 
flowtime-j2.pdfPost-review (final submitted author manuscript)357.24 kBAdobe PDFView/Open


Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.