Input-or-output test — i starts first or j ends last, and i → j when i ≠ j
ProvedComplexScheduling.input_or_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 have at least two elements, and let . If
then in every feasible schedule — feasible for the RCPSP, satisfying and , within the windows — activity starts first in or activity ends last in ; and if then , that is, .
This is the input-or-output test, the instance , of Theorem 3.7 in its form (3.122) without the restriction . The conjunction follows in either case: if starts first it cannot overlap and so finishes before starts, and if ends last the same disjunction, read the other way, again forces before .
Formalization Note The condition is the family over , . The requirement is the book's (proper subsets); with the index sets would be empty and the first conclusion still holds trivially, but the book does not state the test there. Positivity of the processing times on is what the conjunction needs.
import Definitions.Def_ComplexScheduling_RCPSP import Definitions.Def_ComplexScheduling_JobShop import Definitions.Def_ComplexScheduling_ConstraintPropagation
namespace ComplexScheduling
theorem input_or_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)
(J : Finset (Fin n)) (hJI : J ⊆ I) (hJ : 2 ≤ J.card) (i j : Fin n) (hi : i ∈ J) (hj : j ∈ J)
(hcond : ∀ μ ∈ J.erase j, ∀ ν ∈ J.erase i, 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) :
(StartsFirstIn S J i ∨ EndsLastIn p S J j) ∧ (i ≠ 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.