License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2018.59
URN: urn:nbn:de:0030-drops-95226
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9522/
Lucarelli, Giorgio ;
Moseley, Benjamin ;
Thang, Nguyen Kim ;
Srivastav, Abhinav ;
Trystram, Denis
Online Non-Preemptive Scheduling to Minimize Weighted Flow-time on Unrelated Machines
Abstract
In this paper, we consider the online problem of scheduling independent jobs non-preemptively so as to minimize the weighted flow-time on a set of unrelated machines. There has been a considerable amount of work on this problem in the preemptive setting where several competitive algorithms are known in the classical competitive model. However, the problem in the non-preemptive setting admits a strong lower bound. Recently, Lucarelli et al. presented an algorithm that achieves a O(1/epsilon^2)-competitive ratio when the algorithm is allowed to reject epsilon-fraction of total weight of jobs and has an epsilon-speed augmentation. They further showed that speed augmentation alone is insufficient to derive any competitive algorithm. An intriguing open question is whether there exists a scalable competitive algorithm that rejects a small fraction of total weights.
In this paper, we affirmatively answer this question. Specifically, we show that there exists a O(1/epsilon^3)-competitive algorithm for minimizing weighted flow-time on a set of unrelated machine that rejects at most O(epsilon)-fraction of total weight of jobs. The design and analysis of the algorithm is based on the primal-dual technique. Our result asserts that alternative models beyond speed augmentation should be explored when designing online schedulers in the non-preemptive setting in an effort to find provably good algorithms.
BibTeX - Entry
@InProceedings{lucarelli_et_al:LIPIcs:2018:9522,
author = {Giorgio Lucarelli and Benjamin Moseley and Nguyen Kim Thang and Abhinav Srivastav and Denis Trystram},
title = {{Online Non-Preemptive Scheduling to Minimize Weighted Flow-time on Unrelated Machines}},
booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)},
pages = {59:1--59:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-081-1},
ISSN = {1868-8969},
year = {2018},
volume = {112},
editor = {Yossi Azar and Hannah Bast and Grzegorz Herman},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9522},
URN = {urn:nbn:de:0030-drops-95226},
doi = {10.4230/LIPIcs.ESA.2018.59},
annote = {Keywords: Online Algorithms, Scheduling, Resource Augmentation}
}
|
Keywords: |
|
Online Algorithms, Scheduling, Resource Augmentation |
|
Collection: |
|
26th Annual European Symposium on Algorithms (ESA 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
14.08.2018 |
