Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

(18): drift of V_m between consecutive set-up commencements at a machine of a minimal class

Proved
KumarSeidman.CAF.drift_at_setups

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

clearing-policylyapunov-functionmanufacturing-systemsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1stability

Let the system satisfy condition (14), ρm′′<1\rho'_{m'}<1ρm′′​<1 for every machine m′m'm′, and consider a trajectory under a clearing policy. Let mmm be a machine whose class is minimal for the partial order of diconnected classes, and let Tn≤Tn+1T_n\le T_{n+1}Tn​≤Tn+1​ be two consecutive times at which mmm commences a set-up. Then

Vm(Tn+1) ≤ max⁡[0, Vm(Tn)−(1−ρm′)(Tn+1−Tn)+δˉ],V_m(T_{n+1})\ \le\ \max\big[0,\ V_m(T_n)-(1-\rho'_m)(T_{n+1}-T_n)+\bar\delta\big],Vm​(Tn+1​) ≤ max[0, Vm​(Tn​)−(1−ρm′​)(Tn+1​−Tn​)+δˉ],

where VmV_mVm​ is the Lyapunov function (15) and δˉ\bar\deltaδˉ the largest set-up time between buffers of mmm.

Over one cycle of machine mmm the work it receives is at most ρm′\rho'_mρm′​ per unit time, while it completes work at unit rate except during the set-up and while starved; this drift inequality drives the boundedness of VmV_mVm​ on minimal classes.

Formalization Note Tn,Tn+1T_n,T_{n+1}Tn​,Tn+1​ are the starts sk,sk+1s_k,s_{k+1}sk​,sk+1​ of two consecutive runs k≥1k\ge1k≥1 and k+1k+1k+1 of mmm, which need not be strictly ordered. Only the clearing property is assumed (the paper is in the CAF context, but (18) uses only Definition 1). δˉ≥0\bar\delta\ge0δˉ≥0 is not assumed positive; the paper's "δˉ>0\bar\delta>0δˉ>0" is a remark. The minimality of the class of mmm is stated without quotients: every machine from which mmm is reachable is reachable from mmm.

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

/-- (18) (p. 295): under (14) and a clearing policy, for a machine `m` whose class is minimal
and two consecutive set-up commencements `T_n = s_k`, `T_{n+1} = s_{k+1}` (`k ≥ 1`) at `m`,
`V_m(T_{n+1}) ≤ max [0, V_m(T_n) − (1 − ρ'_m)(T_{n+1} − T_n) + δ̄]`. -/
theorem drift_at_setups {P M : ℕ} (S : System P M) (h14 : S.StringentCapacityCondition)
    (T : Trajectory S) (hT : T.IsClearing) (m : Fin M) (hmin : S.IsMinimal m) (k : ℕ)
    (hk : 1 ≤ k) (hnext : T.HasNext m k) :
    T.V m (T.s m (k + 1)) ≤
      max 0 (T.V m (T.s m k) - (1 - S.rhoPrime m) * (T.s m (k + 1) - T.s m k)
        + S.deltaBar m) := 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. 295, proof of Theorem 1, (18)
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