License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2022.114
URN: urn:nbn:de:0030-drops-157108
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15710/
Scully, Ziv ;
Grosof, Isaac ;
Mitzenmacher, Michael
Uniform Bounds for Scheduling with Job Size Estimates
Abstract
We consider the problem of scheduling to minimize mean response time in M/G/1 queues where only estimated job sizes (processing times) are known to the scheduler, where a job of true size s has estimated size in the interval [β s, α s] for some α ≥ β > 0. We evaluate each scheduling policy by its approximation ratio, which we define to be the ratio between its mean response time and that of Shortest Remaining Processing Time (SRPT), the optimal policy when true sizes are known. Our question: is there a scheduling policy that (a) has approximation ratio near 1 when α and β are near 1, (b) has approximation ratio bounded by some function of α and β even when they are far from 1, and (c) can be implemented without knowledge of α and β?
We first show that naively running SRPT using estimated sizes in place of true sizes is not such a policy: its approximation ratio can be arbitrarily large for any fixed β < 1. We then provide a simple variant of SRPT for estimated sizes that satisfies criteria (a), (b), and (c). In particular, we prove its approximation ratio approaches 1 uniformly as α and β approach 1. This is the first result showing this type of convergence for M/G/1 scheduling.
We also study the Preemptive Shortest Job First (PSJF) policy, a cousin of SRPT. We show that, unlike SRPT, naively running PSJF using estimated sizes in place of true sizes satisfies criteria (b) and (c), as well as a weaker version of (a).
BibTeX - Entry
@InProceedings{scully_et_al:LIPIcs.ITCS.2022.114,
author = {Scully, Ziv and Grosof, Isaac and Mitzenmacher, Michael},
title = {{Uniform Bounds for Scheduling with Job Size Estimates}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {114:1--114:30},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-217-4},
ISSN = {1868-8969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15710},
URN = {urn:nbn:de:0030-drops-157108},
doi = {10.4230/LIPIcs.ITCS.2022.114},
annote = {Keywords: Scheduling, queueing systems, algorithms with predictions, shortest remaining processing time (SRPT), preemptive shortest job first (PSJF), M/G/1 queue}
}
|
Keywords: |
|
Scheduling, queueing systems, algorithms with predictions, shortest remaining processing time (SRPT), preemptive shortest job first (PSJF), M/G/1 queue |
|
Collection: |
|
13th Innovations in Theoretical Computer Science Conference (ITCS 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
25.01.2022 |
