Claim 3.8 — the jobs of an independent set can be scheduled within
ProvedFlowJobHardness.ColoringReduction.claim_3_8Let be a simple graph on vertices with a proper colouring into classes, let , and let be the generalized flow shop instance of the colouring reduction, with . For a vertex let be the set of the jobs of .
If is an independent set of , then the jobs admit a feasible schedule (nonnegative start times, the operations of each job in order, and no two operations overlapping on a machine) whose makespan satisfies
This is the building block of the completeness direction: a colouring with colours splits the jobs into such blocks.
Formalization Note. The published model's feasibility and makespan are taken relative to the job subset ; operations of the other jobs are ignored. "Scheduled within time units" is read as makespan .
import Mathlib import Definitions.Def_JobShopLTAS_Core_Instance import Definitions.Def_FlowJobHardness_ColoringReduction_Construction import Definitions.Def_FlowJobHardness_ColoringReduction_Schedule open JobShopLTAS.Core
namespace FlowJobHardness.ColoringReduction
/-- **Claim 3.8** (Mastrolilli–Svensson 2011, p. 20:17). If `IS` is an independent set of `G`,
then the jobs `⋃_{v ∈ IS} J^v` of `S(r, d)` have a feasible schedule with makespan at most
`2 · lb = 2 r^{2d}`. -/
theorem claim_3_8 {n d : ℕ} (G : SimpleGraph (Fin n)) (c : G.Coloring (Fin d)) (r : ℕ)
(IS : Finset (Fin n)) (hIS : G.IsIndepSet (IS : Set (Fin n))) :
∃ s : (inst G c r).Op → ℝ,
(inst G c r).IsFeasibleSchedule
(Finset.univ.filter fun q : Fin (size r d n) => jobVtx q ∈ IS) s ∧
(inst G c r).makespan
(Finset.univ.filter fun q : Fin (size r d n) => jobVtx q ∈ IS) s ≤
2 * (R r d : ℝ) := by sorry
end FlowJobHardness.ColoringReduction
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.