Claim 2 — an incomparable pair has weight 1 if it lies in , and at most otherwise
ProvedSingleMachinePrec.IntervalReduction.claim_2interval-ordersp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1scheduling
Let be the Stage 2 instance with parameter , with precedence constraints the interval order , and let be the set of pairs defined on p. 663. For every pair of incomparable jobs,
So the nodes of of weight one are exactly the pairs of , and every other node has weight at most .
Formalization Note The statement holds for any ; the proof later takes .
Preamble
import Mathlib import Definitions.Def_SingleMachinePrec_IntervalReduction_Instance
Formal statement
namespace SingleMachinePrec.IntervalReduction
/-- Claim 2 (p. 663): an incomparable pair of jobs `(i, j)` has `p_i w_j = 1` if `(i, j) ∈ D`,
and `p_i w_j ≤ 1/k` otherwise. -/
theorem claim_2 {N : ℕ} {G : SimpleGraph (Fin N)} (L : TreeLayout G) (k : ℝ) (hk : 1 < k)
(x y : Job L) (hxy : Incomparable (prec L) x y) :
(InD L x y → procTime L k x * weight L k y = 1) ∧
(¬ InD L x y → procTime L k x * weight L k y ≤ 1 / k) := by sorry
end SingleMachinePrec.IntervalReduction
Source
Ambühl, Mastrolilli, Mutsanas, Svensson, On the Approximability of Single-Machine Scheduling with Precedence Constraints, Math. Oper. Res. 36(4) (2011), p. 663, Claim 2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.