Example 1, Case 1, pp. 291–292 — every clearing trajectory from a large backlog has unbounded buffer 1
ProvedKumarSeidman.Reentrant.example1_case1_all_unboundedinstabilitymanufacturing-systemsscheduling
Consider the re-entrant line of Example 1. One part type arrives at rate and visits machine 1, machine 2, machine 2 and machine 1, through buffers . The processing times satisfy
and the set-up times are positive. The initial state is , with machine 1 set up for buffer 4 and machine 2 set up for buffer 3.
Claim. There is such that for every with , every clearing trajectory from this initial state satisfies
The reason is the paper's cycle map: the state returns as with .
Formalization Note. Unboundedness is stated as: for every there is with .
Preamble
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
Formal statement
namespace KumarSeidman.Reentrant
/-- **Example 1, Case 1, instability** (Kumar–Seidman 1990, §III, pp. 291–292). With (3)–(5) and
positive set-up times, for all sufficiently large backlogs `ξ`, along every clearing trajectory
starting at `x(0) = (ξ, 0, 0, 0)` (machine 1 set up for buffer 4, machine 2 for buffer 3) the
level of buffer 1 is unbounded. -/
theorem example1_case1_all_unbounded (τ : 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 ξ →
∀ C : ℝ, ∃ t : ℝ, 0 ≤ t ∧ C < T.x (ex1Buf 0) t := by sorry
end KumarSeidman.ReentrantSource
Kumar & Seidman, Dynamic Instabilities and Stabilization Methods in Distributed Real-Time Scheduling of Manufacturing Systems, IEEE Trans. Automat. Control 35(3), 1990, pp. 291–292, §III Example 1, Case 1