Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1.3.3 — a time-feasible schedule exists iff the project network has no cycle of positive length

Proved
ProjSchedTW.Temporal.time_feasible_iff_no_positive_cycle

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

longest-pathp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1project-schedulingtime-windows

Let a project with AoN network NNN on V={0,1,…,n+1}V=\{0,1,\dots,n+1\}V={0,1,…,n+1} satisfy the standing assumption: for every node iii there are a path from 000 to iii of nonnegative length and a path from iii to n+1n+1n+1 of length at least pip_ipi​. Then

ST≠∅  ⟺  N contains no cycle of positive length,\mathcal S_T\ne\emptyset\iff N\text{ contains no cycle of positive length},ST​=∅⟺N contains no cycle of positive length,

where ST\mathcal S_TST​ is the set of schedules SSS (S0=0S_0=0S0​=0, Si≥0S_i\ge 0Si​≥0, real start times) satisfying the temporal constraints Sj−Si≥δijS_j-S_i\ge\delta_{ij}Sj​−Si​≥δij​ for all ⟨i,j⟩∈E\langle i,j\rangle\in E⟨i,j⟩∈E.

This is the basic feasibility criterion of temporal project scheduling with minimum and maximum time lags: the temporal constraints are consistent exactly when the time lags around every cycle do not add up to a positive amount.

Formalization Note. The standing assumption of p. 8 is a hypothesis; without it the statement is false (an arc ⟨i,0⟩\langle i,0\rangle⟨i,0⟩ with δi0>0\delta_{i0}>0δi0​>0 forces Si<0S_i<0Si​<0 with no cycle involved). Arc weights are arbitrary integers, so maximum time lags (negative weights) and cycles are allowed. Cycles are simple cycles; the statement is equivalent to the one for closed walks.

Preamble
import Mathlib
import Definitions.Def_ProjSchedTW_Temporal_Project
Formal statement
namespace ProjSchedTW.Temporal

/-- Theorem 1.3.3 (p. 10): there is a time-feasible schedule for a project if and only if the
corresponding AoN network `N` does not contain any cycle of positive length. The standing
property of AoN networks (p. 8) is a hypothesis. -/
theorem time_feasible_iff_no_positive_cycle {n : ℕ} (P : Project n)
    (hP : P.StandingAssumption) :
    (∃ S : Fin (n + 2) → ℝ, IsTimeFeasible P.N S) ↔ ¬ HasPositiveCycle P.N := by sorry

end ProjSchedTW.Temporal
Source
Neumann, Schwindt & Zimmermann, Project Scheduling with Time Windows and Scarce Resources, 2nd ed., Springer 2003, p. 10, Theorem 1.3.3 (with Definition 1.3.1, p. 10, and the path property of AoN networks, p. 8)
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