Lemma 3.12 — some machine group has
ProvedFlowJobHardness.ColoringReduction.lemma_3_12Let be a simple graph on vertices with a proper colouring into classes, let be an integer, let be a real number with , and let be the generalized flow shop instance of the colouring reduction, with . Fix a feasible schedule of all jobs in which at least half of the jobs finish within , and let be the sets of first halves of good long-operations of those jobs on the machines , with covered lengths .
Then there is a group index such that
This is the counting step of the soundness proof: a large amount of first-half time is concentrated in a single machine group.
Formalization Note. "At least half the jobs" is . The paper proves the lemma "in the very same way as Lemma 2.4", whose last step uses "for a sufficiently large "; with the non-strict inequality the threshold is , which is the explicit hypothesis here.
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
/-- **Lemma 3.12** (Mastrolilli–Svensson 2011, p. 20:18). Let `r ≥ 8` and `0 < L ≤ r`, and
let `s` be a feasible schedule of `S(r, d)` in which at least half of the `r^{2d} n` jobs
finish within `L · lb`. Then (keeping only those jobs in `T_{g,v}`) there is a group
`g ∈ {1, …, r^{2d}}` with `∑_{v ∈ V} L(T_{g,v}) ≥ lb · n / 8`. -/
theorem lemma_3_12 {n d : ℕ} (G : SimpleGraph (Fin n)) (c : G.Coloring (Fin d)) (r : ℕ)
(hr : 8 ≤ r) (L : ℝ) (hL0 : 0 < L) (hLr : L ≤ r) (s : (inst G c r).Op → ℝ)
(hs : (inst G c r).IsFeasibleSchedule Finset.univ s)
(hhalf : (size r d n : ℝ) ≤ 2 * (finishedCount G c r s L : ℝ)) :
∃ g : ℕ, 1 ≤ g ∧ g ≤ R r d ∧
(R r d : ℝ) * n / 8 ≤ ∑ v : Fin n, coveredLength G c r s L g v := by sorry
end FlowJobHardness.ColoringReduction
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.