Proof of Theorem 9.2 — every SPT schedule has , and
ProvedTwoAgentSched.TotalTotal.spt_total_eq_Tp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1partitionreductionschedulingtwo-agent
Let be nonnegative integers, , and consider the two-agent instance of the proof of Theorem 9.2, in which agents and each have jobs of lengths . For every SPT schedule (the pairs in this order, each pair in either internal order),
and the threshold of the construction equals .
The overall total completion time therefore does not depend on which agent goes first in each pair; this is the reference value against which feasibility is measured in the rest of the proof.
Formalization Note The SPT schedule is given by the choice of the first agent in each pair. The sortedness hypothesis is the paper's numbering convention.
Preamble
import Mathlib import Definitions.Def_TwoAgentSched_TotalTotal_Construction
Formal statement
namespace TwoAgentSched.TotalTotal
/-- Proof of Theorem 9.2 (Agnetis et al. 2004, p. 237): for integers `p_1 ≤ ⋯ ≤ p_k`, every SPT
schedule of the constructed instance has the same overall total completion time
`∑ C^A_i + ∑ C^B_i = T = 3P + 4 ∑_{i=1}^k (k - i) p_i`, and the threshold `Q_A = Q_B` equals
`T / 2`. -/
theorem spt_total_eq_T {k : ℕ} (p : Fin k → ℕ) (hp : Monotone p) (x : Fin k → Bool) :
(construction p).sumCA (sptSeq x) + (construction p).sumCB (sptSeq x) = (bigT p : ℝ) ∧
thresholdQ p = (bigT p : ℝ) / 2 := by sorry
end TwoAgentSched.TotalTotal
Source
Agnetis, Mirchandani, Pacciarelli & Pacifici, Scheduling Problems with Two Competing Agents, Oper. Res. 52(2) (2004), p. 237, proof of Theorem 9.2 ("Also, note that … Q_A = Q_B = T/2")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.