Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 1 1): a queued buffer completes its next run within γm−ζm\gamma_m-\zeta_mγm​−ζm​

Proved
KumarSeidman.Supervisor.lemma1_wait_bound

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

manufacturing-systemsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1schedulingsupervisory-control

Consider a system satisfying the capacity condition (1), supervisor parameters γ\gammaγ satisfying (24) and thresholds z≥0z\ge 0z≥0, and a supervised trajectory. Let bp,ib_{p,i}bp,i​ be a buffer of machine m=μp,im=\mu_{p,i}m=μp,i​ that enters the priority queue QmQ_mQm​ at time tint_{\mathrm{in}}tin​. Then its subsequent processing run exists, and the time tcompletet_{\mathrm{complete}}tcomplete​ at which it is completed satisfies

tcomplete−tin≤γm−ζm,ζm=γm(1−ρm)−∑b∈Bmmax⁡b′∈Bmδb′,b.t_{\mathrm{complete}}-t_{\mathrm{in}}\le \gamma_m-\zeta_m,\qquad \zeta_m=\gamma_m(1-\rho_m)-\sum_{b\in B_m}\max_{b'\in B_m}\delta_{b',b}.tcomplete​−tin​≤γm​−ζm​,ζm​=γm​(1−ρm​)−b∈Bm​∑​b′∈Bm​max​δb′,b​.

This is the basic waiting-time guarantee of the supervisor: once a buffer is queued, the machine must reach it within a bounded time, whatever the underlying policy does.

Formalization Note As on the page, tint_{\mathrm{in}}tin​ is an instant at which bp,ib_{p,i}bp,i​ enters QmQ_mQm​ (Lean EntersQ: it is in QmQ_mQm​ at tint_{\mathrm{in}}tin​, and tin=0t_{\mathrm{in}}=0tin​=0 or it was not waiting in QmQ_mQm​ just before). QmQ_mQm​ is not a separate state: a buffer is in QmQ_mQm​ exactly when the machine's current run is not on it and its level exceeds zp,iz_{p,i}zp,i​. Existence of the subsequent run is part of the conclusion.

Preamble
import Mathlib
import Definitions.Def_KumarSeidman_Supervisor_System
import Definitions.Def_KumarSeidman_Supervisor_Trajectory
import Definitions.Def_KumarSeidman_Supervisor_Mechanism
Formal statement
namespace KumarSeidman.Supervisor

/-- Lemma 1 1) (Kumar–Seidman 1990, p. 296, (25)–(26)). If buffer `b` enters the priority
queue `Q_m` (`m = μ_b`) at time `t_in`, then its subsequent processing run exists and is
completed by `t_in + γ_m − ζ_m`. -/
theorem lemma1_wait_bound {P M : ℕ} (S : System P M) (hcap : S.CapacityCondition)
    (γ : Fin M → ℝ) (hγ : GammaCondition S γ) (z : Buffer S → ℝ) (hz : ∀ b, 0 ≤ z b)
    (T : Trajectory S) (hT : T.Supervised γ z) (b : Buffer S) (tIn : ℝ)
    (hin : T.EntersQ z b tIn) :
    ∃ k : ℕ, T.IsNextRun b tIn k ∧ T.HasNext (S.mach b) k ∧
      T.s (S.mach b) (k + 1) - tIn ≤ γ (S.mach b) - zeta S γ (S.mach b) := by sorry

end KumarSeidman.Supervisor
Source
Kumar & Seidman, Dynamic Instabilities and Stabilization Methods in Distributed Real-Time Scheduling of Manufacturing Systems, IEEE Trans. Automat. Control 35(3), 1990, p. 296, Lemma 1 1), (25)–(26)
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