An Adversarial Model for Scheduling with Testing
- PDF / 2,467,034 Bytes
- 46 Pages / 439.37 x 666.142 pts Page_size
- 21 Downloads / 262 Views
An Adversarial Model for Scheduling with Testing Christoph Dürr1 · Thomas Erlebach2 · Nicole Megow3 · Julie Meißner4 Received: 3 June 2019 / Accepted: 22 June 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract We introduce a novel adversarial 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. Keywords Explorable uncertainty · Competitive analysis · Lower bounds · Scheduling
This research was carried out in the framework of Matheon supported by Einstein Foundation Berlin, the German Science Foundation (DFG) under contract ME 3825/1 and BayerischFranzösisches Hochschulzentrum (BFHZ). Further support was provided by EPSRC Grant EP/ S033483/1 and the ANR Grant ANR-18-CE25-0008. The second author was supported by a study leave granted by University of Leicester during the early stages of the research. A preliminary version of this paper appeared in The 9th Innovations in Theoretical Computer Science Conference (ITCS), January 2018 [16]. * Christoph Dürr [email protected] Extended author information available on the last page of the article
13
Vol.:(0123456789)
Algorithmica
1 Introduction Uncertainty in scheduling has been modeled and investigated in many different ways, particularly in the frameworks of online optimization, stochastic optimization, and robust optimization. All these different approaches have the common assumption that the uncertain information, e.g., the processing time of a job, cannot be explored before making scheduling decisions. However, in many applications there is the opportunity to gain exact or more precise information at a certain additional cost, e.g., by investing time, money, or energy. It is a challenging problem to design algorithms that balance the cost for data exploration and the benefit for the quality of a solution. This involves quantifying the trade-off between exploration and exploitation, as it is ubiquitous in numerous applications. In t
Data Loading...
