DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2021.79

Restricted Adaptivity in Stochastic Scheduling

Authors: Guillaume Sagnol and Daniel Schmidt genannt Waldschmidt

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract

We consider the stochastic scheduling problem of minimizing the expected makespan on m parallel identical machines. While the (adaptive) list scheduling policy achieves an approximation ratio of 2, any (non-adaptive) fixed assignment policy has performance guarantee Ω((log m)/(log log m)). Although the performance of the latter class of policies are worse, there are applications in which non-adaptive policies are desired. In this work, we introduce the two classes of δ-delay and τ-shift policies whose degree of adaptivity can be controlled by a parameter. We present a policy - belonging to both classes - which is an 𝒪(log log m)-approximation for reasonably bounded parameters. In other words, an exponential improvement on the performance of any fixed assignment policy can be achieved when allowing a small degree of adaptivity. Moreover, we provide a matching lower bound for any δ-delay and τ-shift policy when both parameters, respectively, are in the order of the expected makespan of an optimal non-anticipatory policy.

Cite as

Guillaume Sagnol and Daniel Schmidt genannt Waldschmidt. Restricted Adaptivity in Stochastic Scheduling. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 79:1-79:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{sagnol_et_al:LIPIcs.ESA.2021.79,
  author =	{Sagnol, Guillaume and Schmidt genannt Waldschmidt, Daniel},
  title =	{{Restricted Adaptivity in Stochastic Scheduling}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{79:1--79:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.79},
  URN =		{urn:nbn:de:0030-drops-146603},
  doi =		{10.4230/LIPIcs.ESA.2021.79},
  annote =	{Keywords: stochastic scheduling, makespan minimzation, approximation algorithm, fixed assignment policy, non-anticipatory policy}
}

Search Results

Documents authored by Schmidt genannt Waldschmidt, Daniel

Restricted Adaptivity in Stochastic Scheduling

Abstract

Cite as

Thanks for your feedback!

Could not send message