§5.2.1, p. 312 — every feasible O2 schedule has Cmax ≥ max{T₁, T₂, maxⱼ(aⱼ + bⱼ)}
ProvedSchedSurvey.O2.makespan_lower_boundmakespanopen-shopp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1scheduling
Consider the two-machine open shop with nonnegative processing times on and on , and let , . For every feasible schedule,
Equivalently: if a feasible schedule completes every operation by time , then , , and for every job .
The three terms are the loads of the two machines and the longest job: a machine processes one job at a time, and a job is on one machine at a time. This lower bound is what makes the survey's constructed schedules optimal.
Formalization Note is stated through thresholds: every with satisfies . The hypothesis matters only for , where and the bound reads .
Preamble
import Mathlib import Definitions.Def_SchedSurvey_O2_Model
Formal statement
namespace SchedSurvey.O2
/-- §5.2.1, p. 312: every feasible schedule has `Cmax ≥ max{T₁, T₂, maxⱼ(aⱼ + bⱼ)}`, stated as: if a
feasible schedule completes by `T ≥ 0`, then `T₁ ≤ T`, `T₂ ≤ T` and `aⱼ + bⱼ ≤ T` for every job. -/
theorem makespan_lower_bound {n : ℕ} (a b : Fin n → ℝ) (ha : ∀ j, 0 ≤ a j)
(hb : ∀ j, 0 ≤ b j) (S : Schedule n) (hS : IsFeasible a b S) (T : ℝ) (hT : 0 ≤ T)
(hST : CompletesBy a b S T) :
T₁ a ≤ T ∧ T₂ b ≤ T ∧ ∀ j, a j + b j ≤ T := 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, "For any feasible schedule we obviously have that Cmax ≥ max{T₁, T₂, maxⱼ{aⱼ + bⱼ}}"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.