Theorem 3.7 — the interval consistency theorem for disjunctive sets
ProvedComplexScheduling.interval_consistency_theoremConsider an RCPSP instance with conjunction set , disjunction set and time windows , and let be a disjunctive set for : at least two activities, any two of which are related by a disjunction or a conjunction, so that no two of them can be processed at the same time. Let , let and be proper subsets of with , and write . If
then in every feasible schedule — feasible for the RCPSP, satisfying the conjunctions and the disjunctions , and within the time windows — an activity from starts first in or an activity from ends last in .
This is Theorem 3.7, the general result from which the interval consistency tests of Section 3.6.4 (input, output, input-or-output, and the two negation tests) are read off by choosing and . If neither conclusion held, the activity of starting first would be some and the one ending last some , so all of would be processed inside , an interval too short for non-overlapping activities.
Formalization Note The maximum in (3.121) is stated as the equivalent family over the same index pairs, which has no junk value when the index set is empty (the family is then vacuous, as a maximum over an empty set, , would make it) and no natural-number subtraction. "Starts first" and "ends last" are read with ; on a disjunctive set with positive durations this is the strict reading, and the statement remains true without positivity, so none is assumed: the book invokes positivity only to justify restricting to , and in the case where that restriction empties the index set the conclusion holds outright. The RCPSP feasibility of the schedule is the book's "feasible" and is carried as a hypothesis, although the argument uses only the windows and the disjunctions.
import Definitions.Def_ComplexScheduling_RCPSP import Definitions.Def_ComplexScheduling_JobShop import Definitions.Def_ComplexScheduling_ConstraintPropagation
namespace ComplexScheduling
theorem interval_consistency_theorem {n r : ℕ} (p : Fin n → ℕ) (Rcap : Fin r → ℕ)
(demand : Fin n → Fin r → ℕ) (prec C D : Finset (Fin n × Fin n)) (rel dl : Fin n → ℕ)
(I : Finset (Fin n)) (hI : IsDisjunctiveSet C D I)
(J J' J'' : Finset (Fin n)) (hJI : J ⊆ I) (hJ' : J' ⊂ J) (hJ'' : J'' ⊂ J)
(hne : (J' ∪ J'').Nonempty)
(hcond : ∀ ν ∈ J \ J', ∀ μ ∈ J \ J'', ν ≠ μ → dl μ < rel ν + totalProcessing p J)
(S : Fin n → ℕ) (hS : FeasibleSchedule p Rcap demand prec S) (hC : RespectsArcs p C S)
(hD : SatisfiesDisjunctions p D 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.