Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.7 — the interval consistency theorem for disjunctive sets

Proved
ComplexScheduling.interval_consistency_theorem

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

combinatoricsconstraint-propagationoperations-researchoptimizationscheduling

Consider an RCPSP instance with conjunction set CCC, disjunction set DDD and time windows [ri,di][r_i,d_i][ri​,di​], and let III be a disjunctive set for (C,D)(C,D)(C,D): at least two activities, any two of which are related by a disjunction or a conjunction, so that no two of them can be processed at the same time. Let J⊆IJ\subseteq IJ⊆I, let J′J'J′ and J′′J''J′′ be proper subsets of JJJ with J′∪J′′≠∅J'\cup J''\ne\emptysetJ′∪J′′=∅, and write P(J)=∑i∈JpiP(J)=\sum_{i\in J}p_iP(J)=∑i∈J​pi​. If

max⁡ν∈J∖J′, μ∈J∖J′′ν≠μ(dμ−rν)  <  P(J),(3.121)\max_{\substack{\nu\in J\setminus J',\ \mu\in J\setminus J''\\ \nu\ne\mu}}\bigl(d_\mu-r_\nu\bigr)\;<\;P(J) , \tag{3.121}ν∈J∖J′, μ∈J∖J′′ν=μ​max​(dμ​−rν​)<P(J),(3.121)

then in every feasible schedule — feasible for the RCPSP, satisfying the conjunctions CCC and the disjunctions DDD, and within the time 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.7, the general result from which the interval consistency tests of Section 3.6.4 (input, output, input-or-output, and the two negation tests) are read off by choosing J′J'J′ and J′′J''J′′. If neither conclusion held, the activity of JJJ starting first would be some ν∉J′\nu\notin J'ν∈/J′ and the one ending last some μ∉J′′\mu\notin J''μ∈/J′′, so all of JJJ would be processed inside [rν,dμ][r_\nu,d_\mu][rν​,dμ​], an interval too short for P(J)P(J)P(J) non-overlapping activities.

Formalization Note The maximum in (3.121) is stated as the equivalent family dμ<rν+P(J)d_\mu<r_\nu+P(J)dμ​<rν​+P(J) over the same index pairs, which has no junk value when the index set is empty (the family is then vacuous, as a maximum over an empty set, −∞-\infty−∞, would make it) and no natural-number subtraction. "Starts first" and "ends last" are read with ≤\le≤; on a disjunctive set with positive durations this is the strict reading, and the statement remains true without positivity, so none is assumed: the book invokes positivity only to justify restricting to ν≠μ\nu\ne\muν=μ, and in the case where that restriction empties the index set the conclusion holds outright. The RCPSP feasibility of the schedule is the book's "feasible" and is carried as a hypothesis, although the argument uses only the windows and the disjunctions.

Preamble
import Definitions.Def_ComplexScheduling_RCPSP
import Definitions.Def_ComplexScheduling_JobShop
import Definitions.Def_ComplexScheduling_ConstraintPropagation
Formal statement
namespace ComplexScheduling
theorem interval_consistency_theorem {n r : ℕ} (p : Fin n → ℕ) (Rcap : Fin r → ℕ)
    (demand : Fin n → Fin r → ℕ) (prec C D : Finset (Fin n × Fin n)) (rel dl : Fin n → ℕ)
    (I : Finset (Fin n)) (hI : IsDisjunctiveSet C D I)
    (J J' J'' : Finset (Fin n)) (hJI : J ⊆ I) (hJ' : J' ⊂ J) (hJ'' : J'' ⊂ J)
    (hne : (J' ∪ J'').Nonempty)
    (hcond : ∀ ν ∈ J \ J', ∀ μ ∈ J \ J'', ν ≠ μ → dl μ < rel ν + totalProcessing p J)
    (S : Fin n → ℕ) (hS : FeasibleSchedule p Rcap demand prec S) (hC : RespectsArcs p C S)
    (hD : SatisfiesDisjunctions p D 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.4, printed p. 169 (PDF p. 179), Theorem 3.7: "Let I be a disjunctive set and J′, J′′ ⊂ J ⊆ I with J′ ∪ J′′ ≠ ∅. If max_{ν∈J\J′, μ∈J\J′′, ν≠μ} (d_μ − r_ν) < P(J), (3.121) then in J an activity from J′ must start first or an activity from J′′ must end last in any feasible schedule."
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