Theorem 7.3 — is the optimal value of
ProvedTwoAgentSched.LateLate.theorem_7_3Two agents and share one machine; their jobs , with processing times and due dates , are numbered in EDD order, . In the problem , a sequence of all jobs is feasible if at most jobs of are late, and the objective is the number of late jobs of . Let be the dynamic-programming table of §7. If the instance is feasible, then for some , and
is the optimal value:
- some feasible sequence has exactly late -jobs, and
- every feasible sequence has at least late -jobs.
The theorem turns the table into an exact algorithm for the problem in which agent tolerates at most late jobs and agent minimizes its own number of late jobs.
Formalization Note Only the correctness half is stated; the running time is not formalized. Feasibility of the instance is a hypothesis (otherwise is the minimum of an empty set). is Nat.find of the existence clause. The EDD numbering is the hypothesis that is monotone, ties allowed. The table uses the corrected boundary for all .
import Mathlib import Definitions.Def_TwoAgentSched_LateLate_Model import Definitions.Def_TwoAgentSched_LateLate_DPTable
namespace TwoAgentSched.LateLate
/-- Theorem 7.3 (p. 236), correctness half. Jobs are numbered in EDD order (`Monotone d`) and
the instance of `1‖ΣU^A_i : ΣU^B_i ≤ Q` is feasible. Then some `h` has `C(n, h, Q) < +∞`, and
`h* = min{h : C(n, h, Q) < +∞}` is the optimal value: some feasible sequence has exactly `h*`
late `A`-jobs, and every feasible sequence has at least `h*` late `A`-jobs. -/
theorem theorem_7_3 {n : ℕ} (p d : Fin n → ℕ) (ag : Fin n → Agent) (Q : ℕ) (hd : Monotone d)
(hfeas : ∃ l : List (Fin n), IsFeasible p d ag Q l) :
∃ hex : ∃ h : ℕ, C p d ag n h Q < ⊤,
(∃ l : List (Fin n), IsFeasible p d ag Q l ∧ numLate p d ag .A l = Nat.find hex) ∧
∀ l : List (Fin n), IsFeasible p d ag Q l → Nat.find hex ≤ numLate p d ag .A l := by sorry
end TwoAgentSched.LateLate
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.