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

1 Introduction

• The parallel-machine RWSPT list rule has exact worst-case ratio L(α), with L(α) = √α for α ≥4.The exact ratio takes the supremum over machine counts, jobs, and instances with distortion at most α.Source: §1 · p. 3
• On one machine, RWSPT is √α-robust and best possible for deterministic nonpreemptive algorithms; a nominal PTAS gives ratio (1 + ε)√α for 1 ≤α ≤4.The polynomial-time algorithm is independent of α and constructs a fixed schedule from the nominal data.Source: §1 · p. 3

1.1 Our techniques

• The proof reduces arbitrary nominal ratios to a common ratio and then to endpoint instances where each job is either unstretched or stretched by the full distortion factor.For fixed list and comparison schedules, costs vary linearly with a job’s nominal time, so an extremum occurs at an interval endpoint.Source: §1.1 · pp. 4–5
• Three job classes with a common nominal Smith ratio produce two lower-bound packing regimes, whose distinct equality cases yield the two algebraic branches.The regimes differ in whether short and medium work fits on machines without a large job or residual short load must be spread across all machines.Source: §1.1 · pp. 5–6, Figure 2 · p. 6
• Cutting at the minimum final machine load creates a prefix and at most one suffix piece per machine, enabling separate lower-bound charges for the prefix and each suffix.The certificate preserves each piece’s list-schedule classification when pieces are redistributed in the optimal schedule.Source: §1.1 · pp. 5–6

1.2 Related work

• The paper’s scalar prefix–suffix certificate gives a reusable derivation of the classical Kawaguchi–Kyan bound and extends to track multiplicative processing-time distortion.The paper distinguishes this certificate from a semidefinite framework for scheduling games [14] and from robust flow-time models [1] [2].Source: §1.2 · pp. 7–8

1.3 Organization

• Section 2 establishes structural reductions and fixed-machine lower bounds, Section 3 proves the exact parallel-machine result, and Section 4 derives transfer-based algorithmic consequences.The appendices provide extremal parameters, scalar checks, supporting algebra, and further related work.Source: §1.3 · p. 8

2.1 Common notation and reductions

• Equal-ratio lifting shows that a bound for instances with a common nominal Smith ratio extends to arbitrary nominal ratios.The reduction inducts over distinct ratio classes.Source: §2.1 · pp. 9–10
• Endpoint reduction preserves the true processing times while replacing nominal data so each job is either unstretched or stretched by α.After normalizing the common ratio, the endpoint types satisfy p_j = μ_j or p_j = αμ_j.Source: §2.1 · p. 10

2.2 The exact single-machine bound

• √α bounds the one-machine ratio: after reduction, the algorithm may place stretched jobs first while the optimal true Smith order reverses the two blocks.The canonical-instance bound establishes the upper bound.Source: §2.2 · pp. 11–12
• For every fixed m, every deterministic nonpreemptive algorithm has worst-case ratio at least √α, even when it knows α.Together with the one-machine upper-bound analysis, this establishes the matching lower bound for every fixed machine count.Source: §2.2 · pp. 12–13

3.1 A preliminary bound

• Together with Lemma 2.7, the cited result proves that the ratio is exactly √α for every fixed machine count m, under the condition α ≥ 4.Source: §3.1 · p. 14

3.2 The exact curve

• The exact curve follows branches L1(alpha) through alpha0, L2(alpha) between alpha0 and 4, and sqrt(alpha) for alpha >= 4.The two packing configurations in Figure 2 yield the curve.Source: §3.2 · p. 15

3.3 Three-class instances for the lower bound

• Three job classes with the same nominal Smith ratio produce lower-bound instances whose limiting costs support the curve’s branches.Unstretched medium and large jobs and fully stretched short jobs can be ordered short, medium, then large; feasible comparison schedules bound the clairvoyant optimum from above.Source: §3.3 · pp. 16–17

3.4 The core upper-bound certificate

