p. 406 — the sum of completion times over is at least of its order, hence at least
ProvedIgnallSchrage.MeanCompletion.shat_le_sum_completionLet , let be a node and let be any full sequence that begins with . Let be the order in which processes the jobs of , and let be the completion times of on machine . Then
This is the second half of the bound , and it holds whether or not machine dominates.
Formalization Note The paper first describes as "the sum of the completion times for the jobs in " when . That description is not formalized as an equality: uses in place of , so even under the condition the actual sum may exceed . What the paper uses, and what is stated, is the lower bound ("the actual sum of completion times will be , no matter how the jobs in are sequenced"). The bars over in the subscripts of and are invisible in the scan.
import Mathlib import Definitions.Def_IgnallSchrage_MeanCompletion_LowerBound
namespace IgnallSchrage.MeanCompletion
/-- p. 406: for a node `J = J_r` with `1 ≤ r ≤ n - 1` and every full sequence `σ` that begins
with `J`, whatever the order `l` in which `σ` processes `J̄_r`, `S_r(l) ≤ Σ_{i ∈ J̄_r} d_i(σ)`,
and hence `Ŝ_r ≤ Σ_{i ∈ J̄_r} d_i(σ)`. -/
theorem shat_le_sum_completion {n : ℕ} (a b : Fin n → ℝ) (J : List (Fin n))
(hr : 1 ≤ J.length) (hrn : J.length < n) (σ : Equiv.Perm (Fin n)) (hσ : IgnallSchrage.Makespan.BeginsWith σ J) :
Sval a b J ((List.ofFn σ).drop J.length) ≤ ∑ i ∈ IgnallSchrage.Makespan.unscheduled J, completionTime a b σ i ∧
Shat a b J ≤ ∑ i ∈ IgnallSchrage.Makespan.unscheduled J, completionTime a b σ i := by sorry
end IgnallSchrage.MeanCompletion
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.