Chapter 5.5

Model with Batch Service and Threshold Control: M/GI$^{[\Theta,K]}$/1-S


(c) Tobias Hossfeld (Aug 2021)

This script and the figures are part of the following book. The book is to be cited whenever the script is used (copyright CC BY-SA 4.0):
Tran-Gia, P. & Hossfeld, T. (2021). Performance Modeling and Analysis of Communication Networks - A Lecture Note. Würzburg University Press. https://doi.org/10.25972/WUP-978-3-95826-153-2


We consider now a model with batch service and threshold control: M/GI$^{[\Theta,K]}$/1-S A work station processes a batch of jobs jointly (batch service). At most $K$ jobs can be processed during batch service. However, the work station is first activated if there are enough jobs available to be processed (threshold control). This threshold $\Theta$ when to activate the service controls the efficiency of the system as well as the wait and response time for jobs. For manufacturing systems, it may be more cost-efficient to run the machine for a minimum number $\Theta$ of jobs, while the processing capacity $K$ as well as the waiting space $S$ are limited. The system can still be analyzed using the embedded Markov chain technique.

Example: Definition of Parameters

Random Variable $\Gamma$

The random variable $\Gamma$ reflects the number of Poisson arrivals during the service time $B$. As defined in Chapter 3.3.3 "Poisson Arrivals during an Arbitrarily Distributed Interval", it is

$ \Gamma_{GF} (z) = \Phi_B \Big(\lambda (1 - z)\Big) $.

We compute the probability $\gamma(i)=P(\Gamma=i)$ by numerical integration:

$\gamma(i) = \int\limits_{0}^\infty P(\Gamma=i\,|\,B=\tau) {b(\tau) \;d\tau} = \int\limits_{0}^\infty \frac{(\lambda\tau)^i}{i!} e^{-\lambda\tau} b(\tau) \;d\tau $

Depending on the coefficient of variation $c_B$, we use different distributions for the service time $B$:

State Transition matrix $P = \{p_{ij}\}$

The state transition matrix is defined in Chapter 5.5.2 and implemented here.

Power Method

A simple implementation of the power method with the start condition $ X_0 $ and transition matrix $ P $. The accuracy of the power method is achieved by comparing the expected values with accuracy $ \epsilon = 1e-16 $.

We get the steady state probabilities $ X $ at the embedding times.

State Probabilities at Arbitrary Times

The power method returns the steady state probabilities at the embedding times. We are however interested in the state probabilities $x^*(i)$ at arbitrary times. Due to the PASTA property, it is $x^*(i)=x_A(i)$ for arriving customers.

We define the random variable $X^*_y(i) = P(X^*=i, Y=y)$ with $X^*$ reflecting the number of customers in the waiting queue at an arbitrary time, while $Y$ indicates if the server is active and serving a batch of customers ($Y=1$) or if the server is idle ($Y=0$). The steady state probabilities are then as follows.

$ x^*_0(i) = \frac{\sum_{j=0}^i x(j)}{\lambda E[B] + \sum_{k=0}^i (\Theta-i)x(k) } , \quad 0 \leq i \leq \Theta-1 \\ x^*_1(i) = \frac{\sum_{j=i+1}^{\min(K+i,S)} x(j)}{\lambda E[B] + \sum_{k=0}^i (\Theta-i)x(k) } , \quad 0 \leq i \leq S-1 \\ x^*_1(S) = 1 - \sum_{i=0}^{\Theta-1} x^*_0(i) - \sum_{i=0}^{S-1} x^*_1(i) $

Further system characteristics are obtained from the probabilities in vector $\vec{X}^{\ast}$. The blocking probability is

$ p_B = x^{\ast} (S) \;. $

The mean waiting time in the system is

$ E[W] = \frac{E[X^*]}{\lambda (1-p_B)} \quad \mbox{with}\quad\quad E[X^*] = \sum\limits_{k=0}^S k \cdot x^{\ast} (k) \;. $

In the implementation we have the following variables: