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
ProvedSkutellaCQP.Preempt.power_of_preemptionConsider jobs and unrelated parallel machines; job has weight , and on machine processing time and release date . For every feasible preemptive schedule (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 runs on machine before ) there is a feasible nonpreemptive schedule with
If moreover all release dates are , there is a feasible nonpreemptive schedule with
This is Corollary 4.6: the value of an optimal nonpreemptive schedule is at most a factor above the value of an optimal preemptive schedule, and at most a factor in the absence of nontrivial release dates. It bounds the "power of preemption" for .
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 for all .
import Mathlib import Definitions.Def_SkutellaCQP_Preempt_Setting
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.