The Exact Robustness of Smith's Rule with Predicted Processing Times

Overview & Synopsis

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$.