Non-clairvoyant Scheduling with Partial Predictions
This addresses scheduling efficiency in resource-constrained environments where prediction access is partial, representing an incremental advance in learning-augmented algorithms.
The paper tackles the non-clairvoyant scheduling problem with limited predictions, where only B out of n job sizes are available, establishing near-optimal bounds for perfect predictions and developing a learning-augmented algorithm that balances robustness, consistency, and smoothness.
The non-clairvoyant scheduling problem has gained new interest within learning-augmented algorithms, where the decision-maker is equipped with predictions without any quality guarantees. In practical settings, access to predictions may be reduced to specific instances, due to cost or data limitations. Our investigation focuses on scenarios where predictions for only $B$ job sizes out of $n$ are available to the algorithm. We first establish near-optimal lower bounds and algorithms in the case of perfect predictions. Subsequently, we present a learning-augmented algorithm satisfying the robustness, consistency, and smoothness criteria, and revealing a novel tradeoff between consistency and smoothness inherent in the scenario with a restricted number of predictions.