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.ITCS.2018.30
URN: urn:nbn:de:0030-drops-83360
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8336/
Go to the corresponding LIPIcs Volume Portal

Dürr, Christoph ; Erlebach, Thomas ; Megow, Nicole ; Meißner, Julie

Scheduling with Explorable Uncertainty

pdf-format:
LIPIcs-ITCS-2018-30.pdf (0.6 MB)

Abstract

We introduce a novel model for scheduling with explorable uncertainty. In this model, the processing time of a job can potentially be reduced (by an a priori unknown amount) by testing the job. Testing a job j takes one unit of time and may reduce its processing time from the given upper limit p'_j (which is the time taken to execute the job if it is not tested) to any value between 0 and p'_j. This setting is motivated e.g. by applications where a code optimizer can be run on a job before executing it. We consider the objective of minimizing the sum of completion times on a single machine. All jobs are available from the start, but the reduction in their processing times as a result of testing is unknown, making this an online problem that is amenable to competitive analysis. The need to balance the time spent on tests and the time spent on job executions adds a novel flavor to the problem. We give the first and nearly tight lower and upper bounds on the competitive ratio for deterministic and randomized algorithms. We also show that minimizing the makespan is a considerably easier problem for which we give optimal deterministic and randomized online algorithms.

BibTeX - Entry

@InProceedings{drr_et_al:LIPIcs:2018:8336,
  author =	{Christoph D{\"u}rr and Thomas Erlebach and Nicole Megow and Julie Mei{\ss}ner},
  title =	{{Scheduling with Explorable Uncertainty}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{30:1--30:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Anna R. Karlin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8336},
  URN =		{urn:nbn:de:0030-drops-83360},
  doi =		{10.4230/LIPIcs.ITCS.2018.30},
  annote =	{Keywords: online scheduling, explorable uncertainty, competitive ratio, makespan, sum of completion times}
}

Keywords: online scheduling, explorable uncertainty, competitive ratio, makespan, sum of completion times
Collection: 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Issue Date: 2018
Date of publication: 12.01.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI