INVESTIGATION OF INTERDEPENDENT PROCESS — A SEMI-MARKOV APPROACH

In this presentation an interdependent system evolving in time is described. A new approach to this introduced through the analysis of such a system using semi-Markov approach. The system consists of processes. When these are independent of each other, the study of the system is not quite complex. However, when these processes evolve according to some dependence law, the analysis becomes complex.

The study of such a system when each component process evolves according to an arbitrary distribution appears quite complex. However, if we assume that only one component process is ON and the remaining are OFF at any given time may simplify the study. A number of examples from queues, inventory, reliability are provided when arbitrary distribution of component processes are replaced by PH distribution or MAP/BMAP. This procedure leads us to a much more extended set up in the analysis of queueing/inventory/reliability systems/medication, or for that matter any system with subcomponents evolving in time. In the specific MAP/MSP/1 queue with interdependence between arrival and service processes we provide limiting distribution.

Suppose there are n processes $S_1, S_2, \dots, S_n$ interdependent processes, evolving in time. If the occurrence of events in each is independent of that in the other and also within itself, then the study of the evolution of the totality of the processes boils down to the study of each separately (for example, all have independent PH distributions). Even if occurrence of events within a process has some dependence (like in a MAP or MSP), then also there is NOT much of complexity. However, what happens if all the n processes evolve according to PH renewal/correlated (MAP/BMAP) processes, but with inter-dependence. Instead of PH distribution/MAP/BMAP, if we have arbitrary distribution, situation is quite complex.

Adaan and Kulkarni (QUESTA 2003 and 2007) considers correlation between inter-arrival time sequence $\{A_n\}$ and the sequence of service times $\{S_n\}$. There are two other papers, one of them as early as 1979 and the second one in 1999 that consider M/M/1 and M/M/c queues with interdependent arrival and service processes. Else I am NOT aware of work even distinctly related to the present one.

Suppose we consider the stochastic process $S_i$ evolving according to $PH_i$, with representation $(\alpha_i,T_i)$ of order $m_i$ for $i = 1, 2, \dots, n$. That is, in the general description above, $G_i(\bullet)$ is replaced by $PH_i$. The advantage here is that the sojourn time in a process before the next event (whatever type) occurrence is Phase-type distributed (see Neuts (1975)). Until then transitions are within the transient phases of processes involved. On realization of the next event, the phase where to start is sampled out from the initial probability distribution. The gain in the assumption that inter-occurrence times of events in each process is phase type distributed is that the sojourn time until the occurrence of next event is the convolution of a random number of exponential random variables, with transitions within the transient phases of all processes which is also also governed by a Markov chain obtained by considering the n-dimensional Markov chain. Thus here also we have a semi-Markov process determining the evolution. The great advantage is that the Matrix-Geometric Algorithm (see Neuts (1994)) comes in handy for computation.

However, there is a bit of theory behind the computation in this complex process. This will be elaborated in the “full paper”. Specific problems in queueing theory will be addressed there, namely the MAP/MSP/1 queueing system with interdependent arrival and service processes. This means that the inter-arrival times and service times are correlated. A comparison with MAP/MSP/1 without this inter-dependence will be given through numerical illustrations. Therefore, this specific example (MAP/MSP/1 queue with interdependent inter-arrival and service times, that we use to illustrate the theory as well as computational aspects, has two levels of dependence structures: (i) MAP brings in correlation between successive inter-arrival times and MSP, that between successive service times and (ii) the inter-dependence between inter-arrival times and service times brings in correlation between the arrival and service processes. Thus effectively three correlation structures interact.

This comparison throws light on the relative performance of the two systems (inter-dependent and independent).

The theory and the computational procedure developed in this paper can effectively be used for complex process such as Reliability of k-out-of-n –G system when the component life times are inter-dependent; in queueing-inventory when the inter-arrival and service times are inter-dependent, or in production inventory with positive service time where inter-arrival times, service times and inter-production times of inventory items are inter-dependent. It can also be efficiently used in the analysis of many-server queues/queueing-inventory/reliability of the system talked about earlier when repair process is introduced and so on. It can also be used in Insurance and Risk modeling, in Chemistry for study of chemical reaction; the list is endless.

Most of these problems are under investigation by research groups at Cochin University of Science and Technology and that at CMS College, Kottayam, separately as well as collectively.

Reference:

1. Cinlar, E. (1975): Introduction to Stochastic Processes, Dover Publications, INC, Mineola, New York.
2. Neuts, M.F. (1975): Probability distributions of phase type. Liber Amicorum Prof. Emeritus H. Florin.
3. Neuts, M.F.(1994): Matrix-geometric solutions in stochastic models: an algorithmic approach. Courier Corporation.
4. Ross, S.M. (1970): Applied Probability Models with Optimization Applications, Dover Publications, INC., New York.