Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Example 2, p. 293 — the same system has a bounded and an unbounded clearing trajectory

Proved
KumarSeidman.TwoType.example2_modes_coexist

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

clearing-policyinstabilitymanufacturing-systemsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1schedulingstability

Consider the system of Example 2: two part types with input rate 111, part type 1 visiting buffer 1 at machine 1 and then buffer 2 at machine 2, part type 2 visiting buffer 3 at machine 2 and then buffer 4 at machine 1. Processing times τ1,…,τ4\tau_1,\dots,\tau_4τ1​,…,τ4​ and set-up times δ1,…,δ4\delta_1,\dots,\delta_4δ1​,…,δ4​ are positive, and they satisfy

τ2+τ4>1,(7)\tau_2+\tau_4>1, \tag{7}τ2​+τ4​>1,(7) δ1+δ41−τ1−τ4=δ2+δ31−τ2−τ3=:η,(8)\frac{\delta_1+\delta_4}{1-\tau_1-\tau_4}=\frac{\delta_2+\delta_3}{1-\tau_2-\tau_3}=:\eta, \tag{8}1−τ1​−τ4​δ1​+δ4​​=1−τ2​−τ3​δ2​+δ3​​=:η,(8) δ4<(1−τ3−τ4)η,(9)\delta_4<(1-\tau_3-\tau_4)\eta, \tag{9}δ4​<(1−τ3​−τ4​)η,(9) δ2<(1−τ1−τ2)η,(10)\delta_2<(1-\tau_1-\tau_2)\eta, \tag{10}δ2​<(1−τ1​−τ2​)η,(10)

and the capacity condition (1), τ1+τ4<1\tau_1+\tau_4<1τ1​+τ4​<1 and τ2+τ3<1\tau_2+\tau_3<1τ2​+τ3​<1. Then, under the clearing policy:

  1. (stable mode) From x(0)=(0,η,0,η)x(0)=(0,\eta,0,\eta)x(0)=(0,η,0,η) with machine 1 set up for buffer 1 and machine 2 for buffer 3, a clearing trajectory exists, and every clearing trajectory from this state keeps every buffer level bounded on [0,∞)[0,\infty)[0,∞).
  2. (unstable mode) There is ξ0\xi_0ξ0​ such that for every ξ≥ξ0\xi\ge\xi_0ξ≥ξ0​, from x(0)=(ξ,0,0,0)x(0)=(\xi,0,0,0)x(0)=(ξ,0,0,0) with machine 1 set up for buffer 4 and machine 2 for buffer 3, a clearing trajectory exists, and every clearing trajectory from this state has
sup⁡0≤t<∞x1(t)=+∞.\sup_{0\le t<\infty}x_1(t)=+\infty .0≤t<∞sup​x1​(t)=+∞.

Thus the same system possesses both stable and unstable modes of behaviour, depending only on the initial state, and the instability arises although no part type revisits a machine.

Formalization Note Both modes assert existence of a clearing trajectory, so neither half holds vacuously. Stability and unboundedness are the paper's sup⁡0≤t<∞xp,i(t)<+∞\sup_{0\le t<\infty}x_{p,i}(t)<+\inftysup0≤t<∞​xp,i​(t)<+∞ and its negation for buffer 1 (the paper writes lim sup⁡tx1(t)=+∞\limsup_t x_1(t)=+\inftylimsupt​x1​(t)=+∞, equivalent for these continuous levels). The bound in the stable mode may depend on the trajectory. η\etaη is computed from the data as (δ1+δ4)/(1−τ1−τ4)(\delta_1+\delta_4)/(1-\tau_1-\tau_4)(δ1​+δ4​)/(1−τ1​−τ4​).

Preamble
import Mathlib
import Definitions.Def_KumarSeidman_TwoType_Example2
Formal statement
namespace KumarSeidman.TwoType

open Example2

/-- Example 2 (pp. 292–293): for one system satisfying (7)–(10) and the capacity condition (1),
the clearing policy has both a stable and an unstable mode.

* From `x(0) = (0, η, 0, η)` with machines 1, 2 set up for buffers 1, 3, a clearing trajectory
  exists and every clearing trajectory keeps all buffer levels bounded.
* For every large enough `ξ`, from `x(0) = (ξ, 0, 0, 0)` with machines 1, 2 set up for
  buffers 4, 3, a clearing trajectory exists and every clearing trajectory has `x₁` unbounded
  on `[0, ∞)`. -/
theorem example2_modes_coexist (τ₁ τ₂ τ₃ τ₄ δ₁ δ₂ δ₃ δ₄ : ℝ)
    (hτ₁ : 0 < τ₁) (hτ₂ : 0 < τ₂) (hτ₃ : 0 < τ₃) (hτ₄ : 0 < τ₄)
    (hδ₁ : 0 < δ₁) (hδ₂ : 0 < δ₂) (hδ₃ : 0 < δ₃) (hδ₄ : 0 < δ₄)
    (h7 : τ₂ + τ₄ > 1)
    (h8 : (δ₁ + δ₄) / (1 - τ₁ - τ₄) = (δ₂ + δ₃) / (1 - τ₂ - τ₃))
    (h9 : δ₄ < (1 - τ₃ - τ₄) * ((δ₁ + δ₄) / (1 - τ₁ - τ₄)))
    (h10 : δ₂ < (1 - τ₁ - τ₂) * ((δ₁ + δ₄) / (1 - τ₁ - τ₄)))
    (h1₁ : τ₁ + τ₄ < 1) (h1₂ : τ₂ + τ₃ < 1) :
    let η := (δ₁ + δ₄) / (1 - τ₁ - τ₄)
    ((∃ T : (example2 τ₁ τ₂ τ₃ τ₄ δ₁ δ₂ δ₃ δ₄).Schedule,
        T.IsClearingFrom (levels 0 η 0 η) (setups b₁ b₃)) ∧
      ∀ T : (example2 τ₁ τ₂ τ₃ τ₄ δ₁ δ₂ δ₃ δ₄).Schedule,
        T.IsClearingFrom (levels 0 η 0 η) (setups b₁ b₃) → T.IsBounded) ∧
    ∃ ξ₀ : ℝ, ∀ ξ ≥ ξ₀,
      (∃ T : (example2 τ₁ τ₂ τ₃ τ₄ δ₁ δ₂ δ₃ δ₄).Schedule,
          T.IsClearingFrom (levels ξ 0 0 0) (setups b₄ b₃)) ∧
        ∀ T : (example2 τ₁ τ₂ τ₃ τ₄ δ₁ δ₂ δ₃ δ₄).Schedule,
          T.IsClearingFrom (levels ξ 0 0 0) (setups b₄ b₃) →
            ¬ BddAbove (T.x b₁ '' Set.Ici 0) := by sorry

end KumarSeidman.TwoType
Source
Kumar & Seidman, Dynamic Instabilities and Stabilization Methods in Distributed Real-Time Scheduling of Manufacturing Systems, IEEE Trans. Automat. Control 35(3), 1990, pp. 292–293, Example 2 (conclusion, p. 293)
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