Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Example 2, Case 2, p. 293 (corrected) — at t17t_{17}t17​, x(t17)=(λξ+α,0,0,0)x(t_{17})=(\lambda\xi+\alpha,0,0,0)x(t17​)=(λξ+α,0,0,0) with the initial set-ups

Proved
KumarSeidman.TwoType.case2_full_cycle

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

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

Consider the system of Example 2 with positive processing times τ1,…,τ4\tau_1,\dots,\tau_4τ1​,…,τ4​ and positive set-up times δ1,…,δ4\delta_1,\dots,\delta_4δ1​,…,δ4​. Assume (7), τ2+τ4>1\tau_2+\tau_4>1τ2​+τ4​>1, 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.

Start at t1=0t_1=0t1​=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 set up for buffer 3. Let

t9=ξ+τ2−1(δ1+δ2)τ2−1−1,t17=t9+t9−δ1+τ4−1(δ3+δ4)τ4−1−1,t_9=\frac{\xi+\tau_2^{-1}(\delta_1+\delta_2)}{\tau_2^{-1}-1},\qquad t_{17}=t_9+\frac{t_9-\delta_1+\tau_4^{-1}(\delta_3+\delta_4)}{\tau_4^{-1}-1},t9​=τ2−1​−1ξ+τ2−1​(δ1​+δ2​)​,t17​=t9​+τ4−1​−1t9​−δ1​+τ4−1​(δ3​+δ4​)​, λ=τ2τ4(1−τ2)(1−τ4),α=[δ1+δ21−τ2−δ1+1τ4(δ3+δ4)](1τ4−1)−1−δ3.\lambda=\frac{\tau_2\tau_4}{(1-\tau_2)(1-\tau_4)},\qquad \alpha=\Big[\frac{\delta_1+\delta_2}{1-\tau_2}-\delta_1+\frac{1}{\tau_4}(\delta_3+\delta_4)\Big]\Big(\frac1{\tau_4}-1\Big)^{-1}-\delta_3 .λ=(1−τ2​)(1−τ4​)τ2​τ4​​,α=[1−τ2​δ1​+δ2​​−δ1​+τ4​1​(δ3​+δ4​)](τ4​1​−1)−1−δ3​.

There is ξ0\xi_0ξ0​ such that for every ξ≥ξ0\xi\ge\xi_0ξ≥ξ0​ every clearing trajectory from this state satisfies

x(t17)=(λξ+α, 0, 0, 0),x(t_{17})=(\lambda\xi+\alpha,\,0,\,0,\,0),x(t17​)=(λξ+α,0,0,0),

and at t17t_{17}t17​ machine 1 is again set up for buffer 4 and machine 2 for buffer 3.

The situation at t17t_{17}t17​ is the initial one with the level of buffer 1 multiplied by λ\lambdaλ and shifted by α\alphaα. Since λ>1\lambda>1λ>1 exactly when τ2+τ4>1\tau_2+\tau_4>1τ2​+τ4​>1, iterating this cycle makes x1x_1x1​ grow without bound.

Formalization Note The printed constant α\alphaα (p. 293) lacks the final −δ3-\delta_3−δ3​. Mirroring Stage 8 (buffers 1↔31\leftrightarrow31↔3, 2↔42\leftrightarrow42↔4, machines 1↔21\leftrightarrow21↔2) from the level x3(t9)=t9−δ1x_3(t_9)=t_9-\delta_1x3​(t9​)=t9​−δ1​ gives x1(t17)=(x3(t9)+τ4−1(δ3+δ4))/(τ4−1−1)−δ3x_1(t_{17})=\big(x_3(t_9)+\tau_4^{-1}(\delta_3+\delta_4)\big)/(\tau_4^{-1}-1)-\delta_3x1​(t17​)=(x3​(t9​)+τ4−1​(δ3​+δ4​))/(τ4−1​−1)−δ3​, which is λξ+α\lambda\xi+\alphaλξ+α with the corrected α\alphaα above; an exact simulation of the sample parameters confirms it. The printed λ\lambdaλ is correct. The closed form of t17t_{17}t17​ is the mirror of the paper's computation of t9t_9t9​. The paper's t1t_1t1​ is 000, and "ξ\xiξ large enough" is rendered as ∃ξ0 ∀ξ≥ξ0\exists\xi_0\,\forall\xi\ge\xi_0∃ξ0​∀ξ≥ξ0​.

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

open Example2

/-- Example 2, Case 2, full cycle (p. 293, with the printed constant `α` corrected by `− δ₃`):
under (7) and the capacity condition (1), for every large enough `ξ`, every clearing trajectory
from `x(0) = (ξ, 0, 0, 0)` with machine 1 set up for buffer 4 and machine 2 for buffer 3 reaches
at `t₁₇ = t₉ + (t₉ − δ₁ + τ₄⁻¹(δ₃ + δ₄))/(τ₄⁻¹ − 1)` the state `x(t₁₇) = (λξ + α, 0, 0, 0)`,
again with machine 1 set up for buffer 4 and machine 2 for buffer 3. -/
theorem case2_full_cycle (τ₁ τ₂ τ₃ τ₄ δ₁ δ₂ δ₃ δ₄ : ℝ)
    (hτ₁ : 0 < τ₁) (hτ₂ : 0 < τ₂) (hτ₃ : 0 < τ₃) (hτ₄ : 0 < τ₄)
    (hδ₁ : 0 < δ₁) (hδ₂ : 0 < δ₂) (hδ₃ : 0 < δ₃) (hδ₄ : 0 < δ₄)
    (h7 : τ₂ + τ₄ > 1) (h1₁ : τ₁ + τ₄ < 1) (h1₂ : τ₂ + τ₃ < 1) :
    ∃ ξ₀ : ℝ, ∀ ξ ≥ ξ₀, ∀ T : (example2 τ₁ τ₂ τ₃ τ₄ δ₁ δ₂ δ₃ δ₄).Schedule,
      T.IsClearingFrom (levels ξ 0 0 0) (setups b₄ b₃) →
        let t₉ := (ξ + τ₂⁻¹ * (δ₁ + δ₂)) / (τ₂⁻¹ - 1)
        let t₁₇ := t₉ + (t₉ - δ₁ + τ₄⁻¹ * (δ₃ + δ₄)) / (τ₄⁻¹ - 1)
        let lam := τ₂ * τ₄ / ((1 - τ₂) * (1 - τ₄))
        let α := ((δ₁ + δ₂) / (1 - τ₂) - δ₁ + (1 / τ₄) * (δ₃ + δ₄)) * ((1 / τ₄) - 1)⁻¹ - δ₃
        (∀ b, T.x b t₁₇ = levels (lam * ξ + α) 0 0 0 b) ∧ T.SetupFor m₁ t₁₇ b₄ ∧
          T.SetupFor m₂ t₁₇ b₃ := 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, p. 293, Example 2, Case 2 (display after Stage 8; α corrected)
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