An Adversarial Model for Scheduling with Testing

Christoph Dürr, Thomas Erlebach, Nicole Megow, Julie Meißner

Introduction

In traditional scheduling theory, uncertainty is often viewed as an immutable constraint. However, many real-world tasks allow for "explorable uncertainty," where an initial investment of resources can provide more precise information about a job's requirements. This paper introduces a novel adversarial model to study this trade-off, specifically focusing on how "testing" a job can reduce its processing time.

The Model: Explorable Uncertainty

The authors consider a single-machine environment where each job $j$ has a known upper bound on its processing time, denoted as $\bar{p}_j$. An algorithm has two choices for each job:

  1. Execute immediately: The job takes $\bar{p}_j$ time to complete.
  2. Test first: The algorithm spends one unit of time to "test" the job, revealing a potentially smaller actual processing time $p_j$. The job is then executed for $p_j$ time.

The fundamental challenge is the "testing penalty": while a test might reveal a significantly shorter execution time, the one-unit cost of the test delays every subsequent job in the schedule. The goal is to minimize either the sum of completion times or the maximum completion time (makespan).

Algorithmic Strategies

The paper evaluates several strategies using competitive analysis, comparing online algorithms against an omniscient offline adversary.

  • Thresholding: A deterministic approach where jobs are tested only if their potential time reduction exceeds a specific threshold.
  • Randomization: By testing jobs in a random order, algorithms can prevent an adversary from constructing a worst-case sequence that exploits a fixed deterministic order.
  • Specialized Algorithms (BEAT and UTE): These are optimized for "uniform" instances (where all jobs have the same $\bar{p}_j$) and "extreme uniform" instances (where $p_j$ is either 0 or $\bar{p}_j$).
A typical schedule structure showing the sequence of tests and executions.

As shown in the figure above, a typical schedule produced by these algorithms involves a structured block of tests followed by a mixture of immediate and delayed job executions, balancing the upfront cost of information gathering against the downstream benefits of shorter execution times.

Key Results

The authors provide nearly tight upper and lower bounds for various scenarios. A significant finding is that minimizing the sum of completion times is considerably more complex than minimizing the makespan. For the makespan objective, they achieve a tight deterministic ratio of $\phi \approx 1.618$ (the Golden Ratio) and a randomized ratio of $4/3$.

For the sum of completion times, the results are summarized in the following table:

Summary of competitive ratio bounds for minimizing the sum of completion times.

The analysis demonstrates that randomization provides a provable advantage, lowering the competitive ratio from a deterministic lower bound of 1.8546 to an upper bound of 1.7453. The "extreme uniform" case was identified as the most difficult scenario for algorithms to handle.

Conclusion and Future Work

This work establishes a rigorous framework for scheduling with testing on a single machine. The authors identify that the "extreme" cases—where tests reveal either massive savings or no savings at all—represent the hardest adversarial challenges. Future research directions include extending this model to parallel machine environments, flow shops, and scenarios where test times are job-dependent rather than uniform.

Summary updated

Abstract

We introduce a novel adversarial model for scheduling with explorable uncertainty. In this model, the processing time of a job can potentially be reduced (by an a priori unknown amount) by testing the job. Testing a job j takes one unit of time and may reduce its processing time from the given upper limit \(\bar{p}_j\) (which is the time taken to execute the job if it is not tested) to any value between 0 and \(\bar{p}_j\). This setting is motivated e.g., by applications where a code optimizer can be run on a job before executing it. We consider the objective of minimizing the sum of completion times on a single machine. All jobs are available from the start, but the reduction in their processing times as a result of testing is unknown, making this an online problem that is amenable to competitive analysis. The need to balance the time spent on tests and the time spent on job executions adds a novel flavor to the problem. We give the first and nearly tight lower and upper bounds on the competitive ratio for deterministic and randomized algorithms. We also show that minimizing the makespan is a considerably easier problem for which we give optimal deterministic and randomized online algorithms.
BibTeX
@inproceedings{durr2018adversarial,
  author = {Christoph Dürr and Thomas Erlebach and Nicole Megow and Julie Meißner},
  title = {{An Adversarial Model for Scheduling with Testing}},
  booktitle = {ITCS},
  year = {2018},
  doi = {10.4230/lipics.itcs.2018.30},
}
Figure