§5, proof of Theorem 7 — a schedule with makespan has no idle time, and each machine runs element jobs or dummy jobs
ProvedUnrelatedSched.TwoTimes.no_idle_two_kindsLet and be relatively prime natural numbers with . Let be a ground set of elements and subsets of , and consider the scheduling instance of Theorem 7: machines, element jobs and dummy jobs, where an element job takes time units on a machine whose tuple contains its element and time units otherwise, and every dummy job takes time units everywhere. Let be a schedule with makespan . Then:
- every machine has load exactly (there is no idle time);
- every element job runs on a machine with , so it has length ;
- every machine either processes exactly element jobs and no dummy job, or processes no element job and exactly dummy jobs:
This is the step of the hard direction of Theorem 7 that the paper attributes to the absence of idle time and "an easy number theoretic argument"; from it the machines that run element jobs give the matching.
Formalization Note The hypothesis is not needed for these conclusions and is omitted. The case is included: then there are no dummy jobs and (for ) no schedule with makespan at most exists, so the statement holds trivially there. Loads and makespan are those of MatousekLP.Scheduling.Schedule, with the processing times cast to reals.
import Mathlib import Definitions.Def_MatousekLP_Scheduling_Schedule import Definitions.Def_UnrelatedSched_TwoTimes_Theorem7Instance open MatousekLP.Scheduling
namespace UnrelatedSched.TwoTimes
/-- §5, proof of Theorem 7, p. 9 (Lenstra, Shmoys, Tardos, CWI Report OS-R8714 (1987)): "no
schedule with makespan pq can have idle time, and … each machine processes either q element jobs
of length p or p dummy jobs of length q". For `0 < p < q` relatively prime and any schedule `σ`
of the instance `twoTimes p q n S` with makespan at most `p * q`:
1. every machine has load exactly `p * q`;
2. every element job runs on a machine whose tuple contains its element (so it has length `p`);
3. every machine processes either exactly `q` element jobs and no dummy job, or no element job
and exactly `p` dummy jobs. -/
theorem no_idle_two_kinds {p q m n : ℕ} (hp : 0 < p) (hpq : p < q) (hcop : Nat.Coprime p q)
(S : Fin m → Finset (Fin (q * n))) (σ : Fin (q * n + p * (m - n)) → Fin m)
(hσ : makespan (fun i j => (twoTimes p q n S i j : ℝ)) σ ≤ (p * q : ℝ)) :
(∀ i : Fin m, load (fun i j => (twoTimes p q n S i j : ℝ)) σ i = (p * q : ℝ)) ∧
(∀ u : Fin (q * n), u ∈ S (σ (elemJob p q n m u))) ∧
(∀ i : Fin m,
((Finset.univ.filter (fun u => σ (elemJob p q n m u) = i)).card = q ∧
∀ k : Fin (p * (m - n)), σ (dummyJob p q n m k) ≠ i) ∨
((∀ u : Fin (q * n), σ (elemJob p q n m u) ≠ i) ∧
(Finset.univ.filter (fun k => σ (dummyJob p q n m k) = i)).card = p)) := by sorry
end UnrelatedSched.TwoTimes
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.