Theorem 2.5.7 — every feasible schedule obeys a minimal delaying mode of each forbidden set
ProvedProjSchedTW.DelayingModes.exists_minimal_delaying_modeLet be a forbidden set of a project, i.e. for some resource . For every feasible schedule (time-feasible and resource-feasible) there is a minimal delaying mode for — is a minimal delaying alternative for and — such that
Thus every feasible schedule resolves the conflict of by letting one fixed activity of 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 . is an arbitrary forbidden set, not necessarily minimal; must be minimal and .
import Mathlib import Definitions.Def_ProjSchedTW_DelayingModes_Project
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.