§3, p. 5 — a schedule with makespan at most d is a feasible solution of (LP) with d_i = t = d
ProvedUnrelatedSched.TwoApprox.yes_instance_lp_feasiblelinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1scheduling
Let and , and let be a schedule with makespan at most . Then its 0-1 matrix, if job is assigned to machine and otherwise, is a feasible solution of the linear program (LP) with
This is the 'yes' direction of the 2-relaxed decision procedure: if (LP) has no feasible point, no schedule meets the deadline .
Formalization Note Feasibility includes whenever , which holds because each processing time of an assigned job is at most its machine's load.
Preamble
import Mathlib import Definitions.Def_MatousekLP_Scheduling_Schedule import Definitions.Def_UnrelatedSched_TwoApprox_DeadlineLP
Formal statement
namespace UnrelatedSched.TwoApprox
open MatousekLP.Scheduling
/-- §3, p. 5: the 0-1 matrix of a schedule with makespan at most `d` is feasible for (LP) with
`d_1 = ⋯ = d_m = t = d`. -/
theorem yes_instance_lp_feasible {m n : ℕ} (P : Matrix (Fin m) (Fin n) ℕ) (d : ℝ)
(σ : Fin n → Fin m) (hσ : makespan (realTimes P) σ ≤ d) :
assignmentMatrix σ ∈ LPPolytope P (fun _ => d) d := by sorry
end UnrelatedSched.TwoApprox
Source
Lenstra, Shmoys, Tardos, Approximation algorithms for scheduling unrelated parallel machines, CWI Report OS-R8714 (1987), p. 5, §3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.