Inequality (1) holds for the constructed schedule
ProvedDelayedSWPT.Extended.exists_sigmaEonline-algorithmsp2o-batch-pfp1ap2o-gran-per-chapterp2o-plan-paperp2o-v1scheduling
Let (P) be an instance, (2P) its doubled problem, (E) its extended problem with gap jobs , and the schedule of (E) induced by Delayed SWPT. For every optimal schedule of (2P) there is a feasible schedule of (E) with
In the paper, ends each nongap job at its completion time in , inserts the gap jobs block by block as early as possible, and shifts the gap-generating jobs left; Lemmas 4–7 bound the resulting change in cost. Together with Lemma 3 this proves the upper half of Theorem 8.
Formalization Note The statement is existential, so the construction of is left to the prover. In (2P), ; for a gap job , .
Preamble
import Mathlib import Definitions.Def_DelayedSWPT_Extended_Problem
Formal statement
namespace DelayedSWPT.Extended
open DelayedSWPT.Model
/-- Anderson and Potts (2004), §§3.4–3.6, proof of Theorem 8, p. 696: from an optimal schedule
`μ*` of (2P) one can construct a feasible schedule `σ_E` of (E) satisfying inequality (1)
`∑_{j∈J} wⱼ Cⱼ(σ_E) + ∑_{g∈G} w_g C_g(σ_E) ≤ ∑_{j∈J} wⱼ Cⱼ(μ*) + ∑_{g∈G} w_g C_g(π_E)`. -/
theorem exists_sigmaE {n : ℕ} (I : Instance n) (μstar : Fin n → ℕ)
(hμ : IsOptimal (double I).r (double I).p (double I).w μstar) :
∃ σE : EJob I → ℕ, IsFeasible (rE I) (pE I) σE ∧
∑ j : Fin n, I.w j * ((σE (Sum.inl j) + I.p j : ℕ) : ℝ) +
∑ g : gapTimes I, gapWeight I g * ((σE (Sum.inr g) + 1 : ℕ) : ℝ) ≤
∑ j : Fin n, I.w j * ((μstar j + 2 * I.p j : ℕ) : ℝ) +
∑ g : gapTimes I, gapWeight I g * ((g.1 + 1 : ℕ) : ℝ) := by sorry
end DelayedSWPT.Extended
Source
Anderson and Potts, Online Scheduling of a Single Machine to Minimize Total Weighted Completion Time, Math. Oper. Res. 29(3) (2004), pp. 692–696, §§3.4–3.6, proof of Theorem 8, inequality (1)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.