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.ESA.2023.38
URN: urn:nbn:de:0030-drops-186915
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18691/
Damerius, Christoph ;
Kling, Peter ;
Li, Minming ;
Xu, Chenyang ;
Zhang, Ruilong
Scheduling with a Limited Testing Budget: Tight Results for the Offline and Oblivious Settings
Abstract
Scheduling with testing falls under the umbrella of the research on optimization with explorable uncertainty. In this model, each job has an upper limit on its processing time that can be decreased to a lower limit (possibly unknown) by some preliminary action (testing). Recently, [Christoph Dürr et al., 2020] has studied a setting where testing a job takes a unit time, and the goal is to minimize total completion time or makespan on a single machine. In this paper, we extend their problem to the budget setting in which each test consumes a job-specific cost, and we require that the total testing cost cannot exceed a given budget. We consider the offline variant (the lower processing time is known) and the oblivious variant (the lower processing time is unknown) and aim to minimize the total completion time or makespan on a single machine.
For the total completion time objective, we show NP-hardness and derive a PTAS for the offline variant based on a novel LP rounding scheme. We give a (4+ε)-competitive algorithm for the oblivious variant based on a framework inspired by the worst-case lower-bound instance. For the makespan objective, we give an FPTAS for the offline variant and a (2+ε)-competitive algorithm for the oblivious variant. Our algorithms for the oblivious variants under both objectives run in time ?(poly(n/ε)). Lastly, we show that our results are essentially optimal by providing matching lower bounds.
BibTeX - Entry
@InProceedings{damerius_et_al:LIPIcs.ESA.2023.38,
author = {Damerius, Christoph and Kling, Peter and Li, Minming and Xu, Chenyang and Zhang, Ruilong},
title = {{Scheduling with a Limited Testing Budget: Tight Results for the Offline and Oblivious Settings}},
booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)},
pages = {38:1--38:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-295-2},
ISSN = {1868-8969},
year = {2023},
volume = {274},
editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18691},
URN = {urn:nbn:de:0030-drops-186915},
doi = {10.4230/LIPIcs.ESA.2023.38},
annote = {Keywords: scheduling, total completion time, makespan, LP rounding, competitive analysis, approximation algorithm, NP hardness, PTAS}
}
|
Keywords: |
|
scheduling, total completion time, makespan, LP rounding, competitive analysis, approximation algorithm, NP hardness, PTAS |
|
Collection: |
|
31st Annual European Symposium on Algorithms (ESA 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
30.08.2023 |