• After normalization and fragmentation, each machine has a unit-load prefix and at most one suffix piece, enabling a prefix–suffix certificate to upper-bound endpoint instances.The certificate charges the aggregate prefix and each suffix separately against optimal-schedule lower-bound contributions.Source: §3.4 · pp. 18, 20
• The proof lower-bounds OPT(Iη) using prefix pieces of total load m distributed across the optimal machines and Cauchy–Schwarz.The passage states OPT(Iη)≥m/2 and says Cauchy–Schwarz together with (8) gives a further lower bound.Source: §3.4 · p. 21
• The two Figure 2 extremal examples make the certificate tight in distinct suffix regions, explaining the branches and their transition at ℓ=u (pL=λ).In Case I, λ=1/u and pL≥λ; in Case II, λ=(ℓ+1−u)/ℓ and τ<pL<λ.Source: §3.4 · p. 21

4 Beyond list scheduling: near-optimal robustness

• The transfer proof uses endpoint processing vectors and the linearity of fixed-schedule cost versus the concavity of OPT(p).The proof also constructs a hybrid machine assignment to relate the candidate schedule to an optimum assignment.Source: §4 · p. 23
• An exact nominal optimum, reordered by nominal Smith ratios on each machine, has realized ratio at most √α and is optimal among deterministic nonpreemptive algorithms for each fixed m.The guarantee holds simultaneously for every α ≥ 1; exact nominal optimization may be expensive.Source: §4 · pp. 23–24
• For fixed ε > 0, a nominal PTAS yields a deterministic polynomial-time schedule with ratio (1 + ε)√α simultaneously for 1 ≤ α ≤ 4.The PTAS accuracy depends on the chosen range; one polynomial-time algorithm achieving this factor simultaneously for all α ≥ 1 remains open.Source: §4 · p. 24

5 Conclusion

• The parallel-machine list rule has exact worst-case ratio L(α), starting at the Kawaguchi–Kyan constant when α = 1 and equaling √α for α ≥ 4.On one machine, its exact robustness is √α; for α ≥ 4, the parallel-machine rule attains the optimal deterministic guarantee for each fixed machine count.Source: §5 · p. 24
• Common-ratio lifting and endpoint reduction reduce the analysis to jobs with a shared nominal Smith ratio and endpoint processing times.Cutting at the minimum final machine load yields equal-load prefixes and at most one suffix piece per machine; two packing regimes explain the algebraic branches.Source: §5 · p. 24
• A nominally Smith-ordered fixed schedule with nominal ratio 1 + δ has realized ratio at most √α + αδ; a nominal PTAS gives a deterministic polynomial-time (1 + ε)√α guarantee for 1 ≤ α ≤ 4.The PTAS schedule is independent of α, while achieving the same factor simultaneously for every α ≥ 1 with one such algorithm remains open.Source: §5 · p. 24

Declaration of AI Assistance

• The authors state that they reviewed and verified AI-assisted material and cited sources, and assume responsibility for the paper’s correctness.The assistance also covered presentation and formalization of some mathematical claims.Source: Declaration of AI Assistance · p. 24

A Properties of the parallel-machine target ratio

• The target is the worst-case parallel-machine ratio measured against OPT.The supplied passages introduce the ratio and identify OPT as its comparison cost.Source: A Properties of the parallel-machine… · p. 28
• Requiring distinct nominal Smith ratios leaves the supremum unchanged.This holds by Lemma B.1.Source: A Properties of the parallel-machine… · p. 28
• The first branch is characterized by a polynomial whose root is selected by the Section 3.2 parametrization.The polynomial is given in equation (20).Source: A Properties of the parallel-machine… · p. 28

Appendix D.1 derives the equality conditions and eliminations.

• The two algebraic branches meet continuously at α0.Lemma A.1 states that the branch definitions are well posed and continuous at their meeting point.Source: Appendix D.1 · p. 28
• As α approaches 4 from below, L2(α) approaches 2.The passage gives this endpoint limit for the second branch.Source: Appendix D.1 · p. 28
• For α0 < α < 4, the defining interval contains a unique simple root for the second branch.The appendix establishes existence from opposite endpoint signs and proves uniqueness and simplicity using a resultant and a Sturm count.Source: Appendix D.1 · p. 28

B Extremal parameters and the tight lower bound

