Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Example 2, Case 2, Stage 8, p. 293 — machine 2 clears buffer 2 at t9t_9t9​ with x(t9)=(0,0,t9−δ1,0)x(t_9)=(0,0,t_9-\delta_1,0)x(t9​)=(0,0,t9​−δ1​,0)

Proved
KumarSeidman.TwoType.case2_stage8

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. There is ξ0\xi_0ξ0​ such that for every ξ≥ξ0\xi\ge\xi_0ξ≥ξ0​ every clearing trajectory from this state satisfies, with

t9=ξ+τ2−1(δ1+δ2)τ2−1−1,t_9=\frac{\xi+\tau_2^{-1}(\delta_1+\delta_2)}{\tau_2^{-1}-1},t9​=τ2−1​−1ξ+τ2−1​(δ1​+δ2​)​,

the identity

x(t9)=(0, 0, t9−δ1, 0),x(t_9)=(0,\,0,\,t_9-\delta_1,\,0),x(t9​)=(0,0,t9​−δ1​,0),

and at t9t_9t9​ machine 1 is set up for buffer 1 and machine 2 is set up for buffer 2 (which it has just cleared).

The state at t9t_9t9​ is the mirror image of the initial state: the role of buffers 1, 2 and machine 1 is now played by buffers 3, 4 and machine 2. The level of buffer 3 is t9−δ1t_9-\delta_1t9​−δ1​, the amount that arrived since machine 2 last served it.

Formalization Note The paper's t1t_1t1​ is 000. "ξ\xiξ large enough" is rendered as ∃ξ0 ∀ξ≥ξ0\exists\xi_0\,\forall\xi\ge\xi_0∃ξ0​∀ξ≥ξ0​. Conditions (8)–(10) are not assumed (the paper states they are unnecessary for Case 2). The denominator τ2−1−1\tau_2^{-1}-1τ2−1​−1 is positive because τ2<1\tau_2<1τ2​<1 by (1).

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

open Example2

/-- Example 2, Case 2, Stage 8 (p. 293): 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₉ = (ξ + τ₂⁻¹(δ₁ + δ₂))/(τ₂⁻¹ − 1)` the state `x(t₉) = (0, 0, t₉ − δ₁, 0)`, with machine 1
set up for buffer 1 and machine 2 for buffer 2. -/
theorem case2_stage8 (τ₁ τ₂ τ₃ τ₄ δ₁ δ₂ δ₃ δ₄ : ℝ)
    (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)
        (∀ b, T.x b t₉ = levels 0 0 (t₉ - δ₁) 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, Stage 8
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