Summary
Scheduling jobs efficiently when their processing times are only estimated can be tricky. The authors studied a method called Smith's rule, which orders jobs by a specific ratio, to see how well it performs when actual times vary within known bounds. They found the exact worst-case performance ratio, which depends on how much the true times can differ from estimates. Their results show that this ratio can be precisely calculated and provide exact limits on how well any algorithm can do under these uncertainty conditions. They also offer a way to convert schedules optimized for estimated times into ones that remain robust despite uncertainties.
What this means in practice
- •For cloud resource schedulers: Use the exact robustness bounds to improve job scheduling under uncertain processing time estimates on parallel machines.
- •For manufacturing operations teams: Implement scheduling strategies that remain near optimal even when job durations deviate from planned times within known limits.
A theory result. No direct application yet.
Abstract
Smith's rule orders jobs by their weight-to-processing-time ratios. We study the robustness of its list schedule on identical parallel machines when job $j$ is ordered using a nominal processing time $μ_j$ and its true processing time satisfies $μ_j\leq p_j\leqαμ_j$, where $α\geq1$. We determine the exact worst-case approximation ratio against the clairvoyant optimum, taking the supremum over machine counts. The ratio is an explicit continuous piecewise-algebraic function of $α$. It equals the Kawaguchi--Kyan constant $(1+\sqrt{2})/2$ at $α=1$ and is exactly $\sqrtα$ for $α\geq4$. On one machine the exact ratio is $\sqrtα$. For every fixed machine count, no deterministic nonpreemptive algorithm can improve on this guarantee, even with knowledge of $α$. The proof reduces to a common nominal Smith ratio and endpoint errors. Cutting the list schedule at its minimum final machine load yields a prefix--suffix certificate; two packings of matching lower-bound instances explain the branches below $α=4$. We also prove a nominal-to-robust transfer: any fixed schedule ordered by nominal Smith ratios on each machine, with nominal approximation ratio $1+δ$, has realized ratio at most $\sqrtα+αδ$. A nominal approximation scheme then gives, for every fixed $\varepsilon>0$, a deterministic polynomial-time algorithm independent of $α$ with ratio $(1+\varepsilon)\sqrtα$ simultaneously for $1\leqα\leq4$.