Example 2, p. 293 — the same system has a bounded and an unbounded clearing trajectory
ProvedKumarSeidman.TwoType.example2_modes_coexistConsider the system of Example 2: two part types with input rate , 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 and set-up times are positive, and they satisfy
and the capacity condition (1), and . Then, under the clearing policy:
- (stable mode) From 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 .
- (unstable mode) There is such that for every , from 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
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 and its negation for buffer 1 (the paper writes , equivalent for these continuous levels). The bound in the stable mode may depend on the trajectory. is computed from the data as .
import Mathlib import Definitions.Def_KumarSeidman_TwoType_Example2
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.