Proof of Theorem 1, p. 1410 — parts released after T^(l) have delay at most Σ_{j=1}^l (Γ^(j) + τ_j)
ProvedReentrantScheduling.FBFS.eventual_delay_bounddelayfbfsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1queueing-networkreentrant-line
Consider 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 is a finite time such that every part released after exits the system with
where are the busy-period constants of the proof of Theorem 1.
The bound depends only on the line and on , not on the initial state; the initial state only affects the length of the transient (p. 1410).
Formalization Note Buffers are 0-based, and the sum runs over Fin l. The statement concerns released parts (initial parts are excluded). The exit time lives in WithTop ℝ, so the conclusion includes that the part exits.
Preamble
import Mathlib import Definitions.Def_ReentrantScheduling_FBFS_Model import Definitions.Def_ReentrantScheduling_FBFS_Constants
Formal statement
namespace ReentrantScheduling.FBFS
theorem eventual_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 : ℝ, ∀ p : R.Part, ¬ R.initial p → T < R.α p →
R.exit p ≤ ((R.α p + ∑ j : Fin L.l, (L.Gamma lam γ j + L.τ j) : ℝ) : WithTop ℝ) := by sorry
end ReentrantScheduling.FBFS
Source
Lu & Kumar, Distributed Scheduling Based on Due Dates and Buffer Priorities, IEEE TAC 36(12), 1991, p. 1410, proof of Theorem 1, final paragraph
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.