Input test (3.123) — an activity that must be scheduled first in Ω ∪ {i}
ProvedComplexScheduling.input_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 — activity is processed before every activity of : for all . In the book's notation, : is an input of .
This is the input test, the instance , of Theorem 3.7. If some started first, all of would have to fit between and the largest deadline, an interval too short for ; so starts first, and since it cannot overlap any , it finishes before starts.
Formalization Note The condition is the family over , , with as . Positive processing times on are needed for the conclusion : with an activity could start at the same instant as without violating the disjunction. The book takes positive durations for granted in this section, and this is the hypothesis that turns "starts first" into a conjunction.
import Definitions.Def_ComplexScheduling_RCPSP import Definitions.Def_ComplexScheduling_JobShop import Definitions.Def_ComplexScheduling_ConstraintPropagation
namespace ComplexScheduling
theorem input_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 i + p i ≤ S j := by sorry
end ComplexScheduling
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.