Proof of Theorem 1, p. 1409 — a 1-busy period commencing at T₁ > 0 lasts at most Γ^(1)
ProvedReentrantScheduling.FBFS.gamma1_busy_period_boundbusy-periodfbfsp2o-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). Let , and suppose that:
- a 1-busy period commences at : for some , no part waits in buffer at any time in ;
- is a 1-busy period: at every some part waits in .
Then
This is the base case of the induction that proves Theorem 1: once buffer has emptied, it never stays continuously occupied for longer than .
Formalization Note Buffer is Lean index 0. The page assumes , the first time empties, only to make "commences" meaningful; the statement assumes the commencing condition itself and , a mild generalization. Waiting excludes parts in service, as does on p. 1409.
Preamble
import Mathlib import Definitions.Def_ReentrantScheduling_FBFS_Model import Definitions.Def_ReentrantScheduling_FBFS_Constants
Formal statement
namespace ReentrantScheduling.FBFS
theorem gamma1_busy_period_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₁ T₂ : ℝ) (hT₁ : 0 < T₁) (hT₁₂ : T₁ ≤ T₂)
(hcommence : ∃ δ > 0, ∀ t : ℝ, T₁ - δ < t → t < T₁ →
∀ q, ¬ R.Waiting q ⟨0, L.l_pos⟩ t)
(hbusy : ∀ t : ℝ, T₁ ≤ t → t ≤ T₂ → R.Busy ⟨0, L.l_pos⟩ t) :
T₂ - T₁ ≤ L.Gamma lam γ ⟨0, L.l_pos⟩ := by sorry
end ReentrantScheduling.FBFS
Source
Lu & Kumar, Distributed Scheduling Based on Due Dates and Buffer Priorities, IEEE TAC 36(12), 1991, p. 1409, proof of Theorem 1, the case i = 1 (bound on Γ^(1))
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.