Proof of Theorem 9.2, Eqs. (5) and (6) — the two agents' total completion times in an SPT schedule
ProvedTwoAgentSched.TotalTotal.eq_5_6p2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1partitionreductionschedulingtwo-agent
Let be nonnegative integers, , and consider an SPT schedule of the instance of the proof of Theorem 9.2 (agents and each with jobs of lengths ; the pairs in order). Let if and if in , and . Then
and
So in an SPT schedule the split of between the two agents is governed by the single number , the total length of the pairs in which goes first.
Formalization Note The SPT schedule is given by (true meaning ); of the paper is xSum p x. Indices are 0-based, so the weight is .
Preamble
import Mathlib import Definitions.Def_TwoAgentSched_TotalTotal_Construction
Formal statement
namespace TwoAgentSched.TotalTotal
/-- Proof of Theorem 9.2, Eqs. (5) and (6) (Agnetis et al. 2004, p. 237): for integers
`p_1 ≤ ⋯ ≤ p_k` and the SPT schedule given by `x`, with `x = ∑_h x(0, p_h)` the total length of
the pairs in which B precedes A,
`∑ C^A_i = P + 2 ∑_{i=1}^k (k - i) p_i + x` (5) and
`∑ C^B_i = P + 2 ∑_{i=1}^k (k - i) p_i + (P - x)` (6). -/
theorem eq_5_6 {k : ℕ} (p : Fin k → ℕ) (hp : Monotone p) (x : Fin k → Bool) :
(construction p).sumCA (sptSeq x) =
(bigP p : ℝ) + 2 * (weightedSum p : ℝ) + (xSum p x : ℝ) ∧
(construction p).sumCB (sptSeq x) =
(bigP p : ℝ) + 2 * (weightedSum p : ℝ) + ((bigP p : ℝ) - (xSum p x : ℝ)) := 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, Eqs. (5) and (6)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.