(20): a large buffer at a set-up commencement forces a long clearing run
ProvedKumarSeidman.CAF.clearing_run_lengthclearing-policymanufacturing-systemsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Consider a trajectory under a clearing policy and a machine with . Suppose commences a set-up to buffer at time , and its next set-up commencement is at . Then
The machine may only leave once it is empty, and it cannot empty it faster than at rate ; so long set-up-to-set-up cycles follow from large selected buffers, which is what amortizes the set-up time in the Lyapunov argument.
Formalization Note and for a run of that is followed by run . Only the clearing property and for this machine are assumed.
Preamble
import Mathlib import Definitions.Def_KumarSeidman_CAF_System import Definitions.Def_KumarSeidman_CAF_Trajectory import Definitions.Def_KumarSeidman_CAF_Policy import Definitions.Def_KumarSeidman_CAF_Lyapunov
Formal statement
namespace KumarSeidman.CAF
/-- (20) (p. 295): under a clearing policy, if machine `m` with `ρ'_m < 1` commences a set-up
to buffer `b* = β m k` at `T_n = s_k` (`k ≥ 1`) and its next set-up commencement is
`T_{n+1} = s_{k+1}`, then
`x_{b*}(T_n) ≥ 2 δ̄ / ((1 − ρ'_m) τ_{b*}) ⇒ T_{n+1} − T_n ≥ 2 δ̄ / (1 − ρ'_m)`. -/
theorem clearing_run_length {P M : ℕ} (S : System P M) (T : Trajectory S)
(hT : T.IsClearing) (m : Fin M) (hρ : S.rhoPrime m < 1) (k : ℕ) (hk : 1 ≤ k)
(hnext : T.HasNext m k)
(hx : 2 * S.deltaBar m / ((1 - S.rhoPrime m) * S.tau (T.β m k)) ≤ T.x (T.β m k) (T.s m k)) :
2 * S.deltaBar m / (1 - S.rhoPrime m) ≤ T.s m (k + 1) - T.s m k := by sorry
end KumarSeidman.CAF
Source
Kumar & Seidman, Dynamic Instabilities and Stabilization Methods in Distributed Real-Time Scheduling of Manufacturing Systems, IEEE Trans. Automat. Control 35(3), 1990, p. 295, proof of Theorem 1, (20)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.