§5.2.2, p. 313 — C*max ≥ C: every machine load and job length is at most the makespan
ProvedSchedSurvey.OPmtn.lower_boundlower-boundmakespanopen-shopp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1preemptionscheduling
Let be an matrix of processing times , rows indexed by the machines and columns by the jobs of an open shop with preemption allowed. Let be a feasible preemptive schedule for in which every piece ends by time . Then
Equivalently, . This is the lower half of the optimality theorem for : no machine can finish its load, and no job its total processing, faster than in the given amount of time.
Formalization Note Machines and jobs are indexed by Fin m and Fin n, which are 0-based: is index and is index . The hypothesis is needed only for , where the empty schedule completes by every , including negative ones.
Preamble
import Mathlib import Definitions.Def_SchedSurvey_OPmtn_Model
Formal statement
namespace SchedSurvey.OPmtn
/-- §5.2.2, p. 313: "We clearly have C*max ≥ C." Every feasible preemptive open-shop schedule
that completes by `T ≥ 0` has every machine load and every job length at most `T`. -/
theorem lower_bound {m n : ℕ} (P : Fin m → Fin n → ℝ) (hP : ∀ i j, 0 ≤ P i j)
(S : List (Piece m n)) (hS : IsFeasible P S) (T : ℝ) (hT : 0 ≤ T)
(hST : CompletesBy S T) :
(∀ i, rowSum P i ≤ T) ∧ ∀ j, colSum P j ≤ T := by sorry
end SchedSurvey.OPmtn
Source
Graham, Lawler, Lenstra, Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey, Ann. Discrete Math. 5 (1979), p. 313, §5.2.2, "We clearly have C*max ≥ C."
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.