Correctness of Algorithm DP2 — is the minimum makespan of an on-time batch schedule of jobs , and if none exists
ProvedBurnInBatch.AgreeTmax.dp2_correctConsider jobs on a single batch processing machine of capacity , all available at time , with processing times and due dates in , indexed so that
A batch takes the processing time of its longest job and batches run back to back from time . Let be the value function of Algorithm DP2: and, for ,
Then for every ,
the minimum over all batch schedules (any batching, any order), with the convention that the minimum of the empty set is . In particular exactly when the jobs can be completed by their due dates, and answers the feasibility question of with agreeable processing times and due dates.
Combined with a bisection over due-date shifts, this decides the minimum ; the running-time bounds and are not part of this statement.
Formalization Note The minimum is the infimum in , where is the infimum of the empty set. The paper's standing assumption "jobs are indexed in increasing order of due dates" is strengthened to nondecreasing due dates and nondecreasing processing times: DP2 charges for the batch and checks only , which is right only under both orders. Without the second one the statement is false: for , , the recursion gives while every schedule takes at least . Agreeable data (strict form ) always admit such an indexing. Jobs are 0-based in Lean; the paper's jobs are jobsUpTo n j.
import Mathlib import Definitions.Def_BurnInBatch_AgreeTmax_Model import Definitions.Def_BurnInBatch_AgreeTmax_DP2
namespace BurnInBatch.AgreeTmax
/-- Correctness of Algorithm DP2 (Lee, Uzsoy & Martin-Vega 1992, §3, p. 770): with jobs indexed
so that due dates and processing times are both nondecreasing, for every prefix length `j ≤ n`,
`dp2 B p d j` is the minimum makespan over all valid batch schedules of the jobs `1, …, j` with
`T_max = 0`, and `⊤` (the infimum of the empty set in `ℕ∞`) if there is none. -/
theorem dp2_correct {n B : ℕ} (hB : 0 < B) (p d : Fin n → ℕ)
(hd : Monotone d) (hp : Monotone p) (j : ℕ) (hj : j ≤ n) :
dp2 B p d j =
⨅ (S : List (Finset (Fin n))) (_ : IsValid B (jobsUpTo n j) S ∧ Tmax p d S = 0),
(makespan p S : ℕ∞) := by sorry
end BurnInBatch.AgreeTmax
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.