Output test (3.124) — an activity that must be scheduled last in Ω ∪ {i}
ProvedComplexScheduling.output_testConsider an RCPSP instance with conjunction set , disjunction set and time windows , let be a disjunctive set for whose activities have positive processing times, let be nonempty and let . If
then in every feasible schedule — feasible for the RCPSP, satisfying and , within the windows — every activity of is processed before : for all . In the book's notation, : is an output of .
This is the output test, the instance , of Theorem 3.7, and the mirror image of the input test: if some ended last, all of would have to fit between the smallest head and , an interval too short for ; so ends last, and since it cannot overlap any , finishes before starts.
Formalization Note The condition is the family over , . Positive processing times on are what turn "ends last" into the conjunctions , exactly as in the input test.
import Definitions.Def_ComplexScheduling_RCPSP import Definitions.Def_ComplexScheduling_JobShop import Definitions.Def_ComplexScheduling_ConstraintPropagation
namespace ComplexScheduling
theorem output_test {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) (hp : ∀ i ∈ I, 0 < p i)
(Ω : Finset (Fin n)) (hΩ : Ω ⊆ I) (hne : Ω.Nonempty) (i : Fin n) (hi : i ∈ I) (hiΩ : i ∉ Ω)
(hcond : ∀ μ ∈ Ω, ∀ ν ∈ insert i Ω, dl μ < rel ν + totalProcessing p (insert i Ω))
(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) :
∀ j ∈ Ω, S j + p j ≤ S i := by sorry
end ComplexScheduling
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.