§4 — variable-time extension of DP3 minimizes tardy jobs
ProvedBurnInBatch.TardyJobs.dp3_variable_correctbatch-processingdynamic-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1scheduling
All jobs are available at time zero on one batch machine of capacity . Their processing times and due dates are both nondecreasing in job index. Let be the variable-time DP3 table using for a final on-time batch of jobs when the result does not exceed . If is the minimum number of tardy jobs over complete valid batch schedules, then
This extends the algorithmic characterization to agreeable unequal processing times.
Formalization Note The paper prints a final range starting at one; zero is included to make the all-tardy case defined. Jobs are indexed so both and are nondecreasing. The stated running-time bound is not formalized.
Preamble
import Mathlib import Definitions.Def_BurnInBatch_TardyJobs_Model import Definitions.Def_BurnInBatch_TardyJobs_DP3Variable
Formal statement
namespace BurnInBatch.TardyJobs
/-- The §4 extension of DP3, p. 771, to agreeable processing times and due dates. -/
theorem dp3_variable_correct {n : ℕ} (B : ℕ) (p d : Fin n → ℕ)
(hB : 0 < B) (hd : Monotone d) (hp : Monotone p) :
n - dp3VariableMaxOnTime B p d = minTardy B p (fun _ => 0) d := by sorry
end BurnInBatch.TardyJobs
Source
Lee, Uzsoy & Martin-Vega, Efficient Algorithms for Scheduling Semiconductor Burn-In Operations, Oper. Res. 40(4) (1992), p. 771, §4, extension of DP3 to 1/B/Σ U_i
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.