The first infeasibility test — a disjunctive subset whose windows are shorter than its processing time
ProvedComplexScheduling.disjunctive_set_infeasibility_testConsider an RCPSP instance with conjunction set , disjunction set and time windows , and let be a disjunctive set for . If some nonempty subset satisfies
then no feasible schedule exists: there is no schedule that is feasible for the RCPSP, respects the conjunctions and the disjunctions , and lies within the time windows.
This is the first infeasibility test of Section 3.6.4. The activities of cannot overlap, so they need units of time inside the interval , whose length is smaller.
Formalization Note The inequality between a maximum and a minimum is stated as the equivalent family of inequalities for all , which avoids natural-number subtraction and needs no separate treatment of a negative difference. must be nonempty, as the maximum and minimum presuppose; for the family is vacuous and the conclusion would be false. No positivity of the processing times is needed: a zero-length activity contributes nothing to and nothing to the packing.
import Definitions.Def_ComplexScheduling_RCPSP import Definitions.Def_ComplexScheduling_JobShop import Definitions.Def_ComplexScheduling_ConstraintPropagation
namespace ComplexScheduling
theorem disjunctive_set_infeasibility_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)
(J : Finset (Fin n)) (hJI : J ⊆ I) (hJ : J.Nonempty)
(hcond : ∀ μ ∈ J, ∀ ν ∈ J, dl μ < rel ν + totalProcessing p J) :
¬ ∃ S : Fin n → ℕ, FeasibleSchedule p Rcap demand prec S ∧ RespectsArcs p C S ∧
SatisfiesDisjunctions p D S ∧ WithinWindows rel dl p S := by sorry
end ComplexScheduling
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.