§9, p. 666 — val(σ) = Σᵢ (σ(i+1) − σ(i))·i = n² − Σᵢ σ(i)
ProvedSingleMachinePrec.Biclique.value_identitygantt-chartp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1scheduling
Let be an -by- bipartite graph and any schedule (any ordering) of all the jobs of . For let be the number of jobs of scheduled before jobs of have been scheduled. Then , and
The identity expresses the objective of through the profile of the schedule's "work line" in the two-dimensional Gantt chart; it turns the lower bound of Lemma 9.1 into an upper bound on .
Formalization Note The paper states this for an optimal schedule and sets by convention; here it is stated for every ordering of the jobs (feasibility is not needed), and is a consequence of the definition of , stated as the first conclusion.
Preamble
import Mathlib import Definitions.Def_SingleMachinePrec_Biclique_SG
Formal statement
namespace SingleMachinePrec.Biclique
/-- §9, p. 666 (proof of Lemma 9.1, value identity). Let `G = (U, V, E)` be an `n`-by-`n`
bipartite graph and `l` any sequence of all the jobs `U ∪ V` of `S_G`. With `σ(i)` the number of
jobs of `V` scheduled before `i` jobs of `U` have been scheduled (`vBefore l i`), one has
`σ(n + 1) = n`, and the value of `l` is
`Σ_{i=1}^{n} (σ(i + 1) − σ(i)) · i = n² − Σ_{i=1}^{n} σ(i)`. -/
theorem value_identity {U V : Type*} [Fintype U] [Fintype V] [DecidableEq U] [DecidableEq V]
(n : ℕ) (hU : Fintype.card U = n) (hV : Fintype.card V = n) (l : List (U ⊕ V))
(hl : MooreLateJobs.Shared.IsSchedule Finset.univ l) :
vBefore l (n + 1) = n ∧
valSG l = ∑ i ∈ Finset.Icc 1 n, ((vBefore l (i + 1) : ℝ) - (vBefore l i : ℝ)) * (i : ℝ) ∧
valSG l = (n : ℝ) ^ 2 - ∑ i ∈ Finset.Icc 1 n, (vBefore l i : ℝ) := by sorry
end SingleMachinePrec.Biclique
Source
Ambühl, Mastrolilli, Mutsanas, Svensson, On the Approximability of Single-Machine Scheduling with Precedence Constraints, Math. Oper. Res. 36(4) (2011), p. 666, §9, proof of Lemma 9.1 (displayed identity)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.