Lemma 7.1 — some optimal schedule has its early jobs first, in EDD order, and its late jobs last
ProvedTwoAgentSched.LateLate.lemma_7_1Consider the problem : jobs owned by agents and , with processing times and due dates , are sequenced on one machine from time without idle time; at most jobs of may be late, and the number of late jobs of is minimized. Suppose the instance is feasible, i.e. some sequence has at most late -jobs. Then there is an optimal sequence and an index such that
- the jobs in the first positions of are exactly its early jobs, and the jobs in positions are exactly its late jobs;
- the early jobs appear in earliest-due-date order:
The order of the late jobs is arbitrary. This structural lemma reduces the search for an optimal schedule to the choice of the set of early jobs, which is what the dynamic program of §7 enumerates.
Formalization Note The feasibility hypothesis is added: without a feasible sequence there is no optimal one, and the paper's "there is an optimal schedule" presupposes one. Positions are 0-based in Lean; job at position is early iff its completion time completionAt p l k is at most . EDD order allows ties.
import Mathlib import Definitions.Def_TwoAgentSched_LateLate_Model
namespace TwoAgentSched.LateLate
/-- Lemma 7.1 (p. 236). If `1‖ΣU^A_i : ΣU^B_i ≤ Q` has a feasible sequence, it has an optimal
sequence `l` whose first `m` jobs are exactly its early jobs (every job at a position `< m` meets
its due date, every job at a position `≥ m` is late) and whose early jobs are in EDD order
(nondecreasing due dates). -/
theorem lemma_7_1 {n : ℕ} (p d : Fin n → ℕ) (ag : Fin n → Agent) (Q : ℕ)
(hfeas : ∃ l : List (Fin n), IsFeasible p d ag Q l) :
∃ l : List (Fin n), IsOptimal p d ag Q l ∧
∃ m ≤ l.length,
(∀ (k : ℕ) (hk : k < l.length),
(k < m ↔ MooreLateJobs.Shared.completionAt (fun j => (p j : ℝ)) l k ≤ (d l[k] : ℝ))) ∧
(l.take m).Pairwise (fun a b => d a ≤ d b) := by sorry
end TwoAgentSched.LateLate
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.