Decomposition of Open Queueing Networks with Batch Service

Abstract

The decomposition method for non-product form networks with non-exponentially distributed interarrival and service times assumes that nodes within the network can be treated being stochastically independent and internal flows can be approximated by renewal processes. The method consists of three phases to calculate the interarrival times of a node: merging, flow, splitting. Some well-known approximation formulas for ordinary single class open queueing networks calculate the characteristics in each phase for each node as shown by Kuehn, Chylla, Whitt and Pujolle/Ai. Node performance measures such as mean queue length are determined by using approximation formulas for non-Markovian queues. In 2011 the decomposition method was extended to open queueing networks with batch processing using the approximation formula described by Pujolle/Ai. A comparison with discrete event simulation as benchmark shows that the approach provides good results. Thus, the approach was expanded for the approximation given by Kuehn, Chylla and Whitt. Since the method consists of several phases it is possible to combine different formulas. For example, merging will be approximated by Kuehn and flow by Whitt. To perform an evaluation the benchmark was done in regard to the 2011 publication. Approximation formulas with the same approach generate similar results. In some cases, it is apparent that some formulas have advantages over other ones and a few tend to larger errors. Thus, the focus of interest particularly addresses the load and batch size changes within the network and the impact on the accuracy of the decomposition method as a fast solver or pre-evaluation for optimization using simulation.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

The importance of analysis of non-product form networks by applying approximations has increased steadily in recent years. The most important strategy approach is given by the decomposition method. The decomposition method enables an isolated treatment of the nodes within the network. The method is particularly applied in planning and optimization of production systems by calculating characteristics of each node. In this paper, a decomposition method will be presented serving primarily as a pre-evaluation tool. If the calculated characteristics move in acceptable ranges Monte-Carlo simulations can be performed.

Until now the decomposition method for open queuing networks with batch service was developed using the approach of Pujolle/Ai [1]. The aim is to expand the method to common approximations developing the approaches to batch service and to transfer them to the developed method of [1]. This includes the approximate formation of the superposition of the input streams by Kühn [2] and Chylla [3] as well as the approximation of the departure stream by Whitt [4], Kühn and Chylla.

2 Description of the Model

The open network consists of 1 to N nodes numbering successively and presenting $GI^{X_i}/GI^{(b_i, b_i)}/c_i$ queueing systems. Jobs arrive in groups of size $b_0$ from outside the network according to a renewal process with rate $\uplambda _0<\infty$ and the squared coefficient of variation $SCV[I_0]<\infty$. $0\le p_{ij}\le 1$ describes the transition probability that an arriving batch reaches node j from node i and $\sum _{i=1}^Np_{0i}=1$ applies meaning jobs enters the network from outside. Each queueing systems have $c_i$ identical servers, an unlimited waiting room and the FCFS queueing discipline. The service starts if a batch of the required size $b_i$ was generated. The service times are distributed as some random variables $S_i$ with rates $\upmu _i<\infty$ and $SCV[S_i]$. It is assumed that the interarrival and service times are independent. After a complete service of a batch it will arrive in a form of a batch to the subsequent node according to the transition probabilities. $X_i$ is described by an integer random variable and represents the input size of the groups at node i. The first and second moment are calculated by

$$\begin{aligned} E[X_i]=\frac{\sum \limits _{j=0}^N b_j\cdot \uptau _j\cdot p_{ji}}{\sum \limits _{j=0}^{N}\uptau _j\cdot p_{ji}}\qquad \qquad E[X_i^2]=\frac{\sum \limits _{j=0}^{N}b_j^2\cdot \uptau _j\cdot p_{ji}}{\sum \limits _{j=0}^{N}\uptau _j\cdot p_{ji}}. \end{aligned}$$

$\uptau _i$ denotes the relative throughput and can be determined by a modified traffic equation:

$$\begin{aligned} \uptau _i=p_{01}\cdot \frac{b_0}{b_i}+\sum \limits _{j=1}^N\uptau _j\cdot p_{ji}\cdot \frac{b_j}{b_i}\qquad \qquad \uptau _0:=1. \end{aligned}$$

