6. Aggregate Solutions of GI/G/1-type Processes

In this chapter, we study a class of CTMCs with GI/G/1-type patterns in their repetitive structure, that is they exhibit both M/G/1-type and GI/M/1-type patterns. GI/G/1-type processes cannot be solved exactly by existing techniques, but can alternatively be approximated by QBDs [34]. Such processes occur when modeling open systems that accept customers from multiple exogenous sources (i.e., accepting bulk arrivals) and are also subject to failures and repairs (i.e., the system may empty-out in a single step when a catastrophic failure occurs or only parts of it may be operational when a non-catastrophic failure occurs).

Recall that, as defined in Eq.(2.23), the infinitesimal generator ${\mathbf{Q}}$ can be block-partitioned as

$${\mathbf{Q}}= \left[ \begin{array}{c c c c c c} \L ^{(0)} & ... ...\vdots & \vdots & \vdots & \vdots & \ddots \end{array}\right].$$ (6.1)

Our approach focuses on separating the GI/M/1-type behavior of the system from the M/G/1-type behavior by defining new decomposed CTMCs using stochastic complementation and pseudo-stochastic complementation techniques. The decomposed CTMCs of the M/G/1 and GI/M/1 type can be solved using matrix analytic methods. The solution of the original GI/G/1-type CTMC is then obtained by coupling the solutions of the decomposed CTMCs of M/G/1-type and GI/M/1-type.

The chapter is organized as follows. In Section 6.1, we outline some additional results on stochastic complementation. In Section 6.2, we define pseudo-stochastic complementation as a variation of stochastic complementation. We give the high level idea of our approach in Section 6.3. The general approach is outlined in Section 6.4, followed by formalization of the algorithm in Sections  6.4,  6.5,  6.6,  6.7,  6.8. The case when multiple M/G/1-type and GI/M/1-type subchains can be identified within the original GI/G/1-type CTMC is analyzed in Section 6.9. In Section 6.10, the applicability of the technique is illustrated by solving a GI/G/1-type CTMC that arises in the area of parallel processor scheduling. We conclude the chapter with a summary of the results.