• Below α=4, a three-class construction supplies limiting lower-bound costs, with parameters chosen to attain each algebraic branch.The section first removes nominal-ratio ties, then selects branch-attaining parameters and connects them to the upper-bound certificate.Source: B Extremal parameters and the tight… · pp. 28–30
• For α≥4, the lower bound is √α for every fixed machine count, and therefore also for R.These are the remaining values of the exact ratio function.Source: B Extremal parameters and the tight… · p. 30
• Cutting at minimum final load ℓ normalizes the prefix load to one, with medium jobs forming its type-A fraction and large jobs forming a suffix.The normalization divides nominal times, processing times, and weights by ℓ while preserving weight-to-processing-time ratios.Source: B Extremal parameters and the tight… · p. 30
• The L1 witness has prefix equality at x0 and high-region suffix equality at p1; the L2 witness has suffix equality at p0 in the middle region.The suffix sizes are the normalized large-job sizes in their respective constructions.Source: B Extremal parameters and the tight… · pp. 30–31
• The change from L1 to L2 occurs precisely when the large suffix size pL equals λ, equivalently when ℓ=u.The lower-witness condition identifies this branch transition.Source: B Extremal parameters and the tight… · p. 31
• The lower schedules reveal reference loads τ and λ for the upper proof, which then verifies the resulting inequalities for every instance.Table 1 links those loads and the normalized large-job size pL to equality in the suffix inequality.Source: B Extremal parameters and the tight… · p. 31, Table 1 · p. 31

C Certificate parameters and the tight upper bound

• A reusable prefix–suffix certificate proves the ratio for common-ratio instances and extends it to arbitrary WSPT instances.For the classical case it also derives the tight Kawaguchi–Kyan bound using two scalar checks.Source: C Certificate parameters and the tight… · p. 32
• For α below 4, the branch-specific parameters make the prefix residual vanish at x0 and the suffix residual tangent to zero at p0 or p1.The L2 witness uses the middle region at p0; the L1 witness uses the high region at p1.Source: C Certificate parameters and the tight… · p. 32
• Theorem 1.1 follows by matching the lower bound L(α) with the upper bound, with the lower bound unchanged when nominal Smith ratios must be distinct.The upper bound holds for every machine count before taking their supremum.Source: C Certificate parameters and the tight… · p. 34

D Algebraic certificates

• The algebraic appendix checks polynomial identities, resultants, and Sturm signs using exact arithmetic, but does not independently certify the scheduling or interval-continuity arguments.Supplementary scripts reproduce those algebraic checks.Source: D Algebraic certificates · p. 34

• For the L1 contact pattern, a parameter s is introduced and the prefix and high-contact equations are cleared of their common denominator.The two resulting numerators are used to derive the claimed implicit equation without an unrecorded elimination.Source: §D.1 · pp. 34–35
• For the L2 contact pattern, substitution before imposing a root equation gives exact factorizations.Source: §D.1 · p. 35
• The prefix and middle-suffix contacts are simultaneously active exactly on branch P II.Source: §D.1 · p. 35

D.2 The L2 root and feasible branch

• Endpoint signs and the feasible-branch sign analysis establish the selected P II branch and its sign condition.The selected root lies in (29/20, 73/50), where the sign check fixes the constant as positive.Source: §D.2 · pp. 35–36
• The selected L2 root is unique and simple, varies continuously with α, and converges to 2 as α approaches 4.The endpoint and resultant argument also establishes continuity at the branch point α0.Source: §D.2 · p. 36

D.3 The L2 lower witness

• The L2 lower-witness identities make the comparison exact, with the final contact yielding the active suffix equality pL = p0.Source: §D.3 · pp. 36–37

D.4 Signs and contacts for the L2 certificate

• The L2 certificate’s interval and denominator signs establish Qint > 0, and its two active tangencies are the identities used in Lemma C.2.Source: §D.4 · p. 37

D.5 Signs and contacts for the L1 certificate

• The L1 certificate audits the signs and tangencies used in Lemma C.3 across its parameter interval.The parametrization has positive denominators and λ > τ > 0 on the stated interval.Source: §D.5 · p. 38

E A two-job example

• With α = 3, the realization (p1, p2) = (3, 1) gives RWSPT ratio 17/14, exceeding ρKK, because the realized Smith order reverses the nominal order.The passage notes this is illustrative, not a worst-case instance.Source: E A two-job example · p. 39

F Further related work

• Interval relative-regret work already compares realized cost with OPT, while this paper establishes exact guarantees under common multiplicative distortion and extends the analysis to parallel machines.Prediction studies also examine makespan and queueing settings, [8],, [17], [23].Source: F Further related work · p. 39