The leftover list: sum , entries, every split
ProvedSerialBatchTardy.leftoverList_specbatch-schedulingp2o-gran-per-chapterp2o-plan-paperp2o-v1parameterized-complexityscheduling
Let and let be the leftover list. Then
- every entry of is for some ;
- the entries of sum to ;
- has at most entries;
- for all with , the entries of can be distributed into parts with sums .
With this list in place of unit jobs, the constructed instance has polynomially many jobs and still distinct processing times.
Differences from the source:
- reading: (k − 1)t identical leftover jobs of processing time 1 → the list L(n, k, t) of powers of n with the same total (k − 1)t, O(kn log t) entries, splitting into any k parts of the needed sums; reason: t can be as large as k·n^{3ck}, so (k − 1)t unit jobs cannot be written down in f(k)·n^{O(1)} time on the job-list input of §2; the proof step is repaired, the theorem it serves is unchanged
Preamble
import Definitions.Def_SerialBatchTardy_Construction set_option autoImplicit false
Formal statement
namespace SerialBatchTardy
/-- **The leftover list.** For `n, k, t ≥ 2`, the list `leftoverList n k t` consists of powers
`n^h` with `h ≤ ⌊log_n t⌋`, has sum `(k − 1)t` and at most `2(k + 1)n(⌊log_n t⌋ + 1)` entries,
and for every `s_0, …, s_{k−1}` with `∑ s_ℓ = (k − 1)t` its entries can be distributed into `k`
parts with sums `s_0, …, s_{k−1}`.
It replaces the `(k − 1)t` unit leftover jobs of Hermelin, Mnich & Omlor, J. Scheduling 27 (2024),
§4, p.551 (PDF p.7): "We create (k − 1)t identical jobs, called leftover jobs, each with the
following parameters: Processing time 1 …". -/
theorem leftoverList_spec (n k t : ℕ) (hn : 2 ≤ n) (hk : 2 ≤ k) (ht : 2 ≤ t) :
(∀ e ∈ leftoverList n k t, ∃ h ≤ Nat.log n t, e = n ^ h) ∧
(leftoverList n k t).sum = (k - 1) * t ∧
(leftoverList n k t).length ≤ 2 * (k + 1) * n * (Nat.log n t + 1) ∧
∀ s : Fin k → ℕ, ∑ ℓ, s ℓ = (k - 1) * t →
∃ a : Fin (leftoverList n k t).length → Fin k,
∀ ℓ, ∑ i ∈ Finset.univ.filter (fun i => a i = ℓ), (leftoverList n k t).get i = s ℓ := by sorry
end SerialBatchTardy
Source
Hermelin, Mnich & Omlor, Serial batching to minimize the weighted number of tardy jobs, J. Scheduling 27 (2024), §4, p.551 (PDF p.7), the leftover jobs ("We create (k − 1)t identical jobs, called leftover jobs"); repaired, see the mission's moderation notes
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.