.png){kind=icon}
.png){kind=icon}
Return
Learning-Augmented Scheduling
.png){kind=icon}
PRE
AI
DOI：10.1109/TC.2024.3441856.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The recent revival in learning theory has provided us with improved capabilities for accurate predictions. This work contributes to an emerging research agenda of online scheduling with predictions by studying makespan minimization in uniformly related machine non-clairvoyant scheduling with job size predictions. Our task is to design online algorithms that use predictions and have performance guarantees tied to prediction quality. We first propose a simple algorithm-independent prediction error metric to quantify prediction quality. Then we design an offline improved 2-relaxed decision procedure approximating the optimal schedule to effectively use the predictions. With the decision procedure, we propose an online O(min {log eta,log m})-competitive static scheduling algorithm assuming a known prediction error. We use this algorithm to construct a robust O(min {log eta,log m})-competitive static scheduling algorithm that does not assume a known error. Finally, we extend these static scheduling algorithms to address dynamic scheduling where jobs arrive over time. The dynamic scheduling algorithms attain the same competitive ratios as the static ones. The presented algorithms require just moderate predictions to break the Omega(log m) competitive ratio lower bound, showing the potential of predictions in managing uncertainty.
Keywords:
Prediction algorithms
Heuristic algorithms
Optimal scheduling
Dynamic scheduling
Single machine scheduling
Scheduling algorithms
Minimization
Learning-augmented algorithms
scheduling
makespan
predictions
Journal
IF:
3.8
Papers:
5.3K
Citations:
9.8K