The modified arrival rate of batches can be calculated by $\uplambda _i^*=\uplambda _0\cdot \uptau _i$ and the modified utilization by $\uprho _i^*=\uplambda _i^*/(c_i\upmu _i)<1$.

3 Decomposition of Open Queueing Networks with Batch Service

3.1 Phase 1: Merging

There exist three different approaches to form the superpositions of the arrival streams. The first approach was developed by Pujolle/Ai [5]. The counting process representing the incoming jobs and incoming groups, respectively is described by knowledge of the asymptotic behavior of renewal processes:

$$\begin{aligned} SCV[I_i]=\left( \sum \limits _{j=0}^N\uptau _j p_{ji}\right) ^{-1}\sum \limits _{j=0}^N\uptau _j\cdot p_{ji}\cdot SCV[A_{ji}] \end{aligned}$$

Chylla uses the approach in order to approximate the splitting of the departure stream (see phase 3):

$$\begin{aligned} SCV[I_i]=1+\sum \limits _{j=0}^N\frac{\uplambda _j^*}{\uplambda _i^*}p_{ji}(SCV[A_{ji}]-1). \end{aligned}$$

The approach of Kühn is based on a case-by-case analysis which depends on the values of $SCV[A_{ji}]$ (see phase 3):

$$\begin{aligned} SCV[I_i]=2\cdot \frac{t_1+t_2}{(t_1\cdot t_2)^2}\cdot (I^1+I^2+I^3+I^4)\qquad \qquad t_j=\frac{1}{p_{ji}\uptau _j}, j=1,2. \end{aligned}$$

The components $I^1, \ldots , I^4$ are either a composition of hypoexponentially, hyperexponentially distributed sub-processes or a mixture. For details see [2].

After the interarrival times of the single jobs has been determined the interarrival times of batches will be approximated by [1]:

$$\begin{aligned} SCV[I_i^{*}]\,\approx \,\frac{E[X_i]}{b_i}(SCV[X_i]+SCV[I_i]). \end{aligned}$$

3.2 Phase 2: Flow

There are fundamentally two approaches to approximate the departure stream in a non-product form network. Pujolle/Ai and Chylla use the approach

