Lemma 7.2 — is the minimum completion time of the last early job
ProvedTwoAgentSched.LateLate.lemma_7_2Number the jobs of both agents in EDD order, , and let be the dynamic-programming table of §7. Fix and .
- If is finite, then it is the minimum completion time of the last early job over all partial schedules of the job set with at most late -jobs and at most late -jobs:
and the minimum is attained. 2. If , then no such partial schedule exists.
Here a partial schedule is given by its set of early jobs, processed first in EDD order with each job of completing by its due date, the other jobs of counting as late; is the completion time of its last early job. By Lemma 7.1 these are the schedules among which an optimal one is found. The lemma states that the recursion of §7 computes these minima, which is what makes the table usable for Theorem 7.3.
Formalization Note The paper's "feasible schedules for the job set " is read as partial schedules described by their early set, as in the definition of ("partial schedule … in which there are at most late -jobs"). The reading over complete sequences with actual lateness is false: one -job with , and has , while every sequence of it completes the job early at time . The boundary is the corrected one (see the table's definition).
import Mathlib import Definitions.Def_TwoAgentSched_LateLate_DPTable
namespace TwoAgentSched.LateLate
/-- Lemma 7.2 (p. 236). Jobs are numbered in EDD order (`Monotone d`). For `i ≤ n`: if
`C(i, h, k)` is a finite value `c`, then `c` is the minimum of `∑_{j ∈ E} p_j` (the completion
time of the last early job) over the partial schedules `E` of `{J_1, …, J_i}` with at most `h`
late `A`-jobs and at most `k` late `B`-jobs, and it is attained; if `C(i, h, k) = +∞`, there is
no such partial schedule. -/
theorem lemma_7_2 {n : ℕ} (p d : Fin n → ℕ) (ag : Fin n → Agent) (hd : Monotone d)
(i h k : ℕ) (hi : i ≤ n) :
(∀ c : ℕ, C p d ag i h k = (c : WithTop ℕ) →
(∃ E : Finset (Fin n), IsPartialSchedule p d ag i h k E ∧ ∑ j ∈ E, p j = c) ∧
∀ E : Finset (Fin n), IsPartialSchedule p d ag i h k E → c ≤ ∑ j ∈ E, p j) ∧
(C p d ag i h k = ⊤ → ∀ E : Finset (Fin n), ¬ IsPartialSchedule p d ag i h k E) := by sorry
end TwoAgentSched.LateLate
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.