Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§8 — with all B due dates equal to QQQ and Q′=0Q'=0Q′=0, ∑UiB≤Q′\sum U^B_i\le Q'∑UiB​≤Q′ is the same as Cmax⁡B≤QC^B_{\max}\le QCmaxB​≤Q

Proved
TwoAgentSched.Knapsack.section_8_reduction

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

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

Consider a two-agent single-machine instance (agent AAA with processing times phAp^A_hphA​ and weights whAw^A_hwhA​, agent BBB with processing times pkBp^B_kpkB​), a threshold QAQ_AQA​ for agent AAA's total weighted completion time, and a number QQQ. Give every BBB-job the due date dkB=Qd^B_k=QdkB​=Q and put Q′=0Q'=0Q′=0. Then for every sequence σ\sigmaσ of all jobs,

(∑hwhAChA(σ)≤QA  and  ∑kUkB(σ)≤0)  ⟺  (∑hwhAChA(σ)≤QA  and  Cmax⁡B(σ)≤Q).\Bigl(\sum_hw^A_hC^A_h(\sigma)\le Q_A\ \text{ and }\ \sum_kU^B_k(\sigma)\le 0\Bigr)\iff\Bigl(\sum_hw^A_hC^A_h(\sigma)\le Q_A\ \text{ and }\ C^B_{\max}(\sigma)\le Q\Bigr).(h∑​whA​ChA​(σ)≤QA​  and  k∑​UkB​(σ)≤0)⟺(h∑​whA​ChA​(σ)≤QA​  and  CmaxB​(σ)≤Q).

That is, a feasible solution of 1∥∑wiCiA:∑UiB≤Q′1\|\sum w_iC^A_i:\sum U^B_i\le Q'1∥∑wi​CiA​:∑UiB​≤Q′ for this instance is a feasible solution of 1∥∑wiCiA:Cmax⁡B≤Q1\|\sum w_iC^A_i:C^B_{\max}\le Q1∥∑wi​CiA​:CmaxB​≤Q, and vice versa. This is how §8 transfers the NP-hardness of Theorem 5.2 to 1∥∑wiCiA:∑UiB1\|\sum w_iC^A_i:\sum U^B_i1∥∑wi​CiA​:∑UiB​.

Formalization Note Cmax⁡B≤QC^B_{\max}\le QCmaxB​≤Q is written as CkB≤QC^B_k\le QCkB​≤Q for every BBB-job, and JkBJ^B_kJkB​ is late iff CkB>dkBC^B_k>d^B_kCkB​>dkB​. The statement is the encoding-free equivalence on the paper's construction; the corresponding polynomial-time reduction between languages is not stated.

Preamble
import Mathlib
import Definitions.Def_TwoAgentSched_Knapsack_Model
Formal statement
namespace TwoAgentSched.Knapsack

/-- §8 (Agnetis et al. 2004, p. 237): for the same jobs, giving every B-job the due date `Q` and
taking `Q' = 0`, a sequence is feasible for `1‖∑ w_iC^A_i ≤ Q_A, ∑ U^B_i ≤ 0` iff it is feasible
for `1‖∑ w_iC^A_i ≤ Q_A, C^B_max ≤ Q`. -/
theorem section_8_reduction (I : Instance) (QA Q : ℝ) (l : List (Fin I.nA ⊕ Fin I.nB)) :
    I.MeetsU QA (fun _ => Q) 0 l ↔ I.Meets QA Q l := by sorry

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