# 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.

## 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$:

• $c_B=0$: deterministic distribution
• $c_B=1$: exponential distribution
• otherwise: lognormal distribution

## 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:

• $x^*_0(i)$ : Pn0
• $x^*_1(i)$ : Pn1
• $x^*(i)$ : Pn