Asymptotic behavior of random discrete event systems (Q2640233)

A large class of dynamic systems such as the material flow in production or assembly lines, the message flow in communication networks, and jobs in computer systems can be modeled by discrete event dynamic systems (DEDS). To better understand what a DEDS is, let us explicitly describe such a system. Consider a production network which consists of a fixed number n of nodes. Denote by \(x_ i(k)\), \(1\leq i\leq n\), \(k\in {\mathbb N}^*\), the time point at which node i becomes active (i.e. starts production) for the \(k\)th time. Suppose that in order to start the \((k+1)\)st activity at node \(i\), it is necessary to wait until each node \(j\), \(1\leq j\leq n\), has finished its \(k\)th activity and `supplied' node \(i\), and that node \(i\) becomes active for the \((k+1)\)st time as soon as all necessary supplies from the \(k\)th production cycle are available at it. Let \(a_{ij}(k)\) denote the sum of the production time at node \(j\) in the \(k\)th cycle and the transport time from node \(j\) to node \(i\). Then the above description leads to the formula \[ x_ i(k+1)=\max_{1\leq j\leq n}(x_ j(k)+a_{ij}(k)),\quad 1\leq i\leq n,\quad k\in {\mathbb N}. \tag{1} \] All the papers written up to now on this subject take up only the case of a deterministic DEDS. However, often in the practice, delay and transport times are of a stochastic nature, either inherently or because of the lack of information concerning the precise nature of the system. The aim of the present paper is to introduce the notion of a random DEDS and to study the asymptotic behaviour of such a model. The first section is devoted to present the state of art of the research in the field of DEDS, including the appropriate references, while the second one is a survey of the main results obtained by using the max-algebra in the temporal approach to (deterministic) DEDS. In the third section the asymptotic behaviour of a random DEDS is investigated. More precisely, let \(x(k)=(x_ 1(k),...,x_ n(k))\) and \(A(k)=(a_{ij}(k))_{1\leq i,j\leq n},\) \(k\in {\mathbb N}\). Assume that \((A(k))_{k\in {\mathbb N}}\) is a sequence of i.i.d. real \(n\times n\) matrices and let the (initial) random vector \(x(0)\) be independent of \((A(k))_{k\in {\mathbb N}}\). Then the system described by (1) is called a random DEDS. In fact, for the sake of simplicity, the authors pay attention only to the case \(n=2\), noting that the results remain in principle valid for any \(n>2\). To get results on the asymptotic behaviour of a random DEDS, define two new random processes \((z(k))_{k\in {\mathbb N}}\) and \((d(k))_{k\in {\mathbb N}^*}\) by the formulae \[ z(k)=x_ 2(k)-x_ 1(k),\quad k\in {\mathbb N},\quad d(k)=x_ 1(k)-x_ 1(k-1),\quad k\in {\mathbb N}^*. \] Then it is possible to prove that \((z(k))_{k\in {\mathbb N}}\) is a Markov chain, whose transition probability function is determined in terms of the distribution of \(A(k)\). Moreover, for each \(k\in {\mathbb N}^*\), it is proved that the distribution of \((d(k),z(k))\), given \(z(0),d(1),z(1),...,d(k-1),z(k-1)\), depends only on \(z(k-1)\), and an explicit form of this distribution is given. As a consequence, \(x_ 1(k)-x_ 1(0)\) is equal in distribution to a sum of random variables whose distributions depend only on an underlying Markov chain, and this, in turn, makes it possible to look at this model as a special case of the so-called \(J-X\) processes already studied by \textit{G. L. O'Brien} [J. Appl. Probab. 11, 582--587 (1974; Zbl 0293.60062)] in the case of a discrete space and by the reviewer and \textit{G. Oprişan} [Z. Wahrscheinlichkeitstheor. Verw. Gebiete 35, 65--73 (1976; Zbl 0314.60046)] in the case of a general state space. The section ends with Theorem 1, which is the most important (theoretical) result in the paper, since it shows that, under some natural assumptions, the expected cycle time of a random DEDS is asymptotically normal. Let us note that this theorem is a special case of Theorem 1 in the second cited paper above. In the fourth section the authors compute the expectation and variance of the cycle time in the special cases of Bernoulli, exponential and uniform delays, and prove that in all three examples the hypotheses in Theorem 1 above are satisfied. Let us note that these computations and proofs are difficult and rather tricky. The last section is divided into two subsections. In Subsection 5.1, assuming that \(a_{21}(k)=-\infty\) with probability one while the other entries are real-valued with probability one, an example is given of a DEDS for which the Markov chain \((z(k))_{k\in {\mathbb N}}\) has no invariant probability measure, resulting in the violation of the hypotheses of Theorem 1. In Subsection 5.2, examples are given which show that, in contrast with the case of a deterministic DEDS, the `slowest' circuit in the network may not determine the asymptotic behaviour of the system.