Lemma 5.3 — an eligible B-job can be placed last, and no optimal schedule ends with an A-job
ProvedTwoAgentSched.TotalMax.lemma_5_3interchange-argumentp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1schedulingtwo-agent
Consider the problem on one machine: agent owns jobs , agent owns , all processing times are positive, each is nondecreasing, and a schedule is feasible if for all . Assume the instance is feasible, and let
be the total processing time. If some -job satisfies , then
- there is an optimal schedule in which is scheduled last, and
- there is no optimal schedule in which an -job is scheduled last.
This lemma justifies the first branch of the algorithm of Figure 1: a -job that can afford to finish at the very end may be put there.
Formalization Note "Scheduled last" is the last entry of the sequence (List.getLast?). Positive processing times are assumed; without them part 2 fails, since a -job of length zero can sit anywhere.
Preamble
import Mathlib import Definitions.Def_TwoAgentSched_TotalMax_Model
Formal statement
namespace TwoAgentSched.TotalMax
/-- Lemma 5.3 (Agnetis et al. 2004, §5.2, p. 234). Consider a feasible instance of
`1‖ΣC^A_i : f^B_max ≤ Q` and let `τ = P_A + P_B`. If some B-job `J^B_{k̄}` has
`f^B_{k̄}(τ) ≤ Q`, then (1) some optimal schedule has `J^B_{k̄}` last, and (2) no optimal
schedule has an A-job last. Processing times are positive (needed for (2)). -/
theorem lemma_5_3 {nA nB : ℕ} (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) (kbar : Fin nB)
(hkbar : fB kbar (∑ h : Fin nA, p (Sum.inl h) + ∑ k : Fin nB, p (Sum.inr k)) ≤ Q) :
(∃ l : List (TwoAgentSched.MaxMax.Job nA nB), IsOptimal p fB Q l ∧ l.getLast? = some (Sum.inr kbar)) ∧
∀ l : List (TwoAgentSched.MaxMax.Job nA nB), IsOptimal p fB Q l →
∀ h : Fin nA, l.getLast? ≠ some (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.3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.