$$\begin{aligned} D_i=\left\{ \begin{array}{lll} S_i &{} : with\,\,probability&{} \uprho _i^*\\ S_i+I_i^* &{} : with\,\,probability&{} 1-\uprho _i^* \end{array} \right. \end{aligned}$$

and it results for Pujolle/Ai according to the calculation of the first and second moment of the process $D_i$

$$\begin{aligned} SCV[D_i]\,\approx \,\uprho _i^{*2}SCV[S_i]+(1-\uprho _i^{*})SCV[I_i^*]+\uprho _i^{*}(1-\uprho _i^{*}) \end{aligned}$$

and a slightly modified version of Chylla

$$\begin{aligned} SCV[D_i]=1+P_{i}^2(SCV[S_i]-1)+(1-P_{i})(SCV[I_i^*]-1), \end{aligned}$$

where $P_i$ is described by the Erlang-C formula. Whitt and Kühn use the approach of Marshall [6] to approximate the departure stream basing on Lindley’s recursion of waiting times. The formula

$$\begin{aligned} SCV[D_i]\,\approx \,1+(1-\uprho _i^{*2})\cdot (SCV[I_i^*]-1)+\frac{\uprho _i^{*2}}{\sqrt{c_i}}\cdot (SCV[S_i]-1) \end{aligned}$$

represents the approximation of Whitt and Kühn developed the approximation

$$\begin{aligned} SCV[D_i]=SCV[I_i^*]+2\rho _i^{*2}SCV[S_i]-\rho _i^{*2}(SCV[I_i^*]+SCV[S_i])g_{KLB}, \end{aligned}$$

where $g_{KLB}$ is the correction factor given by Krämer/Langenbach-Belz [7].

3.3 Phase 3: Splitting

The splitting of the departure stream in accordance with the transition probabilities can be considered as a Bernoulli experiment. After service completion at node i, jobs are directed to node j with probability $p_{ij}$ and with probability $1-p_{ij}$ they are routed elsewhere. The number of the first batch to be directed to node j is geometrically distributed. The first moment and the variances of the splitting process are calculated by using the Wald’s equation respectively the Blackwell-Girshick equation. The squared coefficient of variation results by $SCV[\cdot ]=(E[\cdot ^2]/E[\cdot ]^2)-1$:

$$\begin{aligned} SCV[A_{ij}]=1+p_{ij}(SCV[D_i]-1). \end{aligned}$$

If the phases are inserted successively into each other a system of linear equations is formed whose solutions provide the squared coefficient of variation of the interarrival times of the batches. Characteristics like the average number of individual jobs in the system of the various queueing systems can be determined by the modified formula of Allen-Cunneen [1] and the correction factor of Krämer/Langenbach-Belz:

$$\begin{aligned} E[N_i]\,\approx \,E[Z_{\infty ,i}]+b_i\cdot E[Q]_{GI/GI/c}g_{KLB}(\uprho _i^*,SCV[I_i^*],SCV[S_i])+b_ic_i\uprho _i^*+h. \end{aligned}$$

4 Numerical Results

Due to the independence of the phases, the presented approaches can be arbitrarily combined, e.g. merging will be approximated by Kühn and flow by Whitt. The benchmark which was done in regard to [1] was used to evaluate the decomposition method using all possible combinations of the presented approximation approaches. The Fig. 1 shows the reference network. All in all, 16 cases were investigated in detail differing in the characteristics of the utilization, batch sizes, number of servers and $SCV[S_i]$.

Fig. 1

Reference model

Exemplarily, case 11 (benchmark: table 3, case 3) will be evaluated shortly. Table 1 presents the parameterization of the open queueing network. Table 2 summarizes the results and shows the relative errors. The relative error is the discrepancy between calculated approximate values by the decomposition method and the mean of the simulation results. The ratio of mean input batch size ($E[X_4]=6.048$) and batch size $b_4$ at node 4 explains the increased discrepancies. A similar phenomenon occurs at the node 2 ($E[X_2]=3>b_2$). These situations affects an overestimation of the $SCV[I_i^*]$ and at last of the approximate characteristics. The approximations of the input stream of Pujolle/Ai and Kühn are robust. In contrast Chylla’s approximation caused larger errors at node 2. The study of this case also clearly shows that Chylla’s approximation combined with the approximation of the departure stream based on Marshall does not work well if there exist large changes of batch size (node 3). The formation of the superposition of the arrival streams under the circumstances of larger batch size changes revealed weaknesses of the approximation from Kühn (node 4).

Table 1 Queueing network with $\uplambda _0=2$, $SCV[I_0]=1$, $b_0=1$, $E[S_1]=3.6$, $E[S_2]=0.45$, $E[S_3]=4.5$, $E[S_4]=4$, $E[S_5]=8.889$ and $E[S_6]=11.4$

Table 2 PA = Pujolle/Ai, W = Whitt, C = Chylla, K = Kühn. 1st position: Merging, 2nd position: flow

5 Conclusions

All approaches yield acceptable results being useful as pre-evaluation for optimization. Generally it has been shown that the approximation of the input streams from Pujolle/Ai and Kühn are robust. The approximate approach from Chylla on the other hand caused in cases of larger batch size changes high errors (cases 9–16, benchmark: tables 3 and 4). The approach of Kühn, who has a complex case distinction is more difficult to handle than the approach of Pujolle/Ai.

The two approaches of the approximation of the departure streams yield similar results which could be expected since the approaches provide similar approximations. An interesting phenomenon discovered in many cases is that if $b_i<E[X_i]$ and $SCV[S_i]\rightarrow 0$ the approach based on Marshall’s method works better than the approach from Pujolle/Ai and in case of $b_i>E[X_i]$ and $SCV[S_i]\rightarrow 0$ Pujolle/Ai’s approach provides better approximations than the approach of Marshall. In the application it is possible to make a case analysis for each node to approximate the departure streams to reduce the error of the decomposition method.