PaperlayerView exact revision on arXiv

Source-linked AI summary

Robust Non-Clairvoyant Scheduling with Classification Models

Anthony Dugois, Vincent Fagnon, Giorgio Lucarelli

arXiv:2610.01343v1cs.LGcs.DS

TL;DR

Non-clairvoyant scheduling with unknown processing times has no constant-competitive algorithm. This paper uses a classifier’s confusion matrix to model uncertainty as permutations within predicted classes and analyzes non-adaptive, adaptive, and randomized strategies. Min-Cost is optimal among non-adaptive strategies for the three criteria, while adaptive or randomized algorithms can outperform it in specified cases.

  • Problem

    In non-clairvoyant single-machine scheduling, job processing times remain unknown until completion, and no constant-competitive algorithm is possible.

    Source: §1 · p. 2

  • Method

    The paper uses a classifier’s confusion matrix to characterize class counts in predicted groups and studies sequencing under Min-Max, Min-Max Regret, and Min-Expectation criteria.

    Source: §1 · p. 2, §2 · pp. 5–6

  • Results

    Min-Cost is optimal among non-adaptive algorithms for all three criteria, while randomized Min-Max Regret and adaptive Min-Expectation methods can outperform it in specified cases.

    Source: §2 · p. 6, §4.1 · p. 8, §4.2 · p. 8

  • Takeaways & Limitations

    The confusion-matrix model refines non-clairvoyant analysis by using classifier information to derive guarantees for worst-case and average cases.

    Source: §6 · p. 15

    The adaptive Min-Expectation algorithm is not polynomial in the encoded instance size even when K is bounded, because n can be exponential in that size.

    Source: §5.2 · p. 14

Abstract

from arXiv · show

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.

1 Introduction

Scheduling with unknown processing times is difficult, and a single scalar prediction-error score can miss useful structure in classifier errors. The paper uses a classifier’s confusion matrix to inform scheduling despite not knowing individual jobs’ true classes.

1 Introduction

  • A single scalar error score is too coarse to represent structured prediction patterns, such as a classifier that is accurate for one item class but not another.The introduction also notes that classifiers may be guaranteed never to overestimate or underestimate parameter values.Source: §1 · p. 2
  • A classifier’s K × K confusion matrix records counts of jobs predicted as each class against their true classes.Rows denote predicted classes and columns denote true classes.Source: §1 · p. 2
  • For jobs with identical processing times within each class, non-clairvoyant scheduling must choose an arbitrary order, whose worst case is an LPT schedule.With known job classes, SPT is optimal; the non-clairvoyant setting does not reveal a job’s class until completion.Source: §1 · p. 2
  • Knowing the confusion matrix reveals each predicted group’s class composition, which can help avoid the worst-case LPT schedule without identifying individual jobs’ classes.For jobs predicted as large, the matrix gives the counts that are actually small and actually large.Source: §1 · p. 3

2 Model Definition and Contributions

The paper models uncertain job classes through a known classifier confusion matrix, while leaving job order within each predicted group unknown. It compares sequencing strategies under worst-case and expected criteria, and studies when adaptive or randomized strategies can improve on the best non-adaptive strategy.

Model

  • Jobs are partitioned into K classes with class-specific processing times, and the objective is to minimize total completion time on one non-preemptive machine.The model orders the class processing times as λ1 < λ2 < ··· < λK.Source: §2 · p. 3

Knowledge model

  • The classifier’s known confusion matrix gives aggregate class counts within each predicted queue, but the true class of an individual job is revealed only at completion.The classifier is run on every job in advance; the authors leave analysis of inaccurate confusion matrices for future work.Source: §2 · pp. 3–4
  • A classifier is clairvoyant when each confusion-matrix row has at most one nonzero entry, and non-clairvoyant when only one row has nonzero entries.Other matrices lie between these extremes in the paper’s knowledge model.Source: §2 · p. 4

Uncertainty model

  • Uncertainty concerns the unknown ordering of jobs within each predicted queue, modeled as a scenario comprising one permutation per queue.A scheduling sequence specifies which queue to pull from at each step; the selected queue’s front job is executed.Source: §2 · p. 4

Sequencing algorithms

  • For a fixed scenario, Chain-Opt computes an optimal sequence by repeatedly scheduling the available chain prefix with the lowest average processing time.The queues correspond to chains of precedence relationships in the fixed scenario.Source: §2 · p. 5

