§3 — Algorithm DP1 computes the minimum makespan of an on-time batch schedule, and when none exists
ProvedBurnInBatch.ReleaseTmax.dp1_correctConsider one batch machine of capacity and jobs with common processing time , release times and due dates , indexed so that
Let be the value of Algorithm DP1. Then for every ,
with the minimum of the empty set equal to . That is, is finite exactly when jobs can be scheduled with no tardy job, and then it is the minimum makespan of such a schedule; the minimum ranges over all batch schedules (any batching, any order). For this is the paper's claim that DP1 "will find a feasible schedule with minimum makespan if a feasible schedule exists".
The result solves the feasibility version of , and with due dates shifted by a trial value of it is the subroutine of the bisection procedure for minimizing .
Formalization Note The paper's "jobs are indexed in increasing order of due dates" is formalized as an index order nondecreasing in both and ; DP1 uses as the release time of the batch , and with ties in ordered against the claim is false (two jobs, , , , : , optimum ). This index order exists whenever release times and due dates are agreeable, and implies agreeability. The minimum is an infimum in , where the infimum of the empty set is . The paper's remark "if … none are tardy" is not part of the statement. The running time is not formalized.
import Mathlib import Definitions.Def_BurnInBatch_ReleaseTmax_Model import Definitions.Def_BurnInBatch_ReleaseTmax_DP1
namespace BurnInBatch.ReleaseTmax
/-- Correctness of Algorithm DP1 (§3, p. 768). One batch machine of capacity `B ≥ 1`, `n` jobs
with common processing time `p`, release times `r` and due dates `d`, indexed so that both `d`
and `r` are nondecreasing. For every prefix length `j ≤ n`, the DP1 value `f(j)` equals the
minimum makespan over all batch schedules of jobs `1, …, j` in which every job is on time, and
it is `⊤ = ∞` exactly when there is no such schedule (an infimum over the empty set in `ℕ∞`). -/
theorem dp1_correct {n : ℕ} (B p : ℕ) (r d : Fin n → ℕ) (hB : 0 < B)
(hd : Monotone d) (hr : Monotone r) (j : ℕ) (hj : j ≤ n) :
dp1 B p r d j =
⨅ (S : List (Finset (Fin n)))
(_ : IsBatchSchedule B (prefixJobs n j) S ∧ AllOnTime p r d (prefixJobs n j) S),
(makespan p r S : ℕ∞) := by sorry
end BurnInBatch.ReleaseTmax
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.