Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Corollary 4.6, p. 23 — for R | rᵢⱼ | Σ wⱼCⱼ, an optimal nonpreemptive schedule is within factor 3 of an optimal preemptive one, within 2 without release dates

Proved
SkutellaCQP.Preempt.power_of_preemption

by mikedeng1 · Oct 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

p2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1power-of-preemptionpreemptionschedulingunrelated-machinesweighted-completion-time

Consider nnn jobs and mmm unrelated parallel machines; job jjj has weight wj≥0w_j\ge0wj​≥0, and on machine iii processing time pij>0p_{ij}>0pij​>0 and release date rij≥0r_{ij}\ge0rij​≥0. For every feasible preemptive schedule PPP (jobs may be interrupted and resumed later on the same or another machine, a machine processes one job at a time, a job runs on one machine at a time, nothing of job jjj runs on machine iii before rijr_{ij}rij​) there is a feasible nonpreemptive schedule SSS with

∑jwjCj(S) ≤ 3∑jwjCj(P).\sum_j w_jC_j(S)\ \le\ 3\sum_j w_jC_j(P).j∑​wj​Cj​(S) ≤ 3j∑​wj​Cj​(P).

If moreover all release dates are 000, there is a feasible nonpreemptive schedule SSS with

∑jwjCj(S) ≤ 2∑jwjCj(P).\sum_j w_jC_j(S)\ \le\ 2\sum_j w_jC_j(P).j∑​wj​Cj​(S) ≤ 2j∑​wj​Cj​(P).

This is Corollary 4.6: the value of an optimal nonpreemptive schedule is at most a factor 333 above the value of an optimal preemptive schedule, and at most a factor 222 in the absence of nontrivial release dates. It bounds the "power of preemption" for R∣rij∣∑wjCjR\mid r_{ij}\mid\sum w_jC_jR∣rij​∣∑wj​Cj​.

Formalization Note The ratio of optima is stated in the equivalent form "for every preemptive schedule there is a nonpreemptive one within the factor", which needs no existence of optimal schedules. Schedules are finite lists of pieces (job, machine, start, stop); "nonpreemptive" means exactly one piece per job. Communication delays are not modelled; without them the preemptive class is the largest, so this form implies the bound under any delay model. "In the absence of nontrivial release dates" is read as rij=0r_{ij}=0rij​=0 for all i,ji,ji,j.

Preamble
import Mathlib
import Definitions.Def_SkutellaCQP_Preempt_Setting
Formal statement
namespace SkutellaCQP.Preempt

theorem power_of_preemption {m n : ℕ} (p : Fin m → Fin n → ℝ) (w : Fin n → ℝ)
    (r : Fin m → Fin n → ℝ)
    (hp : ∀ i j, 0 < p i j) (hw : ∀ j, 0 ≤ w j) (hr : ∀ i j, 0 ≤ r i j) :
    ∀ P : PSched m n, PFeasible p r P →
      (∃ S : PSched m n, PFeasible p r S ∧ Nonpreemptive S ∧ pval w S ≤ 3 * pval w P) ∧
      ((∀ i j, r i j = 0) →
        ∃ S : PSched m n, PFeasible p r S ∧ Nonpreemptive S ∧ pval w S ≤ 2 * pval w P) := by sorry

end SkutellaCQP.Preempt
Source
Skutella, Convex quadratic and semidefinite programming relaxations in scheduling, J. ACM 48 (2001), p. 23, Corollary 4.6
Human review
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 7, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me