2026-07-25T02:33:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9522 2024-03-06T10:43:57Z ddc:004 open_access

Online Non-Preemptive Scheduling to Minimize Weighted Flow-time on Unrelated Machines Lucarelli, Giorgio Moseley, Benjamin Thang, Nguyen Kim Srivastav, Abhinav Trystram, Denis Online Algorithms Scheduling Resource Augmentation 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Giorgio Lucarelli and Benjamin Moseley and Nguyen Kim Thang and Abhinav Srivastav and Denis Trystram 2018 Is Part Of LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2018.59 urn:nbn:de:0030-drops-95226 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.59 eng https://creativecommons.org/licenses/by/3.0/legalcode