Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 7.1 — some optimal schedule has its early jobs first, in EDD order, and its late jobs last

Proved
TwoAgentSched.LateLate.lemma_7_1

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

late-jobsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1schedulingtwo-agent

Consider the problem 1∥∑UiA:∑UiB≤Q1\|\sum U^A_i : \sum U^B_i \le Q1∥∑UiA​:∑UiB​≤Q: jobs J1,…,JnJ_1,\dots,J_nJ1​,…,Jn​ owned by agents AAA and BBB, with processing times pjp_jpj​ and due dates djd_jdj​, are sequenced on one machine from time 000 without idle time; at most QQQ jobs of BBB may be late, and the number of late jobs of AAA is minimized. Suppose the instance is feasible, i.e. some sequence has at most QQQ late BBB-jobs. Then there is an optimal sequence σ∗\sigma^*σ∗ and an index mmm such that

  1. the jobs in the first mmm positions of σ∗\sigma^*σ∗ are exactly its early jobs, and the jobs in positions m+1,…,nm+1, \dots, nm+1,…,n are exactly its late jobs;
  2. the early jobs appear in earliest-due-date order:
dσ∗(1)≤dσ∗(2)≤⋯≤dσ∗(m).d_{\sigma^*(1)} \le d_{\sigma^*(2)} \le \dots \le d_{\sigma^*(m)}.dσ∗(1)​≤dσ∗(2)​≤⋯≤dσ∗(m)​.

The order of the late jobs is arbitrary. This structural lemma reduces the search for an optimal schedule to the choice of the set of early jobs, which is what the dynamic program of §7 enumerates.

Formalization Note The feasibility hypothesis is added: without a feasible sequence there is no optimal one, and the paper's "there is an optimal schedule" presupposes one. Positions are 0-based in Lean; job jjj at position kkk is early iff its completion time completionAt p l k is at most djd_jdj​. EDD order allows ties.

Preamble
import Mathlib
import Definitions.Def_TwoAgentSched_LateLate_Model
Formal statement
namespace TwoAgentSched.LateLate

/-- Lemma 7.1 (p. 236). If `1‖ΣU^A_i : ΣU^B_i ≤ Q` has a feasible sequence, it has an optimal
sequence `l` whose first `m` jobs are exactly its early jobs (every job at a position `< m` meets
its due date, every job at a position `≥ m` is late) and whose early jobs are in EDD order
(nondecreasing due dates). -/
theorem lemma_7_1 {n : ℕ} (p d : Fin n → ℕ) (ag : Fin n → Agent) (Q : ℕ)
    (hfeas : ∃ l : List (Fin n), IsFeasible p d ag Q l) :
    ∃ l : List (Fin n), IsOptimal p d ag Q l ∧
      ∃ m ≤ l.length,
        (∀ (k : ℕ) (hk : k < l.length),
          (k < m ↔ MooreLateJobs.Shared.completionAt (fun j => (p j : ℝ)) l k ≤ (d l[k] : ℝ))) ∧
        (l.take m).Pairwise (fun a b => d a ≤ d b) := by sorry

end TwoAgentSched.LateLate
Source
Agnetis, Mirchandani, Pacciarelli & Pacifici, Scheduling Problems with Two Competing Agents, Oper. Res. 52(2) (2004), p. 236, Lemma 7.1
Human review
  • Endorsed by Shuze Chen · Oct 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 8, 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