§8 — with all B due dates equal to and , is the same as
ProvedTwoAgentSched.Knapsack.section_8_reductionlate-jobsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1reductionschedulingtwo-agent
Consider a two-agent single-machine instance (agent with processing times and weights , agent with processing times ), a threshold for agent 's total weighted completion time, and a number . Give every -job the due date and put . Then for every sequence of all jobs,
That is, a feasible solution of for this instance is a feasible solution of , and vice versa. This is how §8 transfers the NP-hardness of Theorem 5.2 to .
Formalization Note is written as for every -job, and is late iff . 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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.