1601. Learning-augmented algorithms for robust scheduling
Invited abstract in session TA-7: Scheduling models and algorithms II, stream Scheduling and Project Management.
Tuesday, 8:30-10:00Room: Clarendon GR.01
Authors (first author is the speaker)
| 1. | Thomas Lidbetter
|
| Rutgers Business School, Rutgers University | |
| 2. | Spyros Angelopoulos
|
| CNRS and Sorbonne University | |
| 3. | Konstantinos Panagiotou
|
| Maths, University of Munich |
Abstract
We consider the classic single machine scheduling problem of minimizing some weighted sum of completion times of a set of jobs with given processing times. If the weights are unknown, the problem of finding a randomized scheduled to minimize the worst-case sum of completion times can be viewed as a zero-sum game between a Hider, who hides a target in one of a finite set of boxes with search times, and a Searcher who looks in the boxes one-by-one with the aim of minimizing the expected time to find the target. We consider this game in a learning-augmented setting, where a potentially erroneous prediction is given about the weights of the jobs (or location of the target). We establish tight tradeoffs between "consistency" of a policy (that is, the worst-case sum of completion times if the prediction is correct) and the "robustness" (that is, the worst-case sum of completion times regardless of the correctness of the prediction). We extend our results to the case of unreliable scheduling, where there is a given probability that when the machine attempts to process a job, it is unsuccessful.
Keywords
- Scheduling
- Algorithms
- Game Theory
Status: accepted
Back to the list of papers