Lemma 5.4 — if no B-job can end last, every optimal schedule ends with a longest A-job
ProvedTwoAgentSched.TotalMax.lemma_5_4interchange-argumentp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1schedulingtwo-agent
Consider the problem (positive processing times, nondecreasing , feasibility for all ), with at least one -job. Assume the instance is feasible, and let be the total processing time. If
then in every optimal schedule the last job is a longest -job: an -job with for all .
This lemma justifies the second branch of the algorithm of Figure 1. When several -jobs have the maximum length, the lemma does not say which of them is last.
Formalization Note The hypothesis excludes the instance with no jobs at all, whose empty schedule is feasible and has no last job; the paper's "a longest -job" presupposes -jobs.
Preamble
import Mathlib import Definitions.Def_TwoAgentSched_TotalMax_Model
Formal statement
namespace TwoAgentSched.TotalMax
/-- Lemma 5.4 (Agnetis et al. 2004, §5.2, p. 234). Consider a feasible instance of
`1‖ΣC^A_i : f^B_max ≤ Q` with at least one A-job, and let `τ = P_A + P_B`. If every B-job has
`f^B_k(τ) > Q`, then in every optimal schedule the last job is a longest A-job: an A-job `h`
with `p^A_{h'} ≤ p^A_h` for every A-job `h'`. -/
theorem lemma_5_4 {nA nB : ℕ} (hA : 0 < nA) (p : TwoAgentSched.MaxMax.Job nA nB → ℝ) (hp : ∀ j, 0 < p j)
(fB : Fin nB → ℝ → ℝ) (hfB : ∀ k, Monotone (fB k)) (Q : ℝ)
(hfeas : IsFeasibleInstance p fB Q)
(hall : ∀ k : Fin nB,
Q < fB k (∑ h : Fin nA, p (Sum.inl h) + ∑ k : Fin nB, p (Sum.inr k))) :
∀ l : List (TwoAgentSched.MaxMax.Job nA nB), IsOptimal p fB Q l →
∃ h : Fin nA, l.getLast? = some (Sum.inl h) ∧
∀ h' : Fin nA, p (Sum.inl h') ≤ p (Sum.inl h) := by sorry
end TwoAgentSched.TotalMax
Source
Agnetis, Mirchandani, Pacciarelli & Pacifici, Scheduling Problems with Two Competing Agents, Oper. Res. 52(2) (2004), p. 234, Lemma 5.4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.