AI Balances Predictions and Greed in Scheduling

In many real-world systems, from computing resource management to manufacturing and satellite communication, tasks arrive over time and must be scheduled immediately without knowing what comes next. This online interval scheduling problem is notoriously difficult because no algorithm can guarantee a constant competitive ratio in general, meaning performance relative to an optimal offline solution is often poor. However, practical scenarios often provide partial information through historical trends or machine-learned predictions about future tasks. A new study introduces a framework that leverages these predictions to improve scheduling decisions while maintaining robust performance even when predictions are wrong, addressing a critical gap in irrevocable settings where decisions cannot be revoked.

The researchers developed the SemiTrust-and-Switch framework, which combines prediction-based and classical scheduling algorithms to balance consistency—performance under accurate predictions—and robustness—performance under adversarial inputs. This framework works by initially trusting predictions for intervals below a length threshold τ, while accepting longer intervals greedily, and switching to a backup algorithm if predictions are found inaccurate. For example, in a two-value instance with short and long intervals, using the Greedy algorithm as the backup, the framework achieves (1 + k/τ)-consistency, where k is the maximum interval length, and guarantees that the optimal solution's total length is at most max(θ, Δ + 1) times the algorithm's output plus τ, with θ being the competitive ratio of the backup algorithm and Δ the ratio of longest to shortest intervals.

Ology involves a binary prediction model where predictions arrive online with each interval, suggesting whether to accept or reject it. The framework evaluates predictions at each interval's release time, comparing the predicted solution's value to the offline optimum up to a computed evaluation point. If the prediction is suboptimal, it switches irrevocably to a classical algorithm like Greedy. The researchers also introduced a randomized algorithm called SmoothMerge, which probabilistically merges the Trust algorithm (following predictions) and Greedy. SmoothMerge accepts intervals based on probabilities pt and pg for the two strategies, achieving smooth degradation in performance as prediction quality worsens, with expected output bounded by expressions involving prediction error η and the outputs of Trust and Greedy.

Show that the SemiTrust-and-Switch framework is optimal for two-value instances, with lower bounds proving that no algorithm can achieve better robustness than Δ times the algorithm's output plus k/Δ while maintaining consistency better than Δ, even with full predictions. In experiments using real-world scheduling data from parallel machine benchmarks like NASA-iPSC-1993-3.1 and CTC-SP2-1996-3.1, SmoothMerge demonstrated graceful performance degradation as prediction error increased, outperforming pure Trust when predictions were unreliable while staying close to Greedy. For instance, with parameters pt=0.5 and pg=0.5, SmoothMerge achieved smoothness of 0.25*(1-η)*|Opt| and robustness of 0.33*|Greedy|, illustrating the trade-off between relying on predictions and maintaining baseline performance.

Are significant for industries relying on real-time scheduling, such as cloud computing and logistics, where machine learning forecasts can enhance efficiency but must not compromise reliability. By providing a tunable trade-off between consistency and robustness, this framework allows systems to adapt to prediction quality, reducing the risk of poor performance in unpredictable environments. The SmoothMerge algorithm's smoothness property means performance declines gradually with prediction errors, offering a practical solution for dynamic settings where prediction accuracy varies over time.

Limitations include the framework's reliance on a binary prediction model, which may not capture all nuances of real-world data, and the assumption that intervals arrive in non-decreasing order of release times. The study focuses on proportional-weight objectives where task value depends on duration, leaving gaps for other variants like weighted intervals or revocable settings. Additionally, while lower bounds are tight for two-value instances, there remains a gap between upper and lower bounds for general instances, indicating room for further refinement in more complex scenarios.