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
can be block-partitioned as

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.

- 6.1 Non-disjoint coupling
- 6.2 Pseudo-stochastic complementation
- 6.3 GI/G/1 solution (High-level idea)
- 6.4 GI/G/1 solution - General approach
- 6.5 Determining the upper and lower sets
- 6.6 Determining a gate state
- 6.7 Generation of the new ``upper'' process
- 6.8 Generation of the new ``lower'' process
- 6.9 Multiple upper-lower classes
- 6.10 Application: parallel scheduling in the presence of failures
- 6.11 Chapter summary