Lemma 3.10 — a job finishing by has a fraction at least of good long-operations
ProvedFlowJobHardness.ColoringReduction.lemma_3_10Let be a simple graph on vertices with a proper colouring into classes, let be an integer, and let be the generalized flow shop instance of the colouring reduction, with . Fix a feasible schedule of all jobs.
Let be a job of frequency , so has long-operations, each of length . If the completion time of is at most , then the number of good long-operations of (those followed by the next long-operation of within delay ) satisfies
In the paper this is applied to the jobs that finish within . It is the analogue for of Lemma 2.2 for the flow shop gap instance.
Formalization Note. The paper's context ("all jobs (that were not disregarded) have completion time at most , which is by assumption at most ") becomes the hypothesis on the single job . The fraction is stated as a count, multiplied out by the number of long-operations of .
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.10** (Mastrolilli–Svensson 2011, p. 20:18). For `r ≥ 1`, in a feasible schedule
of `S(r, d)`, every job `q` of frequency `f` whose completion time is at most `r · lb =
r · r^{2d}` has at least `(1 - 4/r) · r^{2f}` good long-operations, i.e. a fraction at least
`1 - 4/r` of its `r^{2f}` long-operations is good. -/
theorem lemma_3_10 {n d : ℕ} (G : SimpleGraph (Fin n)) (c : G.Coloring (Fin d)) (r : ℕ)
(hr : 1 ≤ r) (s : (inst G c r).Op → ℝ)
(hs : (inst G c r).IsFeasibleSchedule Finset.univ s)
(q : Fin (size r d n)) (hq : jobCompletion G c r s q ≤ (r : ℝ) * (R r d : ℝ)) :
(1 - 4 / (r : ℝ)) * (r : ℝ) ^ (2 * jobFreq c q) ≤ (goodCount G c r s q : ℝ) := by sorry
end FlowJobHardness.ColoringReduction
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.