Robustness criteria

  • Min-Max minimizes worst-case cost, Min-Max Regret minimizes worst-case deviation from the scenario optimum, and Min-Expectation minimizes expected cost over scenarios.Unless specified otherwise, scenarios are equiprobable; adaptive algorithms can change choices during execution, unlike non-adaptive algorithms.Source: §2 · pp. 5–6

Contributions and organization

  • Min-Cost is the best possible non-adaptive algorithm for Min-Max, Min-Max Regret, and Min-Expectation; adaptive or randomized methods improve on it only in specified settings.The paper reports improvements for randomized Min-Max Regret with particular binary-classifier matrix structures and an adaptive Min-Expectation dynamic program with a relative gap asymptotically greater than 4/3 on a specific family.Source: §2 · p. 6

3 Related Work

Prior work addresses scheduling uncertainty through non-clairvoyant, learning-augmented, stochastic, and classical robust models. This paper’s related-work discussion distinguishes its confusion-matrix uncertainty model from those approaches.

Non-clairvoyant and learning-augmented scheduling

  • No randomized algorithm has a constant competitive ratio for non-clairvoyant scheduling when processing times are revealed only at job completion.Learning-augmented work supplies predictions, and prior work on the sum of completion times mainly handles preemptive settings.Source: §3 · p. 6

Stochastic scheduling

  • Stochastic scheduling treats processing times as random variables with known distributions or moments, with SEPT optimal on a single machine.For general distributions, the passage reports an approximation ratio of Ω(n^1/4) for SEPT.Source: §3 · pp. 6–7

Classical robust optimization

  • Classical robust scheduling represents uncertainty through discrete scenarios or intervals, whereas this work represents it through permutations of predicted queues.Prior work establishes NP-hardness for several classical robust criteria; for Min-Max, approximation below 6/5 is NP-hard.Source: §3 · p. 7

Other uncertainty models

  • Query-based scheduling models let a scheduler pay to reveal uncertain data, while probabilistic prediction models limit the number of predictions used for permutation problems.The related work includes deterministic and randomized query results and adaptive and non-adaptive algorithms for two job types.Source: §3 · p. 7

4 An Oblivious Non-Adaptive Algorithm

Min-Cost processes queues in non-decreasing order of average processing time and is optimal across the non-adaptive Min-Max, Min-Expectation, and Min-Max Regret criteria, with a qualification for regret. For Min-Max, no adaptive or randomized algorithm can do better.

4 An Oblivious Non-Adaptive Algorithm

  • Min-Cost schedules each queue completely in non-decreasing order of average processing time.With rows ordered by average processing time, it processes R1, then R2, and so on.Source: §4 · p. 7

4.1 Min-Max problem

  • Min-Cost is optimal for Min-Max, and no adaptive or randomized algorithm can improve on it.The worst scenario for any sequence orders each queue in non-increasing processing-time order.Source: §4.1 · p. 8

4.2 Min-Expectation problem

  • When all scenarios are equiprobable, Min-Cost is optimal among non-adaptive algorithms for Min-Expectation.Source: §4.2 · p. 8

4.3 Min-Max Regret problem

  • For Min-Max Regret, Min-Cost is best among deterministic algorithms with two classes; the authors conjecture this extends to any number of classes.The analysis derives an upper bound for Min-Cost and a matching lower bound for deterministic algorithms in the binary-class case.Source: §4.3 · p. 9

5 Beyond Non-Adaptivity

Randomization can break the deterministic lower bound for Min-Max Regret under particular confusion-matrix structures, while adaptive scheduling improves on non-adaptive Min-Expectation on a specific family of instances.

5.1 Randomization for Min-Max Regret

  • For binary classifiers, Rand-Half breaks the deterministic lower bound under particular confusion-matrix structures by randomly choosing among three sequences.The sequence probabilities depend on the matrix structure.Source: §5.1 · p. 11, §5 · p. 11
  • The randomized-regret expressions switch between L1L2 − s1s2 and s1s2 − L1L2 across the stated imbalance conditions.The two cases cover opposite strict-inequality patterns, allowing equality in the other pair.Source: §5.1 · pp. 11–12

