Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.8 — the interval consistency theorem for a cumulative resource

Proved
ComplexScheduling.cumulative_consistency_theorem

by naimengye · Sep 23, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatoricsconstraint-propagationoperations-researchoptimizationscheduling

Consider an RCPSP instance with time windows [ri,di][r_i,d_i][ri​,di​] and a renewable resource kkk of capacity RkR_kRk​; let IkI_kIk​ be the activities that need resource kkk, wi=rikpiw_i=r_{ik}p_iwi​=rik​pi​ their work and W(J)=∑i∈JwiW(J)=\sum_{i\in J}w_iW(J)=∑i∈J​wi​. Let J⊆IkJ\subseteq I_kJ⊆Ik​ and let J′,J′′J',J''J′,J′′ be proper subsets of JJJ. If

Rk(max⁡μ∈J∖J′′dμ  −  min⁡ν∈J∖J′rν)  <  W(J),(3.145)R_k\Bigl(\max_{\mu\in J\setminus J''}d_\mu\;-\;\min_{\nu\in J\setminus J'}r_\nu\Bigr)\;<\;W(J) , \tag{3.145}Rk​(μ∈J∖J′′max​dμ​−ν∈J∖J′min​rν​)<W(J),(3.145)

then in every feasible schedule (feasible for the RCPSP and within the windows) an activity from J′J'J′ starts first in JJJ or an activity from J′′J''J′′ ends last in JJJ.

This is Theorem 3.8, the cumulative counterpart of Theorem 3.7: instead of "the activities of JJJ cannot overlap" the argument uses "the resource supplies at most RkR_kRk​ units per time unit", so an interval of length LLL offers RkLR_kLRk​L units of work, and if the activities of JJJ were all processed between the earliest head of J∖J′J\setminus J'J∖J′ and the latest deadline of J∖J′′J\setminus J''J∖J′′ they would have less than W(J)W(J)W(J) available.

Formalization Note The condition is the family Rkdμ<Rkrν+W(J)R_kd_\mu<R_kr_\nu+W(J)Rk​dμ​<Rk​rν​+W(J) over ν∈J∖J′\nu\in J\setminus J'ν∈J∖J′, μ∈J∖J′′\mu\in J\setminus J''μ∈J∖J′′, equivalent to (3.145) and free of subtraction. Unlike Theorem 3.7 the book imposes no ν≠μ\nu\ne\muν=μ here, and the theorem has no hypothesis J′∪J′′≠∅J'\cup J''\ne\emptysetJ′∪J′′=∅: with J′=J′′=∅J'=J''=\emptysetJ′=J′′=∅ the conclusion is false and the theorem says that no feasible schedule exists, which is the cumulative infeasibility test. "Starts first" is read with ≤\le≤, so a tie for the earliest start counts, which is what the book's proof uses when several activities of a cumulative resource start together. J⊆IkJ\subseteq I_kJ⊆Ik​ is the hypothesis that every activity of JJJ has positive demand for kkk.

Preamble
import Definitions.Def_ComplexScheduling_RCPSP
import Definitions.Def_ComplexScheduling_ConstraintPropagation
Formal statement
namespace ComplexScheduling
theorem cumulative_consistency_theorem {n r : ℕ} (p : Fin n → ℕ) (Rcap : Fin r → ℕ)
    (demand : Fin n → Fin r → ℕ) (prec : Finset (Fin n × Fin n)) (rel dl : Fin n → ℕ)
    (k : Fin r) (J J' J'' : Finset (Fin n)) (hJk : ∀ i ∈ J, 0 < demand i k)
    (hJ' : J' ⊂ J) (hJ'' : J'' ⊂ J)
    (hcond : ∀ ν ∈ J \ J', ∀ μ ∈ J \ J'',
      Rcap k * dl μ < Rcap k * rel ν + totalWork p demand k J)
    (S : Fin n → ℕ) (hS : FeasibleSchedule p Rcap demand prec S) (hw : WithinWindows rel dl p S) :
    (∃ i ∈ J', StartsFirstIn S J i) ∨ ∃ i ∈ J'', EndsLastIn p S J i := by sorry
end ComplexScheduling
Source
Peter Brucker and Sigrid Knust, Complex Scheduling, 2nd ed., Springer 2012, https://doi.org/10.1007/978-3-642-23929-8 — Section 3.6.5, printed p. 186 (PDF p. 196), Theorem 3.8: "Let J′, J′′ ⊂ J ⊆ I_k. If R_k · max_{ν∈J\J′, μ∈J\J′′} (d_μ − r_ν) = R_k · (max_{μ∈J\J′′} d_μ − min_{ν∈J\J′} r_ν) < W(J), (3.145) then in J an activity from J′ must start first or an activity from J′′ must end last."
Human review
  • Endorsed by Shuze Chen · Sep 25, 2026

    Confirmed by the moderator at approval.

  • Endorsed by naimengye · Sep 25, 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