§4, Algorithm DP3 — optimal number of tardy jobs
ProvedBurnInBatch.TardyJobs.dp3_correctOn one batch machine with capacity , let all jobs have common processing time . Index the jobs so that their releases and due dates are nondecreasing. Let be Algorithm DP3's table: , for , and for the recurrence minimizes between skipping job and appending an eligible final on-time batch of through consecutive jobs. Then the minimum tardy-job count over all complete valid batch schedules is
The equality is DP3's correctness claim. Its right-hand side is computed from the paper's recurrence; independently minimizes over all complete schedules.
Formalization Note The paper's printed maximum starts at , leaving an empty set when no job can finish on time. The corrected range starts at zero. Both release and due-date sequences are required to be nondecreasing in index; due-date order alone makes the recurrence's unsuitable when ties are broken against releases. The running-time bound is not formalized.
import Mathlib import Definitions.Def_BurnInBatch_TardyJobs_Model import Definitions.Def_BurnInBatch_TardyJobs_DP3
namespace BurnInBatch.TardyJobs
/-- Correctness of Algorithm DP3, pp. 770–771, with zero included among
feasible on-time job counts when taking the maximum. -/
theorem dp3_correct {n : ℕ} (B p : ℕ) (r d : Fin n → ℕ)
(hB : 0 < B) (hd : Monotone d) (hr : Monotone r) :
n - dp3MaxOnTime B p r d = minTardy B (equalTime p) r d := by sorry
end BurnInBatch.TardyJobs
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.