1 Search Results for "Scully, Ziv"

Document

DOI: 10.4230/LIPIcs.ITCS.2022.114

Uniform Bounds for Scheduling with Job Size Estimates

Authors: Ziv Scully, Isaac Grosof, and Michael Mitzenmacher

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

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).

Cite as

Ziv Scully, Isaac Grosof, and Michael Mitzenmacher. Uniform Bounds for Scheduling with Job Size Estimates. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 114:1-114:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.114},
  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}
}

Refine by Author
1 Grosof, Isaac
1 Mitzenmacher, Michael
1 Scully, Ziv

Refine by Classification
1 Mathematics of computing → Queueing theory
1 Theory of computation → Online algorithms
1 Theory of computation → Scheduling algorithms

Refine by Keyword
1 M/G/1 queue
1 Scheduling
1 algorithms with predictions
1 preemptive shortest job first (PSJF)
1 queueing systems
Show More...

Refine by Type
1 document

Refine by Publication Year
1 2022

1 Search Results for "Scully, Ziv"

Uniform Bounds for Scheduling with Job Size Estimates

Abstract

Cite as

Thanks for your feedback!

Could not send message