Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1 (Kumar–Seidman): if ρ′ₘ < 1 for every machine, all CAF policies are stable for all initial conditions

Proved
KumarSeidman.CAF.caf_policies_stable

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

clear-a-fractionmanufacturing-systemsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1schedulingstability

Consider a manufacturing system with PPP part types and MMM machines, routes μp,1,…,μp,np\mu_{p,1},\dots,\mu_{p,n_p}μp,1​,…,μp,np​​ (revisits allowed), input rates dp>0d_p>0dp​>0, processing times τp,i>0\tau_{p,i}>0τp,i​>0 and set-up times δb,b′≥0\delta_{b,b'}\ge0δb,b′​≥0. For each buffer bp,ib_{p,i}bp,i​ let λp,i\lambda_{p,i}λp,i​, the prior machine πp,i\pi_{p,i}πp,i​ and the modified input rate dp,i′d'_{p,i}dp,i′​ be defined by (11)–(13): dp,i′=1/τp,λp,id'_{p,i}=1/\tau_{p,\lambda_{p,i}}dp,i′​=1/τp,λp,i​​ if the prior machine exists and is diconnected with μp,i\mu_{p,i}μp,i​, and dp,i′=dpd'_{p,i}=d_pdp,i′​=dp​ otherwise. If the more stringent capacity condition

ρm′:=∑(p,i): μp,i=mdp,i′ τp,i<1for all m(14)\rho'_m:=\sum_{(p,i):\,\mu_{p,i}=m}d'_{p,i}\,\tau_{p,i}<1\qquad\text{for all } m \tag{14}ρm′​:=(p,i):μp,i​=m∑​dp,i′​τp,i​<1for all m(14)

holds, then all CAF policies are stable for all system initial conditions: for all constants εm>0\varepsilon_m>0εm​>0 and KmK_mKm​, every fluid trajectory, from any initial levels and initial set-ups, that obeys the clearing rule (Definition 1) and the clear-a-fraction rule (2) with these constants satisfies

sup⁡0≤t<∞xp,i(t)<+∞for every buffer bp,i.\sup_{0\le t<\infty}x_{p,i}(t)<+\infty\qquad\text{for every buffer } b_{p,i}.0≤t<∞sup​xp,i​(t)<+∞for every buffer bp,i​.

Theorem 1 contrasts with the examples of §III, in which clearing policies are unstable although the usual capacity condition ρm<1\rho_m<1ρm​<1 holds: on machines that lie in a common cycle of material flow, (14) budgets for the peak rate at which an upstream machine can release parts, not only for the average rate dpd_pdp​.

Formalization Note The model, the reading of "nonempty" in Definition 1 as "nonempty or with inflow starting now", and the run structure are those of the imported definition files. The bound on each buffer may depend on the trajectory (and so on the initial state); no bound uniform in the initial state is claimed. Condition (1) is not assumed separately: (14) implies it, since dp,i′≥dpd'_{p,i}\ge d_pdp,i′​≥dp​. Set-up times may be zero.

Preamble
import Mathlib
import Definitions.Def_KumarSeidman_CAF_System
import Definitions.Def_KumarSeidman_CAF_Trajectory
import Definitions.Def_KumarSeidman_CAF_Policy
Formal statement
namespace KumarSeidman.CAF

/-- **Theorem 1** (Kumar–Seidman 1990, p. 294). If the more stringent capacity condition (14),
`ρ'_m < 1` for every machine `m`, holds, then all CAF policies are stable for all system
initial conditions: for all CAF constants `ε_m > 0`, `K_m`, and every trajectory from any
initial state obeying the clearing and clear-a-fraction rules with these constants, every
buffer level is bounded on `[0, ∞)`. -/
theorem caf_policies_stable {P M : ℕ} (S : System P M) (h14 : S.StringentCapacityCondition)
    (ε K : Fin M → ℝ) (T : Trajectory S) (hT : T.IsCAF ε K) : T.IsStable := by sorry

end KumarSeidman.CAF
Source
Kumar & Seidman, Dynamic Instabilities and Stabilization Methods in Distributed Real-Time Scheduling of Manufacturing Systems, IEEE Trans. Automat. Control 35(3), 1990, p. 294, Theorem 1, (11)–(14)
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me