Theorem 1.3.3 — a time-feasible schedule exists iff the project network has no cycle of positive length
ProvedProjSchedTW.Temporal.time_feasible_iff_no_positive_cycleLet a project with AoN network on satisfy the standing assumption: for every node there are a path from to of nonnegative length and a path from to of length at least . Then
where is the set of schedules (, , real start times) satisfying the temporal constraints for all .
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 with forces 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.
import Mathlib import Definitions.Def_ProjSchedTW_Temporal_Project
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.