Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2019.24
URN: urn:nbn:de:0030-drops-115867
URL: https://drops.dagstuhl.de/opus/volltexte/2019/11586/
Lucarelli, Giorgio ; Moseley, Benjamin ; Thang, Nguyen Kim ; Srivastav, Abhinav ; Trystram, Denis
Online Non-Preemptive Scheduling to Minimize Maximum Weighted Flow-Time on Related Machines
| pdf-format: |
|
Abstract
We consider the problem of scheduling jobs to minimize the maximum weighted flow-time on a set of related machines. When jobs can be preempted this problem is well-understood; for example, there exists a constant competitive algorithm using speed augmentation. When jobs must be scheduled non-preemptively, only hardness results are known. In this paper, we present the first online guarantees for the non-preemptive variant. We present the first constant competitive algorithm for minimizing the maximum weighted flow-time on related machines by relaxing the problem and assuming that the online algorithm can reject a small fraction of the total weight of jobs. This is essentially the best result possible given the strong lower bounds on the non-preemptive problem without rejection.
BibTeX - Entry
@InProceedings{lucarelli_et_al:LIPIcs:2019:11586,
author = {Giorgio Lucarelli and Benjamin Moseley and Nguyen Kim Thang and Abhinav Srivastav and Denis Trystram},
title = {{Online Non-Preemptive Scheduling to Minimize Maximum Weighted Flow-Time on Related Machines}},
booktitle = {39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
pages = {24:1--24:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-131-3},
ISSN = {1868-8969},
year = {2019},
volume = {150},
editor = {Arkadev Chattopadhyay and Paul Gastin},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11586},
URN = {urn:nbn:de:0030-drops-115867},
doi = {10.4230/LIPIcs.FSTTCS.2019.24},
annote = {Keywords: Online Algorithms, Scheduling, Resource Augmentation}
}
| Keywords: | Online Algorithms, Scheduling, Resource Augmentation | |
| Seminar: | 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019) | |
| Issue date: | 2019 | |
| Date of publication: | 04.12.2019 |
