Subadditivity and Stability of a Class of Discrete-Event Systems

We investigate the stability of discrete-event systems modeled as generalized semi-Markov processes with event epochs that satisfy (max, +) recursions. We obtain three types of results, under conditions: We show that there exists for each event a cycle time, which is the long-run average time between event occurrences; we characterize the rate of convergence to this limit, bounding the error for finite horizons; and we give conditions for delays (i.e., differences between event epochs) to converge to a stationary regime. The main tools for the cycle time results are (max, +) matrix products and the subadditive ergodic theorem. The convergence rate result (which assumes bounded i.i.d. inputs) is based on a martingale inequality. The stability of delays is derived from existing results on the stability of stochastic difference equations. We discuss connections with these different fields, with the general theory of random matrix products and with recent results for discrete-event systems. © 1995 IEEE