§5.2.1, p. 312 — with n ≥ 2 there are distinct J_r, J_l with a_r ≥ max_{A} bⱼ and b_l ≥ max_{B} aⱼ
ProvedSchedSurvey.O2.exists_r_lmakespanopen-shopp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1scheduling
Consider the two-machine open shop with jobs and nonnegative processing times on and on , and let , . If , there are two distinct jobs and such that
The analysis of in the survey begins by choosing such a pair; this statement asserts that the choice is always possible.
Formalization Note Each maximum is written as a bound on every member ( for all ), which is also correct when or is empty. The hypothesis is added: the page presupposes two distinct jobs.
Preamble
import Mathlib import Definitions.Def_SchedSurvey_O2_Model
Formal statement
namespace SchedSurvey.O2
/-- §5.2.1, p. 312: with at least two jobs, there are two distinct jobs `r` (`J_r`) and `l`
(`J_l`) with `a_r ≥ max_{Jⱼ ∈ A} bⱼ` and `b_l ≥ max_{Jⱼ ∈ B} aⱼ`; the maxima over `A`, `B`
are written as bounds for every member, which is also correct when `A` or `B` is empty. -/
theorem exists_r_l {n : ℕ} (a b : Fin n → ℝ) (ha : ∀ j, 0 ≤ a j) (hb : ∀ j, 0 ≤ b j)
(hn : 2 ≤ n) :
∃ r l : Fin n, r ≠ l ∧ (∀ j ∈ setA a b, b j ≤ a r) ∧ (∀ j ∈ setB a b, a j ≤ b l) := by sorry
end SchedSurvey.O2
Source
Graham, Lawler, Lenstra, Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey, Ann. Discrete Math. 5 (1979), p. 312, §5.2.1, "Now choose J_r and J_l to be any two distinct jobs …"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.