Remark 3.6 — in S(r, d) every job length and every machine load is , and a job has at most operations
ProvedFlowJobHardness.ColoringReduction.remark_3_6Let 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 machines and jobs. Then:
- every job has length (total processing time) ;
- every machine has load (total processing time of the operations assigned to it) ;
- if every vertex of has degree at most , then every job has at most operations.
Consequently the trivial lower bound on the optimal makespan equals , the unit in which all bounds of the reduction are expressed.
Formalization Note. The machine and job counts are definitional (both types are Fin (r^{2d} n)), so only the three listed properties are stated. The degree bound is a hypothesis for all rather than the maximum degree itself, which makes the statement apply to every upper bound. The section introduction (p. 20:12) states the weaker count "at most operations"; the two agree when , as in the proof of Theorem 1.2.
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
/-- **Remark 3.6** (Mastrolilli–Svensson 2011, p. 20:17). In `S(r, d)` (which has `r^{2d} n`
machines and `r^{2d} n` jobs by construction) every job has length `r^{2d}`, every machine has
load `r^{2d}`, and if every vertex of `G` has degree at most `Δ` then every job has at most
`(Δ + 1) r^{2d}` operations. -/
theorem remark_3_6 {n d : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj]
(c : G.Coloring (Fin d)) (r : ℕ) :
(∀ q : Fin (size r d n), (inst G c r).jobLength q = (R r d : ℝ)) ∧
(∀ p : Fin (size r d n), (inst G c r).load p = (R r d : ℝ)) ∧
(∀ Δ : ℕ, (∀ v : Fin n, G.degree v ≤ Δ) →
∀ q : Fin (size r d n), (inst G c r).μ q ≤ (Δ + 1) * R r d) := by sorry
end FlowJobHardness.ColoringReduction
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.