Proof of Theorem 9.2 — a schedule with and is SPT
ProvedTwoAgentSched.TotalTotal.feasible_is_sptLet be nonnegative integers, and , and consider the instance of the proof of Theorem 9.2, in which agents and each have jobs of lengths . If a sequence of all jobs satisfies
then is SPT: the processing times of the jobs, read along , are nondecreasing.
Feasibility thus forces the shortest-processing-time order, which is where the two agents' totals become controlled by (5) and (6).
Formalization Note "SPT" here means nondecreasing lengths along the sequence. That is what the paper's exchange argument establishes. The stronger reading, that consists of the consecutive pairs , fails when lengths repeat: for the sequence with agents (lengths ) has but is not a sequence of consecutive pairs. For pairwise distinct lengths the two readings coincide.
import Mathlib import Definitions.Def_TwoAgentSched_TotalTotal_Construction
namespace TwoAgentSched.TotalTotal
/-- Proof of Theorem 9.2 (Agnetis et al. 2004, pp. 237–238): for integers `p_1 ≤ ⋯ ≤ p_k`, every
sequence `l` of all `2k` jobs of the constructed instance that is feasible for
`1‖∑ C^A_i ≤ T/2, ∑ C^B_i ≤ T/2` processes the jobs in nondecreasing order of length
(it is SPT). -/
theorem feasible_is_spt {k : ℕ} (p : Fin k → ℕ) (hp : Monotone p)
(l : List (Fin k ⊕ Fin k))
(hl : (construction p).Meets ((bigT p : ℝ) / 2) ((bigT p : ℝ) / 2) l) :
(l.map (construction p).p).Pairwise (· ≤ ·) := by sorry
end TwoAgentSched.TotalTotal
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.