Theorem 3.8 — the interval consistency theorem for a cumulative resource
ProvedComplexScheduling.cumulative_consistency_theoremConsider an RCPSP instance with time windows and a renewable resource of capacity ; let be the activities that need resource , their work and . Let and let be proper subsets of . If
then in every feasible schedule (feasible for the RCPSP and within the windows) an activity from starts first in or an activity from ends last in .
This is Theorem 3.8, the cumulative counterpart of Theorem 3.7: instead of "the activities of cannot overlap" the argument uses "the resource supplies at most units per time unit", so an interval of length offers units of work, and if the activities of were all processed between the earliest head of and the latest deadline of they would have less than available.
Formalization Note The condition is the family over , , equivalent to (3.145) and free of subtraction. Unlike Theorem 3.7 the book imposes no here, and the theorem has no hypothesis : with the conclusion is false and the theorem says that no feasible schedule exists, which is the cumulative infeasibility test. "Starts first" is read with , so a tie for the earliest start counts, which is what the book's proof uses when several activities of a cumulative resource start together. is the hypothesis that every activity of has positive demand for .
import Definitions.Def_ComplexScheduling_RCPSP import Definitions.Def_ComplexScheduling_ConstraintPropagation
namespace ComplexScheduling
theorem cumulative_consistency_theorem {n r : ℕ} (p : Fin n → ℕ) (Rcap : Fin r → ℕ)
(demand : Fin n → Fin r → ℕ) (prec : Finset (Fin n × Fin n)) (rel dl : Fin n → ℕ)
(k : Fin r) (J J' J'' : Finset (Fin n)) (hJk : ∀ i ∈ J, 0 < demand i k)
(hJ' : J' ⊂ J) (hJ'' : J'' ⊂ J)
(hcond : ∀ ν ∈ J \ J', ∀ μ ∈ J \ J'',
Rcap k * dl μ < Rcap k * rel ν + totalWork p demand k J)
(S : Fin n → ℕ) (hS : FeasibleSchedule p Rcap demand prec S) (hw : WithinWindows rel dl p S) :
(∃ i ∈ J', StartsFirstIn S J i) ∨ ∃ i ∈ J'', EndsLastIn p S J i := by sorry
end ComplexScheduling
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.