Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2.5.7 — every feasible schedule obeys a minimal delaying mode of each forbidden set

Proved
ProjSchedTW.DelayingModes.exists_minimal_delaying_mode

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

branch-and-bounddelaying-alternativesforbidden-setsp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1project-scheduling

Let FFF be a forbidden set of a project, i.e. ∑i∈Frik>Rk\sum_{i\in F}r_{ik}>R_k∑i∈F​rik​>Rk​ for some resource kkk. For every feasible schedule SSS (time-feasible and resource-feasible) there is a minimal delaying mode (i,B)(i,B)(i,B) for FFF — BBB is a minimal delaying alternative for FFF and i∈F∖Bi\in F\setminus Bi∈F∖B — such that

Sj≥Si+pi(j∈B).(2.5.4)S_j\ge S_i+p_i\qquad(j\in B).\qquad(2.5.4)Sj​≥Si​+pi​(j∈B).(2.5.4)

Thus every feasible schedule resolves the conflict of FFF by letting one fixed activity iii of FFF complete before all activities of a minimal delaying alternative start. This is the completeness statement behind the enumeration scheme of De Reyck and Herroelen (Algorithm 2.5.8): branching over the minimal delaying modes of a forbidden active set loses no feasible schedule. Since the objective function plays no role, the result holds for every objective.

Formalization Note. The standing assumptions of the model are hypotheses; resource constraints are required for all t≥0t\ge0t≥0. FFF is an arbitrary forbidden set, not necessarily minimal; BBB must be minimal and i∉Bi\notin Bi∈/B.

Preamble
import Mathlib
import Definitions.Def_ProjSchedTW_DelayingModes_Project
Formal statement
namespace ProjSchedTW.DelayingModes

theorem exists_minimal_delaying_mode {n : ℕ} {K : Type} [Fintype K] (P : Project n K)
    (hP : P.StandingAssumptions) (F : Finset (Fin (n + 2))) (hF : P.IsForbidden F)
    (S : Fin (n + 2) → ℝ) (hS : P.IsFeasible S) :
    ∃ (i : Fin (n + 2)) (B : Finset (Fin (n + 2))),
      P.IsMinimalDelayingMode F i B ∧ ∀ j ∈ B, S i + P.p i ≤ S j := by sorry

end ProjSchedTW.DelayingModes
Source
Neumann, Schwindt & Zimmermann, Project Scheduling with Time Windows and Scarce Resources, 2nd ed., Springer 2003, p. 49, Theorem 2.5.7, Eq. (2.5.4)
Human review
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 5, 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