Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Inequality (1) holds for the constructed schedule σE\sigma_EσE​

Proved
DelayedSWPT.Extended.exists_sigmaE

by mikedeng1 · Oct 4, 2026 · Mathlib 0df444a (Lean v4.33.1)

online-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 GGG, and πE\pi_EπE​ the schedule of (E) induced by Delayed SWPT. For every optimal schedule μ∗\mu^*μ∗ of (2P) there is a feasible schedule σE\sigma_EσE​ of (E) with

∑j∈JwjCj(σE)+∑g∈GwgCg(σE)≤∑j∈JwjCj(μ∗)+∑g∈GwgCg(πE).(1)\sum_{j\in J} w_j C_j(\sigma_E) + \sum_{g\in G} w_g C_g(\sigma_E) \le \sum_{j\in J} w_j C_j(\mu^*) + \sum_{g\in G} w_g C_g(\pi_E). \tag{1}j∈J∑​wj​Cj​(σE​)+g∈G∑​wg​Cg​(σE​)≤j∈J∑​wj​Cj​(μ∗)+g∈G∑​wg​Cg​(πE​).(1)

In the paper, σE\sigma_EσE​ ends each nongap job jjj at its completion time in μ∗\mu^*μ∗, 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 σE\sigma_EσE​ is left to the prover. In (2P), Cj(μ∗)=μj∗+2pjC_j(\mu^*) = \mu^*_j + 2p_jCj​(μ∗)=μj∗​+2pj​; for a gap job gtg_tgt​, Cg(πE)=t+1C_g(\pi_E) = t + 1Cg​(πE​)=t+1.

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
  • Endorsed by Shuze Chen · Oct 4, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 4, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me