5.2 Adaptive Algorithms for Min-Expectation

  • Choosing the queue with the smallest current expected processing time is strictly suboptimal in the given 3-class example: its cost is 19.5 versus the optimum of 19.Source: §5.2 · p. 13
  • The optimal adaptive policy is a dynamic program, but it is not polynomial-time even when the number of classes is bounded.With bounded K, it is pseudopolynomial; n can be exponential in the instance size.Source: §5.2 · p. 14
  • For the Min-Expectation objective, on the specific family of instances M_K,x, the ratio of optimal non-adaptive to optimal adaptive expected costs is asymptotically close to 4/3.Source: §5.2 · pp. 13–14

6 Conclusions and Perspectives

The paper applies a classification- and confusion-matrix-based robustness model to single-machine scheduling, deriving guarantees for worst-case and average objectives. It also identifies extensions involving prediction quality, matrix structure, and multi-label classification.

6 Conclusions and Perspectives

  • The framework uses classifier information to derive robustness guarantees for both Min-Max Regret and Min-Expectation in non-clairvoyant scheduling.Source: §6 · p. 15
  • Future directions include robust algorithms for perfect predictions, studying matrix structure, and extending the model to multi-label classification and weighted completion-time scheduling.Source: §6 · p. 15

A Optimal Algorithm for 1|chains| P Cj

Chain-Opt produces an optimal schedule by repeatedly selecting a low-average-processing-time prefix from the available job chains.

A Optimal Algorithm for 1|chains| P Cj

  • Chain-Opt computes each chain prefix’s average processing time and schedules a minimum-average prefix, taking the longest such prefix in a tie.Each predicted class is treated as a chain of jobs.Source: A Optimal Algorithm for 1|chains| P Cj · p. 18

B Optimal Solution of Min-Max-Alpha (Theorem 5)

The proof minimizes the Min-Max-Alpha objective over the feasible parameters by analyzing boundary cases. It selects α1 = 1, α2 = 0, and α3 = 0, yielding the stated objective value.

B Optimal Solution of Min-Max-Alpha (Theorem 5)

C Proof of Theorem 6

Theorem 6 establishes that the dynamic program is optimal among adaptive algorithms. Its proof uses induction over states, and the algorithm selects the queue minimizing the state-value function.

C Proof of Theorem 6

  • At each state Et, DP selects the queue Rk* that minimizes f(Et).The induction starts from the zero-cost terminal state and establishes a lower bound for any adaptive algorithm's expected cost.Source: C Proof of Theorem 6 · p. 21
  • Theorem 6 identifies DP as an optimal adaptive algorithm, with complexity stated as O(…).The supplied passage truncates the complexity expression, so no order can be reported.Source: C Proof of Theorem 6 · p. 21
  • The complexity argument counts admissible values for each confusion-matrix entry and takes a minimum over K queue choices per state.The passage gives the state-counting approach but truncates the resulting bound.Source: C Proof of Theorem 6 · p. 21

D Expected-Cost Ratio Between Optimal Non-Adaptive and Adaptive Solutions

The analysis constructs instances on which the expected-cost ratio between optimal non-adaptive and adaptive solutions is asymptotically greater than 4K/(3K+1). It derives the bound using Min-Cost's expected cost and a half-and-check heuristic to bound optimal adaptive cost.

D Expected-Cost Ratio Between Optimal Non-Adaptive and Adaptive Solutions

  • The construction MK,x uses a K × K matrix with first-column entries x, last-column entries 1, and endpoint processing times λ1 = 0 and λK = 1.x is a positive odd integer.Source: D Expected-Cost Ratio Between Optimal… · p. 22
  • Half-and-Check divides each queue into half-blocks, checks the first half, and either executes or defers the second half based on whether it finds the large job.The analysis tracks block-internal costs and their delays to later blocks; the optimal adaptive DP costs no more than this heuristic.Source: D Expected-Cost Ratio Between Optimal… · p. 22
  • The proof decomposes each queue's contribution into internal cost and external delays, then uses a recurrence as queues are added.The recurrence tracks jobs scheduled after the terminal queue and large jobs scheduled before it.Source: D Expected-Cost Ratio Between Optimal… · pp. 23–24
  • The expected-cost ratio between optimal non-adaptive and optimal adaptive solutions is asymptotically greater than 4K/(3K+1).The proof derives the ratio on the constructed instance and obtains the stated asymptotic bound by choosing x sufficiently large.Source: D Expected-Cost Ratio Between Optimal… · p. 25
Loading 2610.01343v1…