2.5.3 M/G/1-type processes

Consider again the example of the M/Hypo(2)/1 queue. Now suppose that the arrivals can occur in bulk, i.e., one job arrives with rate $\lambda$, two jobs arrive simultaneously with rate $\lambda/2$, three jobs arrive simultaneously with rate $\lambda/4$, i.e., the bulk sizes decrease geometrically. The service process consists of two exponential phases in series. The state transition diagram of this process is illustrated in Figure 2.4.

Figure 2.4: The state transition diagram of a M/Hypo(2)$1$ queue with bulk arrivals.

The processes with similar patterns in the embedded Markov chain are known as M/G/1-type or skip-free to the left processes. Their infinitesimal generator matrix ${\mathbf{Q}}_{M/G/1}$ can be block-partitioned as:

$${\mathbf{Q}}_{M/G/1} = \left[ \begin{array}{c c c c c c c } ... ...vdots & \vdots & \vdots & \vdots & \ddots \end{array}\right] .$$ (2.22)

The infinitesimal generator ${\mathbf{Q}}_{M/G/1}$ of an M/G/1 type process is an upper Hessenberg matrix, i.e., the blocks below the main block-diagonal, but the first one, are all zero matrices. As depicted in Figure 2.4, M/G/1-type processes usually characterize bulk arrivals, i.e., more than one job may arrive in the queueing system at a time [34]. We give details on solution methods for M/G/1-type processes in Chapter 3.