Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 7.3 — h∗=min⁡{h:C(nA+nB,h,Q)<+∞}h^* = \min\{h : C(n_A+n_B, h, Q) < +\infty\}h∗=min{h:C(nA​+nB​,h,Q)<+∞} is the optimal value of 1∥∑UiA:∑UiB≤Q1\|\sum U^A_i : \sum U^B_i \le Q1∥∑UiA​:∑UiB​≤Q

Proved
TwoAgentSched.LateLate.theorem_7_3

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

dynamic-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1schedulingtwo-agent

Two agents AAA and BBB share one machine; their n=nA+nBn = n_A + n_Bn=nA​+nB​ jobs J1,…,JnJ_1,\dots,J_nJ1​,…,Jn​, with processing times pjp_jpj​ and due dates djd_jdj​, are numbered in EDD order, d1≤⋯≤dnd_1 \le \dots \le d_nd1​≤⋯≤dn​. In the problem 1∥∑UiA:∑UiB≤Q1\|\sum U^A_i : \sum U^B_i \le Q1∥∑UiA​:∑UiB​≤Q, a sequence of all jobs is feasible if at most QQQ jobs of BBB are late, and the objective is the number ∑UiA\sum U^A_i∑UiA​ of late jobs of AAA. Let C(i,h,k)C(i,h,k)C(i,h,k) be the dynamic-programming table of §7. If the instance is feasible, then C(n,h,Q)<+∞C(n, h, Q) < +\inftyC(n,h,Q)<+∞ for some hhh, and

h∗=min⁡{ h:C(nA+nB,h,Q)<+∞ }h^* = \min\{\, h : C(n_A + n_B, h, Q) < +\infty \,\}h∗=min{h:C(nA​+nB​,h,Q)<+∞}

is the optimal value:

  1. some feasible sequence has exactly h∗h^*h∗ late AAA-jobs, and
  2. every feasible sequence has at least h∗h^*h∗ late AAA-jobs.

The theorem turns the table into an exact algorithm for the problem in which agent BBB tolerates at most QQQ late jobs and agent AAA minimizes its own number of late jobs.

Formalization Note Only the correctness half is stated; the running time O(nA2nB+nAnB2)O(n_A^2 n_B + n_A n_B^2)O(nA2​nB​+nA​nB2​) is not formalized. Feasibility of the instance is a hypothesis (otherwise h∗h^*h∗ is the minimum of an empty set). h∗h^*h∗ is Nat.find of the existence clause. The EDD numbering is the hypothesis that ddd is monotone, ties allowed. The table uses the corrected boundary C(0,h,k)=0C(0,h,k) = 0C(0,h,k)=0 for all h,k≥0h,k \ge 0h,k≥0.

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

/-- Theorem 7.3 (p. 236), correctness half. Jobs are numbered in EDD order (`Monotone d`) and
the instance of `1‖ΣU^A_i : ΣU^B_i ≤ Q` is feasible. Then some `h` has `C(n, h, Q) < +∞`, and
`h* = min{h : C(n, h, Q) < +∞}` is the optimal value: some feasible sequence has exactly `h*`
late `A`-jobs, and every feasible sequence has at least `h*` late `A`-jobs. -/
theorem theorem_7_3 {n : ℕ} (p d : Fin n → ℕ) (ag : Fin n → Agent) (Q : ℕ) (hd : Monotone d)
    (hfeas : ∃ l : List (Fin n), IsFeasible p d ag Q l) :
    ∃ hex : ∃ h : ℕ, C p d ag n h Q < ⊤,
      (∃ l : List (Fin n), IsFeasible p d ag Q l ∧ numLate p d ag .A l = Nat.find hex) ∧
      ∀ l : List (Fin n), IsFeasible p d ag Q l → Nat.find hex ≤ numLate p d ag .A l := by sorry

end TwoAgentSched.LateLate
Source
Agnetis, Mirchandani, Pacciarelli & Pacifici, Scheduling Problems with Two Competing Agents, Oper. Res. 52(2) (2004), p. 236, Theorem 7.3
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