Example 1, pp. 291–292 — on the re-entrant line with τ₂ + τ₄ > 1, the clearing policy is unstable, with or without set-up times
ProvedKumarSeidman.Reentrant.example1_clearing_unstableConsider the manufacturing system of Example 1: one part type arriving at rate visits machine 1, machine 2, machine 2 and machine 1, through buffers , with processing times satisfying the critical condition (3) and the capacity condition (1), i.e.
Start from with machine 1 set up for buffer 4 and machine 2 set up for buffer 3, and schedule with a clearing policy.
- Case 1 (positive set-up times). If , there is such that for every with , a clearing trajectory from this initial state exists, and along every such trajectory
- Case 2 (no set-up times). If , then for every a clearing trajectory from this initial state exists, and along every such trajectory .
So the system is unstable under clearing even though every machine has spare capacity; in Case 2 the instability is caused purely by starvation of machines by upstream machines, not by set-up times.
Formalization Note The paper's conclusions are (Case 1) and (Case 2); their common content, unboundedness of on , is stated as: for every there is with . The existence of a clearing trajectory is part of the statement, so the universal half is not vacuous. "Clearing" uses the reading of Definition 1 recorded with the clearing definition (a target buffer counts as nonempty when it is demanding). Time is real, and the model has no transport delays.
import Mathlib import Definitions.Def_KumarSeidman_Reentrant_System import Definitions.Def_KumarSeidman_Reentrant_Trajectory import Definitions.Def_KumarSeidman_Reentrant_Clearing import Definitions.Def_KumarSeidman_Reentrant_Example1
namespace KumarSeidman.Reentrant
/-- **Example 1** (Kumar–Seidman 1990, §III, pp. 291–292). Consider the re-entrant line of
Example 1 with processing times `τ₁, …, τ₄ > 0` (Lean `τ 0, …, τ 3`) satisfying the critical
condition (3) `τ₂ + τ₄ > 1` and the capacity condition (1), i.e. (4) `τ₁ + τ₄ < 1` and
(5) `τ₂ + τ₃ < 1`. Start from `x(0) = (ξ, 0, 0, 0)` with machine 1 set up for buffer 4 and
machine 2 set up for buffer 3.
* (Case 1, positive set-up times) If `δ₁, …, δ₄ > 0`, there is `ξ₀` such that for every
`ξ > 0` with `ξ ≥ ξ₀` a clearing trajectory from that initial state exists, and along every
such trajectory the level `x₁` of buffer 1 is unbounded on `[0, ∞)`.
* (Case 2, no set-up times) If `δ₁ = ⋯ = δ₄ = 0`, the same holds for every `ξ > 0`. -/
theorem example1_clearing_unstable (τ : Fin 4 → ℝ) (hτ : ∀ k, 0 < τ k)
(h3 : 1 < τ 1 + τ 3) (h4 : τ 0 + τ 3 < 1) (h5 : τ 1 + τ 2 < 1) :
(∀ (δ : Fin 4 → ℝ) (hδ : ∀ k, 0 < δ k),
∃ ξ₀ : ℝ, ∀ ξ : ℝ, 0 < ξ → ξ₀ ≤ ξ →
(∃ T : Trajectory (ex1 τ hτ δ (fun k => (hδ k).le)),
IsClearing (ex1 τ hτ δ (fun k => (hδ k).le)) T ∧ Ex1Initial T ξ) ∧
∀ T : Trajectory (ex1 τ hτ δ (fun k => (hδ k).le)),
IsClearing (ex1 τ hτ δ (fun k => (hδ k).le)) T → Ex1Initial T ξ →
∀ C : ℝ, ∃ t : ℝ, 0 ≤ t ∧ C < T.x (ex1Buf 0) t) ∧
(∀ ξ : ℝ, 0 < ξ →
(∃ T : Trajectory (ex1 τ hτ (fun _ => 0) (fun _ => le_refl 0)),
IsClearing (ex1 τ hτ (fun _ => 0) (fun _ => le_refl 0)) T ∧ Ex1Initial T ξ) ∧
∀ T : Trajectory (ex1 τ hτ (fun _ => 0) (fun _ => le_refl 0)),
IsClearing (ex1 τ hτ (fun _ => 0) (fun _ => le_refl 0)) T → Ex1Initial T ξ →
∀ C : ℝ, ∃ t : ℝ, 0 ≤ t ∧ C < T.x (ex1Buf 0) t) := by sorry
end KumarSeidman.Reentrant
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.