Proof of Theorem 1, p. 1409 — a part reaching b_j after T^(j) leaves b_j within Γ^(j) + τ_j
ProvedReentrantScheduling.FBFS.buffer_delay_boundConsider a nonacyclic flow line operated under first buffer first serve (FBFS), with releases satisfying the burstiness constraint (1) with constants and load (3). Then there are finite times such that every part that arrives at buffer at a time is served there and completes its service at by
with the busy-period constant of the proof of Theorem 1. In words: the delay of a part at is at most if it arrived at after .
Summing these delays along the route gives the bound on the time a part needs to reach , which feeds the induction step.
Formalization Note Buffers are 0-based. The delay at is measured from arrival at to the end of service there. Arrival and start times live in WithTop ℝ; the conclusion forces the service start to be finite.
import Mathlib import Definitions.Def_ReentrantScheduling_FBFS_Model import Definitions.Def_ReentrantScheduling_FBFS_Constants
namespace ReentrantScheduling.FBFS
theorem buffer_delay_bound
(L : Line) (lam γ : ℝ) (hlam : 0 ≤ lam) (hγ : 0 ≤ γ) (hload : L.load lam < 1)
(R : Run L) (hR : R.Admissible L.fbfs) (harr : R.Arrivals lam γ) :
∃ T : Fin L.l → ℝ, ∀ (j : Fin L.l) (p : R.Part), R.entry p ≤ j →
((T j : ℝ) : WithTop ℝ) < R.arrive p j →
R.start p j + ((L.τ j : ℝ) : WithTop ℝ) ≤
R.arrive p j + ((L.Gamma lam γ j + L.τ j : ℝ) : WithTop ℝ) := by sorry
end ReentrantScheduling.FBFS
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.