Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§5, proof of Theorem 7 — a schedule with makespan ≤pq\le pq≤pq has no idle time, and each machine runs qqq element jobs or ppp dummy jobs

Proved
UnrelatedSched.TwoTimes.no_idle_two_kinds

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

makespannumber-theoryp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1reductionscheduling

Let ppp and qqq be relatively prime natural numbers with 0<p<q0<p<q0<p<q. Let UUU be a ground set of qnqnqn elements and S1,…,SmS_1,\dots,S_mS1​,…,Sm​ subsets of UUU, and consider the scheduling instance of Theorem 7: mmm machines, qnqnqn element jobs and p(m−n)p(m-n)p(m−n) dummy jobs, where an element job takes ppp time units on a machine whose tuple contains its element and qqq time units otherwise, and every dummy job takes qqq time units everywhere. Let σ\sigmaσ be a schedule with makespan Cmax⁡(σ)≤pqC_{\max}(\sigma)\le pqCmax​(σ)≤pq. Then:

  1. every machine has load exactly pqpqpq (there is no idle time);
  2. every element job uuu runs on a machine i=σ(u)i=\sigma(u)i=σ(u) with u∈Siu\in S_iu∈Si​, so it has length ppp;
  3. every machine iii either processes exactly qqq element jobs and no dummy job, or processes no element job and exactly ppp dummy jobs:
∣{u:σ(u)=i}∣=q  and no dummy job on i,orno element job on i  and  ∣{d:σ(d)=i}∣=p.\bigl|\{u:\sigma(u)=i\}\bigr|=q \ \text{ and no dummy job on } i, \qquad\text{or}\qquad \text{no element job on } i \ \text{ and } \ \bigl|\{d:\sigma(d)=i\}\bigr|=p .​{u:σ(u)=i}​=q  and no dummy job on i,orno element job on i  and  ​{d:σ(d)=i}​=p.

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 nnn machines that run element jobs give the matching.

Formalization Note The hypothesis ∣Si∣=q|S_i|=q∣Si​∣=q is not needed for these conclusions and is omitted. The case m<nm<nm<n is included: then there are no dummy jobs and (for n≥1n\ge1n≥1) no schedule with makespan at most pqpqpq exists, so the statement holds trivially there. Loads and makespan are those of MatousekLP.Scheduling.Schedule, with the processing times cast to reals.

Preamble
import Mathlib
import Definitions.Def_MatousekLP_Scheduling_Schedule
import Definitions.Def_UnrelatedSched_TwoTimes_Theorem7Instance

open MatousekLP.Scheduling
Formal statement
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
Source
Lenstra, Shmoys, Tardos, Approximation algorithms for scheduling unrelated parallel machines, CWI Report OS-R8714 (1987), p. 9, §5, proof of Theorem 7 ("no schedule with makespan pq can have idle time, and it now follows from an easy number theoretic argument that each machine processes either q element jobs of length p or p dummy jobs of length q")
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me