Robust job scheduling improves with classifier error data
Robust Non-Clairvoyant Scheduling with Classification Models
Machine LearningData Structures and Algorithms
Summary
Scheduling jobs when you don’t know how long each will take is very hard and usually can’t be done very well. The authors look at a way to use information from a machine learning classifier that groups jobs into types, even if it sometimes mistakes one type for another. Using this information about classifier errors, they create scheduling methods that are more reliable in the worst cases and on average. They also show that adapting strategies based on the classification mistakes can sometimes perform better than fixed methods.
What this means in practice
- •For cloud resource schedulers: Improve task scheduling on servers by using classification error patterns to better anticipate job processing times and reduce overall completion delays.
- •For manufacturing operations planners: Plan machine task sequences more robustly by accounting for uncertain job durations using classification-based uncertainty modeling.
Authors
Anthony Dugois, Vincent Fagnon, Giorgio Lucarelli
Abstract
We study the classical single-machine scheduling problem of minimizing the sum of completion times of jobs in a non-clairvoyant setting, where the processing time of each job remains unknown until its completion. This is a hard problem for which no constant competitive algorithm is possible. Inspired by robust optimization and learning-augmented algorithms, we introduce a novel robustness framework that leverages structural information provided by a classification model to overcome this limitation. Specifically, we assume that jobs are partitioned into classes and we have access to the confusion matrix of the classifier, whose entry $(k,\ell)$ indicates the number of jobs predicted to belong to class~$k$ but that actually belong to class~$\ell$. In this manner, we are able to characterize uncertainty as a set of permutations within each predicted class, rather than as a collection of discrete numerical scenarios, avoiding the computational difficulty of classical robust metrics, such as Min-Max and Min-Max Regret. In addition to these worst-case metrics, we also consider the expected objective over all scenarios. We first propose an optimal non-adaptive strategy that is oblivious with respect to all three robust criteria. We then investigate adaptive and randomized algorithms, showing that they can outperform the optimal non-adaptive strategy when the matrix exhibits particular structural properties.