Theorem 1, p. 1409 — FBFS is stable whenever the arrivals satisfy (1) and ρ < 1
ProvedReentrantScheduling.FBFS.theorem1_fbfs_stableTheorem 1 (Stability of FBFS). Consider a nonacyclic flow line with service centers, identical machines at center , route and processing times . Let with load
Then every admissible run of the first buffer first serve (FBFS) policy whose releases satisfy the burstiness constraint
is stable: there is such that every part , initial or released, exits the system and
The constant may depend on the run, in particular on the initial state (p. 1409). Theorem 1 shows that the "push" policy which always serves the earliest buffer at a center never lets delays grow without bound when the arrival rate is within capacity, in contrast with Example 1, where another buffer priority policy is unstable.
Formalization Note The run model is the one of the Model definition: nonidling, nonpreemptive, head-of-buffer dispatch with FBFS priority (L.fbfs), times in WithTop ℝ so that a never-served part has exit time , and counts by Set.encard. Initial parts have . The pinned hypothesis is part of the line data. is quantified after the run, as on the page.
import Mathlib import Definitions.Def_ReentrantScheduling_FBFS_Model
namespace ReentrantScheduling.FBFS
theorem theorem1_fbfs_stable
(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 γ) :
R.Stable := by sorry
end ReentrantScheduling.FBFS
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.