Lemma 11 — a schedule within the bound gives a k-Sum solution (corrected: )
ProvedSerialBatchTardy.lemma_11batch-schedulingp2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1parameterized-complexityscheduling
Let be distinct positive integers, each smaller than , with for all , and let the leftover processing times sum to . If the constructed instance has a feasible schedule with , then there are , not necessarily distinct, with
This is the converse direction of the reduction.
Differences from the source:
- correction: standing assumption "k − 1 times the largest integer in {x_1, …, x_n} is less than t" (p.550) → every x_i < t; reason: at k = 1 the printed assumption only says 0 < t and Lemma 11 is false: k = 1, t = 2, xs = (5, 6); the schedule with all of J_5 in one batch [0, 7) has tardy weight 7S ≤ 10S, the bound, yet no x_i equals 2; for k ≥ 2 the printed assumption implies x_i < t, so every k ≥ 2 instance of the source is covered (the proof itself uses "all x_i are smaller than t", p.551)
- generalization: (k − 1)t leftover jobs of processing time 1 → any leftover list L with sum (k − 1)t; reason: the unit list is one such list
- encoding: weights n^h + n^h/x_i and k(X + n), bound kX − t + (n − 1)k → all multiplied by S = ∏ x_i (weights n^h·(S + S/x_i) and S·k(X + n); bound S·(k(X + n) − (t + k)) in ℤ); reason: p.551 makes the weights integral exactly this way ("multiplying them with ∏ x_i"); the comparison is in ℤ so that no truncated subtraction occurs
- reading: "S_{B′} ∉ [S_B, C_B) for any batch B′ ≠ B" (p.546), "no two batches are processed at the same time" (p.548) → for distinct used batches, C_B ≤ S_{B′} or C_{B′} ≤ S_B; reason: the two agree for batches of positive length; they differ only when a batch of length 0 (Δ = 0, all its p_j = 0) starts together with another batch, where the literal p.546 condition breaks the time reversal of Lemma 12 (Δ = 0, jobs (p, r, d) = (0, 0, 0) and (1, 0, 1): cost > 0, reversed cost 0)
- encoding: start times S_B (domain not stated) → start times in ℤ; reason: all data are integers; rounding every start time down keeps a schedule feasible and keeps every early job early
- generalization: x_i ∈ {1, …, n^{ck}} written in base n (p.550) → no range bound on the x_i and no condition on n; reason: the argument uses only the totals of each J_{x,ℓ}, which hold for the base-n digits of any x in any base (Nat.ofDigits_digits), so the instances of the source are included
Preamble
import Definitions.Def_SerialBatchTardy_Construction import Definitions.Def_SerialBatchTardy_KSum set_option autoImplicit false
Formal statement
namespace SerialBatchTardy
/-- **Lemma 11** (Hermelin, Mnich & Omlor, J. Scheduling 27 (2024), p.553, PDF p.9; corrected
assumption). Let `xs` be a duplicate-free list of positive integers, each smaller than `t`, with
`(k − 1)·x_i < t`, and let the leftover list `L` have sum `(k − 1)t`. If the constructed instance
has a feasible schedule whose weighted number of tardy jobs is at most the bound, then some `k`
entries of `xs` (repetitions allowed) sum to `t`.
**Formalization Note.** For `L = List.replicate ((k-1)*t) 1` this is the printed lemma. Weights and
bound are scaled by `S = ∏ x_i`. -/
theorem lemma_11 (xs : List ℕ) (t k : ℕ) (L : List ℕ) (hnd : xs.Nodup) (hpos : ∀ a ∈ xs, 1 ≤ a)
(hstand : ∀ a ∈ xs, ((k : ℤ) - 1) * a < t) (hlt : ∀ a ∈ xs, a < t) (hL : L.sum = (k - 1) * t)
(σ : Schedule (hardInstance xs t k L)) (hσ : σ.Feasible)
(hW : (σ.tardyWeight : ℤ) ≤ hardBound xs t k) :
KSumSolvable xs t k := by sorry
end SerialBatchTardy
Source
Hermelin, Mnich & Omlor, Serial batching to minimize the weighted number of tardy jobs, J. Scheduling 27 (2024), Lemma 11, p.553 (PDF p.9)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.