§3, justification of DP1 — some minimum-makespan on-time schedule has consecutive batches
ProvedBurnInBatch.ReleaseTmax.consecutive_batchesConsider one batch machine of capacity and jobs with common processing time , release times and due dates , indexed so that
Fix and let be a batch schedule of jobs in which every job is on time. Then there is a batch schedule of jobs in which every job is on time, every batch consists of consecutively indexed jobs (at most of them), the batches appear in increasing index order, and
In particular, if an on-time schedule of jobs exists, some on-time schedule of minimum makespan is a consecutive partition of into blocks of at most jobs. This is the claim that turns the problem into the consecutive partition problem solved by Algorithm DP1.
Formalization Note The paper assumes that the jobs are indexed in increasing order of due dates. Here the index order is nondecreasing in both and : with ties in ordered against the claim fails (two jobs, , , , : the consecutive DP value is but no schedule finishes before ). Such an indexing exists whenever release times and due dates are agreeable (sort by ), and the two monotonicity conditions imply strict-form agreeability. The makespan clause is the content of the proof of Lemma 1 ("the completion times of the batches after the exchange … will not be greater"), which the justification of DP1 relies on.
import Mathlib import Definitions.Def_BurnInBatch_ReleaseTmax_Model
namespace BurnInBatch.ReleaseTmax
/-- Justification of DP1 (§3, p. 768): with the jobs indexed in nondecreasing order of due dates
and of release times, every on-time batch schedule `S` of the first `j` jobs can be replaced by
an on-time batch schedule `S'` of the same jobs whose batches are blocks of consecutively indexed
jobs (at most `B` each, as in every batch schedule), in increasing index order, with makespan no
larger than that of `S`. -/
theorem consecutive_batches {n : ℕ} (B p : ℕ) (r d : Fin n → ℕ) (hB : 0 < B)
(hd : Monotone d) (hr : Monotone r) (j : ℕ) (hj : j ≤ n)
(S : List (Finset (Fin n))) (hS : IsBatchSchedule B (prefixJobs n j) S)
(hon : AllOnTime p r d (prefixJobs n j) S) :
∃ S' : List (Finset (Fin n)),
IsBatchSchedule B (prefixJobs n j) S' ∧ AllOnTime p r d (prefixJobs n j) S' ∧
IsConsecutive S' ∧ makespan p r S' ≤ makespan p r S := by sorry
end BurnInBatch.ReleaseTmax
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.