Test or Run? Scheduling Jobs of Unknown Length
2026-08-31 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors look at a problem where a machine has many jobs to do, but it doesn't know how long each job will take until it spends time checking. Checking costs time, and sometimes it helps find a quick job to finish first, but other times it wastes time. They study when it's best for the machine to keep checking and when to stop and start working. The authors find the best strategies for these choices and show that the solutions can be simple and practical.
job schedulinginspection costoptimal algorithmsworst-case analysisinstance-optimalityonline algorithmsdecision makingtime complexity
Authors
Václav Rozhoň
Abstract
A machine faces many jobs whose lengths are hidden. Spending one unit of time to inspect a job may reveal a short job that should be finished now, or it may reveal nothing useful while every other job waits. When should the machine keep looking, and when should it start working? We study natural variants of this question and provide optimal algorithms in both the worst-case and instance-optimal frameworks. The resulting algorithms are often quite simple, which may make them useful in practice.