Asymptotic Estimates for Queueing Systems with Time-Varying Periodic Transition Rates

Abstract

We consider the $M_t/M_t/1$ queue, the multi-server queue ($M_t/M_t/c_t$), and queues with jumps of size one and two. Results are extensible to more general ergodic quasi-birth-death processes (QBDs) with time-varying periodic transition rates of period one. The estimates are asymptotic in the level of the process (the length of the queue). These asymptotic estimates highlight the connections between the asymptotic periodic distribution of a stable queue with time-varying rates and the same type of queue with constant rates. The estimates can also be used to approximate other performance measures such as the waiting time distribution. We illustrate the method with several examples.

1 Introduction

Systems with time-varying periodic rates are pervasive. They include telephone call centers, hospital emergency rooms, airports, any system which exhibits seasonal behavior whether natural or man-made, ambulances, police and fire service and many, many others. The recent paper by Schwarz, Selinka and Stolletz [7] provides both a useful survey of applications and a survey of methods for analyzing queueing systems with time-varying parameters.

In this paper, we consider the $M_t/M_t/1$ queue, the multi-server queue ($M_t/M_t/c_t$), and queues with jumps of size one and two. Results are extensible to more general ergodic quasi-birth-death processes (QBDs) with time-varying periodic transition rates of period one. The estimates are asymptotic in the level of the process (the length of the queue). These asymptotic estimates highlight the connections between the asymptotic periodic distribution of a stable queue with time-varying rates and the same type of queue with constant rates. The estimates can also be used to approximate other performance measures such as the waiting time distribution. We illustrate the method with several examples.

The basic approach is to solve for the generating function of the queueing system using the assumption that if the process is in its asymptotic periodic distribution at some time t, then the generating function at time t will equal the generating function at time $t+1$. That is, we assume the system is in the periodic analog of steady state. For more detail on when the asymptotic periodic distribution exists, see [5]. This will yield a function for the generating function in terms of an integral equation. We find the poles of this function to create our asymptotic estimates. The poles of the generating function depend only on the evolution of the system over the course of a single period.

For the single-server queue, these estimates take a particularly simple form. Let $\bar{\lambda }$ be the average arrival rate in a time period and $\bar{\mu }$ be the average departure rate. Then an asymptotic estimate for the probability that there are n in the queue at time t is given by $\pi _n(t)\approx f(t)\left( \frac{\bar{\lambda }}{\bar{\mu }}\right) ^n$. For constant rates, the formula is exact and $f(t)=\pi _0=1-\frac{\bar{\lambda }}{\bar{\mu }}$. In general, f(t) depends on $\pi _0(t)$. Given $\pi _0(t),$ f(t) can be easily computed for any stable periodic $M_t/M_t/1$ queue. Similar formulas can be developed using this approach for more complex quasi-birth-and-death processes.

In Sect. 2, we find the transient solution of the $M_t/M_t/1$ queue up to an integral equation. In Sect. 2.1, we find the generating function for the single-server queue with periodic rates and use that to find the asymptotic periodic distribution of the number in the system in terms of an integral equation. In Sect. 2.2, we obtain asymptotic estimates for the distribution of the number in the queue at time t within the period. Section 2.3 provides numerical examples for the single-server queue with time-varying transition rates. In Sect. 3 we find similar quantities for the multi-server queue with time-varying transition rates. In Sect. 4, we illustrate the method for another type of queue.

2 $M_t/M_t/1$ Queue Example

Consider a single-server queue with time-varying arrival and departure rates. Let $X_t$ represent the number in the queue at time t, and let $X_s=i$ give the length of the queue at some given initial time s. Define $p_{i,n}(t)=P\{X_t=n|X_s=i\}$.

We have the Chapman–Kolmogorov equations:

$$\begin{aligned} \dot{p}_{i,0}(t)= & {} -\lambda (t) p_{i,0}(t)+\mu (t) p_{i,1}(t)\\ \dot{p}_{i,n}(t)= & {} \lambda (t) p_{i,n-1}(t)-(\lambda (t)+\mu (t))p_{i,n}(t)+\mu (t) p_{i,n+1}(t), \end{aligned}$$

with $p_{i,n}(s)=\delta _{i=n}$ for some initial time s. We define the generating function $P(z,s,t)=\sum _{n=0}^\infty z^n p_{i,n}(t)$, then P(z, s, t) satisfies the ordinary differential equation:

$$\begin{aligned} \dot{P}(z,s,t)=(\lambda (t)(z-1)+\mu (t)(z^{-1}-1))P(z,s,t) +(\mu (t)-z^{-1}\mu (t))p_{i,0}(t). \end{aligned}$$

This has solution

$$ P(z,s,t)=\int _s^t\mu (u)(1-z^{-1})p_{i,0}(u)\varPhi (z,u,t)du +P(z,s,s)\varPhi _Y(z,s,t), $$

where $\varPhi (z,u,t)$ is defined below. Note that since $p_{i,n}(s)=\delta _{i=n}$, $P(z,s,s)=z^i.$

We define the randomized random walk, $Y_t$ with jumps to the left occurring at rate $\mu (t)$ and to the right at rate $\lambda (t)$. Let

$$\begin{aligned} M(s,t)=\int _s^t\mu (u)du \end{aligned}$$

and

$$\begin{aligned} \varLambda (s,t)=\int _s^t\lambda (u)du, \end{aligned}$$

then

$$P\{Y_t=n+k|Y_s=k\}=e^{-(M(s,t)+\varLambda (s,t))}\left( \frac{\varLambda (s,t)}{M(s,t)}\right) ^{n/2} I_n(2\sqrt{\varLambda (s,t)M(s,t)}), $$

where $I_n(\cdot )$ is the modified Bessel function of the first kind. We denote the generating function for $Y_t$ as $\varPhi _Y(z,s,t)$ with

$$\begin{aligned} \varPhi _Y(z,s,t)=\sum _{n=-\infty }^\infty P\{Y_t=n+i|Y_s=i\}z^n=e^{\varLambda (s,t)(z-1)+M(s,t)(z^{-1}-1)}. \end{aligned}$$

Furthermore, we define

$$\begin{aligned} \phi _n(s,t)=P\{Y_t=n+i|Y_s=i\}. \end{aligned}$$

Note that $\phi _n(s,t)$ does not depend on i, the location of the random walk at time s.

$\varPhi _Y(z,s,t)$ is the solution of the evolution equation:

$$\begin{aligned} \frac{\partial }{\partial t}\varPhi _Y(z,s,t)=\varPhi _Y(z,s,t)\left( \lambda (t)(z-1)+\mu (t)(z^{-1}-1)\right) \end{aligned}$$

and

$$\begin{aligned} \varPhi (z,s,s)=\mathbf{I}. \end{aligned}$$

We will use the notation $[z^n](A(z))$ to represent the coefficient $a_n$ of $z^n$ in the series $A(z)=\sum _n a_n z^n$ (see Flajolet and Sedgewick [1]). The transient solution for the single-server queue with time-varying transition rates is then given by

$$\begin{aligned} p_{i,n}(t)=[z^n]P(z,s,t)=\int _s^t p_{i,0}(u)\mu (u)(\phi _n(u,t)-\phi _{n+1}(u,t))du+\phi _{n-i}(s,t). \end{aligned}$$

To find $p_{i,0}(u)$, we solve the Volterra equation

$$\begin{aligned} p_{i,0}(t)=[z^0]P(z,s,t)=\int _s^t p_{i,0}(u)\mu (u)(\phi _0(u,t)-\phi _{1}(u,t))du+\phi _{-i}(s,t). \end{aligned}$$

2.1 Periodic

Now suppose transition rates are periodic with period one. In this case, we use $\pi _n(t)$ to designate the asymptotic periodic probability of n in the queue at time t rather than $p_{i,n}(t)$ for the transient probability. We wish to solve directly for the asymptotic periodic solution. In that case, $P(z,t-1,t)=P(z,t-1,t-1)$, so

$$\begin{aligned} P(z,t-1,t)=\int _{t-1}^t {\pi }_0(u)\mu (u)(1-z^{-1})\varPhi _Y(z,u,t)du\left( 1-\varPhi (z,t-1,t)\right) ^{-1} \end{aligned}$$

(14.1)

Now,

$$\begin{aligned} \left( I-\varPhi (z,t-1,t)\right) ^{-1}=\sum _{k=0}^\infty \varPhi (z,t-1,t)^k=\sum _{k=0}^\infty \varPhi (z,t,t+k), \end{aligned}$$

and

$$\begin{aligned} \varPhi (z,u,t)\varPhi (z,t,t+k)=\varPhi (z,u,t+k), \end{aligned}$$

so

$$ \pi _n(t)=[z^n]P(z,t-1,t)=\int _{t-1}^t {\pi }_0(u)\mu (u) \sum _{k=0}^\infty \left( \phi _n(u,t+k)-\phi _{n+1}(u,t+k)\right) du. $$

Although we have an explicit formula for $\phi _n(u,t+k)=P\{Y(u,t+k)=n\}$, computation of these quantities is very cumbersome and in general convergence is slow.

In the next section, we describe asymptotic methods for approximating these infinite sums.

2.2 Asymptotic Methods

Define $\bar{\lambda }=\varLambda (0,1)=\int _{t-1}^t\lambda (u)du$ and $\bar{\mu }=M(0,1)=\int _{t-1}^t\mu (u)du$. These represent the expected number of steps to the right ($\bar{\lambda }$) or to the left ($\bar{\mu }$) during one period for the random walk $Y_t$. We have zeros in the denominator of equation (14.1), where

$$\begin{aligned} \bar{\lambda }(z-1)+\bar{\mu }(z^{-1}-1)=0. \end{aligned}$$

This expression has two zeros: $z=1$, and $z=\bar{\mu }/\bar{\lambda }$. $z=1$ is a root of both the numerator and the denominator, so we factor it out:

$$\begin{aligned} P(z,t-1,t)=\int _{t-1}^t {\pi }_0(u)\frac{\mu (u)}{\bar{\mu }-\bar{\lambda }z}\varPhi _{Y}&(z,u,t)du \\&\times \left( \sum _{k=1}^\infty \frac{(\bar{\lambda }(z-1)+\bar{\mu }(z^{-1}-1))^{k-1}}{k!}\right) ^{-1}. \end{aligned}$$

We can rewrite this as

$$\begin{aligned} P(z,t-1,t)=\sum _{j=0}^\infty \left( \frac{\bar{\lambda }}{\bar{\mu }}\right) ^j\int _{t-1}^{t}&{\pi }_{0}(u)\frac{\mu (u)}{\bar{\mu }}\varPhi _Y(z,u,t)du z^j\nonumber \\&\times \left( \sum _{k=1}^\infty \frac{(\bar{\lambda }(z-1)+\bar{\mu }(z^{-1}-1))^{k-1}}{k!}\right) ^{-1}. \end{aligned}$$

(14.2)

This is suggestive of the relation between the asymptotic periodic solution for the queue with time-varying parameters and the steady-state solution for the constant rate queue which is given by

$$\begin{aligned} \pi _j=\pi _0\left( \frac{\lambda }{\mu }\right) ^j=\left( 1-\frac{\lambda }{\mu }\right) \left( \frac{\lambda }{\mu }\right) ^j. \end{aligned}$$

To obtain the asymptotic estimate, we use the following result (see [1, p. 228, IV.2]):

$$\begin{aligned}{}[z^n]\frac{h(z)}{(1-z)}\sim h(1). \end{aligned}$$

So

$$\begin{aligned}{}[z^n]\frac{h(z)}{\left( 1-\frac{\bar{\lambda }}{\bar{\mu }}z\right) }\sim h\left( \frac{\bar{\mu }}{\bar{\lambda }}\right) . \end{aligned}$$

Hence an asymptotic estimate is given by

$$\begin{aligned} \nonumber \pi _n(t)&\approx \frac{1}{\bar{\mu }}\int _{t-1}^t \pi _0(u)\mu (u)\varPhi _Y\!\left( \frac{\bar{\mu }}{\bar{\lambda }},u,t\right) du\left( \frac{\bar{\lambda }}{\bar{\mu }}\right) ^n\\&=\frac{1}{\bar{\mu }}\int _{t-1}^t \pi _0(u)\mu (u)\exp \!\left\{ \left( \frac{\varLambda (u,t)}{\bar{\lambda }}-\frac{M(u,t)}{\bar{\mu }}\right) (\bar{\mu }-\bar{\lambda })\right\} du \left( \frac{\bar{\lambda }}{\bar{\mu }}\right) ^n. \end{aligned}$$

(14.3)

We have shown that

$$\begin{aligned} \pi _n(t)\sim \left( \frac{\bar{\lambda }}{\bar{\mu }}\right) ^nf(t), \end{aligned}$$

where

$$\begin{aligned} f(t)=\frac{1}{\bar{\mu }}\int _{t-1}^t \pi _0(u)\mu (u)\exp \!\left\{ \left( \frac{\varLambda (u,t)}{\bar{\lambda }}-\frac{M(u,t)}{\bar{\mu }}\right) (\bar{\mu }-\bar{\lambda })\right\} du. \end{aligned}$$

(14.4)

Note that, if $\mu (t)=\bar{\mu }$ and $\lambda (t)=\bar{\lambda }$, the expression simplifies to

$$\begin{aligned} \pi _n=\pi _0\left( \frac{\lambda }{\mu }\right) ^n=\left( 1-\frac{\lambda }{\mu }\right) \left( \frac{\lambda }{\mu }\right) ^n. \end{aligned}$$

If we let $\alpha (z)=\bar{\lambda }(z-1)+\bar{\mu }(z^{-1}-1)$, then we obtain

$$\left( \sum _{k=1}^\infty \frac{(\bar{\lambda }(z-1) +\bar{\mu }(z^{-1}-1))^{k-1}}{k!}\right) ^{-1} =\frac{\alpha (z)}{1-e^{\alpha (z)}}.$$

This has Maclaurin series in $\alpha$ of

$$\frac{\alpha }{1-e^{\alpha }} =1-\frac{\alpha }{2}+\frac{\alpha ^2}{12} -\frac{\alpha ^4}{720}+\frac{\alpha ^6}{30240} +\cdots =\sum _{n=0}^\infty \frac{B_{n}}{n!}\alpha ^{n},$$

where the $B_n$’s are the Bernoulli numbers. See, for example, [6, p. 289]. Additional terms of an asymptotic expansion for the number in queue may be obtained using this expansion, since as $z\rightarrow \bar{\mu }/\bar{\lambda }$, $\alpha \rightarrow 0$. In what follows, we will use the asymptotic estimate given in Eq. (14.3).

2.3 Numerical Examples for the $M_t/M_t/1$ Queue

We consider several numerical examples:

Examples	1	2	3
Arrival rate $\lambda (t)$	$3-2\cos (2\pi t)$	$0.3-0.2\cos (2\pi t)$	$3-2\cos (2\pi t)$
Departure rate $\mu (t)$	$4+2\cos (2\pi t)$	$0.4+0.2\cos (2\pi t)$	$4 - 2\cos (2\pi t)$
$\bar{\lambda }$	3	0.3	3
$\bar{\mu }$	4	0.4	4
$\rho =\frac{\bar{\lambda }}{\bar{\mu }}$	0.75	0.75	0.75

Examples	4	5	6
Arrival rate $\lambda (t)$	$3.6-2.8\cos (2\pi t)$	$0.36-0.28\cos (2\pi t)$	$0.4-0.3\cos (2\pi t)$
Departure rate $\mu (t)$	$4+2\cos (2\pi t)$	$0.4+0.2\cos (2\pi t)$	$4 - 2\cos (2\pi t)$
$\bar{\lambda }$	3.6	0.36	0.4
$\bar{\mu }$	4	0.4	4
$\rho =\frac{\bar{\lambda }}{\bar{\mu }}$	0.9	0.9	0.1

These examples collectively illustrate the convergence behavior toward theasymptotic estimates for the probabilities of the number in queue for three different traffic intensities: $\rho =0.75$ (examples 1–3), $\rho =0.9$ (examples 4–5), and $\rho =0.1$ (example 6); for different rates and for arrival and service intensities that move together or do not. For each of the examples, the convergence to the asymptotic estimate is fairly rapid. The behavior of periodic probabilities for some sets of parameters is close to the constant rate steady state probabilities, but for other examples (those with greater rates), the probabilities show greater variability within the period (Fig. 1).

For each of these six examples, we provide two graphs. One shows the asymptotic periodic probabilities of having j in the queue for $j=$ 0–5 (solid lines) compared to the asymptotic estimate of the probability shown as dashed lines. The second graph shows the estimate for the function f(t) used in the asymptotic estimates for each of probabilities zero to five compared to the exact f(t), where f(t) is given in Eq. (14.4). As the number in the queue increases, it can be seen that the quality of the asymptotic estimate improves (Fig. 2).

Fig. 1

Example 1. The graph on the left shows $\pi _j(t)$, $j=0,\dots ,5$ (solid lines) and the asymptotic estimates for each of these probabilities (dashed lines). The graph on the right shows $\pi _j(t)\left( \frac{\bar{\mu }}{\bar{\lambda }}\right) ^j$, $j=0,\dots ,5$ and the asymptotic estimate for $f(t)=\pi _j(t)\left( \frac{\bar{\mu }}{\bar{\lambda }}\right) ^j$ which does not depend on j

Fig. 2

Example 2. The graph on the left shows $\pi _j(t)$, $j=0,\dots ,5$ (solid lines) and the asymptotic estimates for each of these probabilities (dashed lines). The graph on the right shows $\pi _j(t)\left( \frac{\bar{\mu }}{\bar{\lambda }}\right) ^j$, $j=0,\dots ,5$ and the asymptotic estimate for $f(t)=\pi _j(t)\left( \frac{\bar{\mu }}{\bar{\lambda }}\right) ^j$ which does not depend on j

Fig. 3

Example 3. The graph on the left shows $\pi _j(t)$, $j=0,\dots ,5$ (solid lines) and the asymptotic estimates for each of these probabilities (dashed lines). The graph on the right shows $\pi _j(t)\left( \frac{\bar{\mu }}{\bar{\lambda }}\right) ^j$, $j=0,\dots ,5$ and the asymptotic estimate for $f(t)=\pi _j(t)\left( \frac{\bar{\mu }}{\bar{\lambda }}\right) ^j$ which does not depend on j

3 Example: Multi-server Queue

Next, we consider the multi-server queue with time-varying periodic rates and c servers. The analysis parallels the analysis for the single-server queue (Fig. 3).

We have the Chapman–Kolmogorov equations

$$\begin{aligned} \dot{p}_{i,0}(t)&=-\lambda (t) p_{i,0}(t)+\mu (t) p_{i,1}(t)\\ \dot{p}_{i,1}(t)&=\lambda (t) p_{i,0}(t)-(\lambda (t)+\mu (t)) p_{i,1}(t)+2\mu (t)p_{i,2}(t)\\&\,\,\vdots \\ \dot{p}_{i,j}(t)&=\lambda (t) p_{i,j-1}(t)-(\lambda (t)+j\mu (t)) p_{i,j}(t)+(j+1)\mu (t)p_{i,j+1}(t),\;\;0<j< c\\&\,\,\vdots \\ \dot{p}_{i,c-1}(t)&=\lambda (t) p_{i,c-2}(t)-(\lambda (t)+(c-1)\mu (t)) p_{i,c-1}(t)+c\mu (t)p_{i,c}(t)\\ \dot{p}_{i,n}(t)&=\lambda (t) p_{i,n-1}(t)-(\lambda (t)+c\mu (t))p_{i,n}(t)+c\mu (t) p_{i,n+1}(t),\;\;n\ge c. \end{aligned}$$

We define the generating function $P(z,s,t)=\sum _{n=0}^\infty z^n p_{i,n}(t)$. The function P(z, s, t) satisfies the ordinary differential equation

$$\begin{aligned} \dot{P}(z,s,t)=\lambda (t)\sum _{n=0}^\infty&p_{i,n}(t)(z^{n+1}-z^n)\\&-\mu (t)\sum _{n=0}^{c-1} n p_{i,n}(t)z^n -c\mu (t)\sum _{n=c}^\infty p_{i,n}(t)z^n\\&\qquad \qquad \quad +\mu (t)\sum _{n=0}^{c-1} n p_{i,n}(t)z^{n-1} +c\mu (t)\sum _{n=c}^\infty p_{i,n}(t)z^{n-1} \end{aligned}$$

In line 1 on the right-hand side of the preceding equation, we replace the infinite sum with the generating function for the number in queue. In lines 2 and 3, we add and subtract like quantities so that we can rewrite the expressions in terms of the generating function for the number in queue:

$$\begin{aligned} \dot{P}(z,s,t)=\lambda (t)&(z-1)P(z,s,t) \\&+\mu (t)\sum _{n=0}^{c-1}(c- n) p_{i,n}(t)z^n -c\mu (t)\sum _{n=0}^\infty p_{i,n}(t)z^n\\&\qquad \quad +\mu (t)\sum _{n=0}^{c-1} (n-c)p_{i,n}(t)z^{n-1} +c\mu (t)\sum _{n=0}^\infty p_{i,n}(t)z^{n-1}. \end{aligned}$$

We replace the series in lines 2 and 3 of the right-hand side of the previous equation with the generating function for the number in queue:

$$\begin{aligned} \dot{P}(z,s,t)=\left( \lambda (t)(z-1)+c\mu (t)(z^{-1}-1)\right)&P(z,s,t) \\&+\mu (t)\sum _{n=0}^{c-1}(c- n)z^n(1-z^{-1})p_{i,n}(t). \end{aligned}$$

This differential equation has solution

$$\begin{aligned} P(z,s,t)=\int _s^t\mu (u)\sum _{n=0}^{c-1}(c- n)z^n(1-z^{-1})p_{i,n}(u)\varPhi _Y(z,u,t)&du\\&+P(z,s,s)\varPhi _Y(z,s,t), \end{aligned}$$

where we denote the generating function for $Y_t$ as $\varPhi _Y(z,s,t)$ and

$$\begin{aligned} \varPhi _Y(z,s,t)=\sum _{n=-\infty }^\infty P\{Y_t=n\}z^n=e^{\varLambda (s,t)(z-1)+cM(s,t)(z^{-1}-1)}. \end{aligned}$$

$\varPhi _Y(z,s,t)$ is the solution of the evolution equation

$$\begin{aligned} \frac{\partial }{\partial t}\varPhi _Y(z,s,t)=\varPhi _Y(z,s,t)\left( \lambda (t)(z-1)+c\mu (t)(z^{-1}-1)\right) \end{aligned}$$

and

$$\begin{aligned} \varPhi (z,s,s)=\mathbf{I}. \end{aligned}$$

The transient distribution for number in queue is given by

$$\begin{aligned} p_{i,j}(s,t)&=[z^j]P(z,s,t)\\&=\int _s^t\mu (u)\sum _{n=0}^{c-1}(c- n)p_{i,n}(s,u)\left( \phi _{j-n}(u,t)-\phi _{j-n+1}(u,t)\right) du\\&\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \quad +\phi _{j-i}(s,t). \end{aligned}$$

Let

$$\begin{aligned} \mathbf{p}_i(s,t)=\left[ \begin{array}{cccc}p_{i,0}(s,t)&p_{i,1}(s,t)&\cdots&p_{i,c-1}(s,t)\end{array}\right] \end{aligned}$$

and

$$ {\varvec{\phi }}_i(s,t)= \left[ \begin{array}{cccc}\phi _{-i}(s,t)&\phi _{-i+1}(s,t)&\cdots&\phi _{-i+c-1}(s,t)\end{array}\right] .$$

Define the matrix function $\mathbf{K}(s,t)$

$$\begin{aligned} \mathbf{K}(s,t)=\left[ \begin{array}{cccc}{} \mathbf{k}_{0}(s,t)&\mathbf{k}_{1}(s,t)&\dots&\mathbf{k}_{c-1}(s,t)\end{array}\right] , \end{aligned}$$

where $\mathbf{k}_j(u,t)$ is the column vector

$$\mathbf{k}_j(u,t)=\mu (s)\left[ \begin{array}{c} c(\phi _{j}(s,t)-\phi _{j+1}(s,t))\\ (c-1)(\phi _{j-1}(s,t)-\phi _{j}(s,t))\\ \vdots \\ 2(\phi _{j-c+2}(s,t)-\phi _{j-c+3}(s,t))\\ (\phi _{j-c+1}(s,t)-\phi _{j-c+2}(s,t)) \end{array}\right] .$$

Then

$$\begin{aligned} \mathbf{p}_i(s,t)=\int _s^t \mathbf{p}_i(s,u)\mathbf{K}(u,t)du+ {{\varvec{\phi }}}_i(s,t), \end{aligned}$$

and

$$\begin{aligned} p_{i,j}(s,t)=\int _s^t\mathbf{p}_i(s,u)\mathbf{k}_{j}(u,t) du+\phi _{j-i}(s,t). \end{aligned}$$

To compute these transient probabilities, we discretize each component of the matrix function $\mathbf{K}(s,t)$ so that we have a matrix of matrices. Let m be the mesh size, then we weight each component matrix by $\frac{1}{m}$.

In the case where transition rates are periodic only the first m rows of each component matrix need be computed. Subsequent blocks of m rows are equal to preceding blocks shifted m columns to the right. We also weight the diagonal and the top row of each component matrix by $\frac{1}{2}$. These weights allow us to use matrix multiplication to apply the trapezoidal rule of numerical integration to solve for the transient probabilities (Fig. 4).

Fig. 4

Example 4. The graph on the left shows $\pi _j(t)$, $j=0,\dots ,5$ (solid lines) and the asymptotic estimates for each of these probabilities (dashed lines). The graph on the right shows $\pi _j(t)\left( \frac{\bar{\mu }}{\bar{\lambda }}\right) ^j$, $j=0,\dots ,5$ and the asymptotic estimate for $f(t)=\pi _j(t)\left( \frac{\bar{\mu }}{\bar{\lambda }}\right) ^j$ which does not depend on j

3.1 Periodic

Now suppose transition rates are periodic with period one. In this case, we use $\pi _n(t)$ to designate the asymptotic periodic probability of n in the queue at time t rather than $p_{i,n}(t)$ for the transient probability. We wish to solve directly for the asymptotic periodic solution. In that case, $P(z,t-1,t)=P(z,t-1,t-1)$, so

$$\begin{aligned}&P(z,t-1,t)\nonumber \\&\qquad =\int _{t-1}^t \mu (u)\sum _{n=0}^{c-1}(c- n)z^n(1-z^{-1})\pi _n(u)\varPhi _Y(z,u,t)du\left( \!1-\varPhi (z,t-1,t)\!\right) ^{-1}. \end{aligned}$$

(14.5)

The coefficient on $z^j$ gives us the following integral formula for the periodic probability, $\pi _j(t)$, of j in the queue at time t within the period:

$$\begin{aligned} \pi _j(t)=&[z^j]P(z,t-1,t)\\&=\int _{t-1}^t \mu (u)\sum _{n=0}^{c-1}(c- n) \pi _n(u) \sum _{k=0}^\infty \left( \phi _{j-n}(u,t+k)-\phi _{j-n+1}(u,t+k)\right) du. \end{aligned}$$

We have zeros in the denominator of equation (14.5), where

$$\begin{aligned} \bar{\lambda }(z-1)+c\bar{\mu }(z^{-1}-1)=0. \end{aligned}$$

This expression has two zeros: $z=1$, and $z=c\bar{\mu }/\bar{\lambda }$. The value $z=1$ is a root of both the numerator and the denominator, so we factor it out:

$$\begin{aligned} P(z,t-1,t)= \int _{t-1}^t \sum _{n=0}^{c-1}(c- n)z^n\pi _n(u)&\frac{\mu (u)}{c\bar{\mu }-\bar{\lambda }z}\varPhi _Y(z,u,t)du\\ \times&\left( \sum _{k=1}^\infty \frac{(\bar{\lambda }(z-1)+c\bar{\mu }(z^{-1}-1))^{k-1}}{k!}\right) ^{-1}. \end{aligned}$$

We can rewrite this as

$$\begin{aligned} P(z,t-1,t)=&\int _{t-1}^t \sum _{n=0}^{c-1}(c- n)z^n\pi _n(u)\frac{\mu (u)}{c\bar{\mu }}\varPhi _Y(z,u,t)du\nonumber \\&\qquad \left( \sum _{k=1}^\infty \frac{(\bar{\lambda }(z-1)+c\bar{\mu }(z^{-1}-1))^{k-1}}{k!}\right) ^{-1} \sum _{j=0}^\infty \left( \frac{\bar{\lambda }}{c\bar{\mu }}\right) ^j z^j. \end{aligned}$$

(14.6)

An asymptotic estimate is then given by

$$\begin{aligned}&\pi _j(t)\approx \int _{t-1}^t \frac{\mu (u)}{c\bar{\mu }} \varPhi _Y\left( \frac{c\bar{\mu }}{\bar{\lambda }},u,t\right) \sum _{n=0}^{c-1}(c- n)\pi _n(u)du \left( \frac{\bar{\lambda }}{c\bar{\mu }}\right) ^{j-n}\nonumber \\ =&\int _{t-1}^t \frac{\mu (u)}{c\bar{\mu }} \exp \!\left\{ \left( \frac{\varLambda (u,t)}{\bar{\lambda }}-\frac{M(u,t)}{\bar{\mu }}\right) (c\bar{\mu }-\bar{\lambda })\right\} \sum _{n=0}^{c-1}(c- n)\pi _n(u)\left( \frac{\bar{\lambda }}{c\bar{\mu }}\right) ^{j-n}du. \end{aligned}$$

(14.7)

We may estimate $\pi _j(t)$ as

$$\begin{aligned} \pi _j(t)\approx f(t)\left( \frac{\bar{\lambda }}{c\bar{\mu }}\right) ^j, \end{aligned}$$

where

$$ f(t)=\int _{t-1}^t \frac{\mu (u)}{c\bar{\mu }} \exp \!\left\{ \left( \frac{\varLambda (u,t)}{\bar{\lambda }}-\frac{M(u,t)}{\bar{\mu }}\right) (c\bar{\mu }-\bar{\lambda })\right\} \sum _{n=0}^{c-1}(c- n)\pi _n(u)\left( \frac{c\bar{\mu }}{\bar{\lambda }}\right) ^n du. $$

The resulting expression for f(t) in the multi-server case is analogous to that in the single-server case in Eq. (14.4). For a c server queue, the expression depends on the first c periodic probabilities for number in queue. The expression reduces to the single-server expression when $c=1$. The queue length probabilities are asymptotically geometric with rate $\frac{\bar{\lambda }}{c\bar{\mu }}$.

4 Example: The Queue with Transitions of Size One and Two

For this queueing system, the classical single-server queueing system, M / M / 1 is generalized to allow transition rates of size two in addition to the standard transition rates of size one (Fig. 5).

In terms of the queueing models, these systems each allow customers to arrive or be served instantly in pairs as well as individually (Fig. 6).

Krinik and Shun [2] have derived the steady-state distributions explicitly and determined a condition for the existence of a steady-state distribution. Assuming that a steady-state condition prevails, they determined the canonical performance measures, including expressions for the average number of customers in either system or queue. They also derived formulae for the average waiting time that a customer spends in the system or queue.

Fig. 5

Example 5. The graph on the left shows $\pi _j(t)$, $j=0,\dots ,5$ (solid lines) and the asymptotic estimates for each of these probabilities (dashed lines). The graph on the right shows $\pi _j(t)\left( \frac{\bar{\mu }}{\bar{\lambda }}\right) ^j$, $j=0,\dots ,5$ and the asymptotic estimate for $f(t)=\pi _j(t)\left( \frac{\bar{\mu }}{\bar{\lambda }}\right) ^j$ which does not depend on j

Fig. 6

Example 6. The graph on the left shows $\pi _j(t)$, $j=0,\dots ,5$ (solid lines) and the asymptotic estimates for each of these probabilities (dashed lines). The graph on the right shows $\pi _j(t)\left( \frac{\bar{\mu }}{\bar{\lambda }}\right) ^j$, $j=0,\dots ,5$ and the asymptotic estimate for $f(t)=\pi _j(t)\left( \frac{\bar{\mu }}{\bar{\lambda }}\right) ^j$ which does not depend on j

In this example, we generalize their model to allow transition rates to vary periodically with period of length one.

We have the Chapman–Kolmogorov equations with $\beta (t)$ and $\gamma (t)$ giving the rates at which transitions of size two occur:

$$\begin{aligned} \dot{p}_{i,0}(t)= & {} -(\lambda (t)+\beta (t))p_{i,0}(t)+\mu (t) p_{i,1}(t)+\gamma (t) p_{i,2}(t)\\ \dot{p}_{i,1}(t)= & {} \lambda (t) p_{i,0}(t)-(\lambda (t)+\beta (t)+\mu (t))p_{i,1}(t)+\mu (t) p_{i,2}(t)+\gamma (t) p_{i,3}(t)\\ \dot{p}_{i,n}(t)= & {} \beta (t) p_{i,n-2}(t)+\lambda (t) p_{i,n-1}(t)\\&-(\lambda (t)+\beta (t)+\mu (t)+\gamma (t))p_{i,n}(t)+\mu (t) p_{i,n+1}(t)+\gamma (t) p_{i,n+2}(t). \end{aligned}$$

We define the generating function $P(z,t)=\sum _{n=0}^\infty z^n p_{i,n}(t)$. Then we have

$$\begin{aligned} \dot{P}(z,t)=&(z^2\beta (t)+z\lambda (t)-(\lambda (t)+\beta (t)+\mu (t)+\gamma (t))+z^{-1}\mu (t)+z^{-2}\gamma (t))P(z,t)\\&\qquad +\gamma (t)(z-z^{-1})p_{i,1}(t)+(\gamma (t)+\mu (t)-z^{-1}\mu (t)-\gamma (t) z^{-2})p_{i,0}(t). \end{aligned}$$

This has solution

$$\begin{aligned}&P(z,s,t)=\int _0^t\left( \gamma (t)(z-z^{-1})p_{i,1}(u)+(\gamma (t)(1-z^{-2})+\mu (t)(1-z^{-1}) )p_{i,0}(u)\right) \nonumber \\&\qquad \qquad \qquad \qquad \qquad \qquad \qquad \times \varPhi (z,u,t)du +P(z,s,s)\varPhi (z,s,t), \end{aligned}$$

(14.8)

where

$$\begin{aligned} \varPhi (z,s,t)&=\exp \left\{ \int _s^t(z^2\beta (u)+z\lambda (u)\right. \\&\qquad \qquad \quad \left. -(\lambda (u)+\beta (u)+\mu (u)+\gamma (u))+z^{-1}\mu (u)+z^{-2}\gamma (u))du\right\} \\&=\exp \left\{ \int _s^t(z\lambda (u)-(\lambda (u)+\mu (u))+z^{-1}\mu (u))du\right\} \\&\qquad \qquad \qquad \quad \times \exp \left\{ \int _s^t(z^2\beta (u)-(\beta (u)+\gamma (u))+z^{-2}\gamma (u))du\right\} \\&=\varPhi _Y(z,s,t)\varPhi _X(z^2,s,t), \end{aligned}$$

and $X_t$ and $Y_t$ are the randomized random walks. For the walk $X_t$ steps to the right occur at rate $\beta (t)$ and to the left at rate $\gamma (t)$. For the walk $Y_t$ steps to the right occur at rate $\lambda (t)$ and to the left at rate $\mu (t)$. $\varPhi _X(z,s,t)$ and $\varPhi _Y(z,s,t)$ are the generating functions for the randomized random walks $X_t$ and $Y_t$, respectively. Expanding the generating function in terms of coefficients on $z^n$, we have

$$\begin{aligned} \varPhi (z,s,t)&=\sum _{n=-\infty }^\infty z^n\phi _n(s,t)\\&=\sum _{n=-\infty }^\infty z^n\sum _{j=-\infty }^\infty P\{X_t=j|X_s=0\}P\{Y_t=n-2j|Y_s=0\}. \end{aligned}$$

Assume that $p_{i,j}(s)=\delta _{j=i}$. Matching coefficients on $z_n$, we see that

$$\begin{aligned} p_{i,0}(t)&=\int _s^t\left( p_{i,1}(u)\gamma (u)\left( \phi _{-1}(u,t)-\phi _{1}(u,t)\right) \right. \\&\left. +p_{i,0}(u)\left( (\gamma (u)+\mu (u))\phi _0(u,t)-\mu (u)\phi _{1}(u,t)-\gamma (u) \phi _{2}(u,t)\right) \right) du\\&\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad +\phi _{-i}(s,t)\\ p_{i,1}(t)&=\int _s^t\left( p_{i,1}(u)\gamma (u)\left( \phi _{0}(u,t)-\phi _{2}(u,t)\right) \right. \\&\left. +p_{i,0}(u)\left( (\gamma (u)+\mu (u))\phi _1(u,t)-\mu (u)\phi _{2}(u,t)-\gamma (u) \phi _{3}(u,t)\right) \right) du\\&\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad +\phi _{-i+1}(s,t), \end{aligned}$$

and more generally

$$\begin{aligned} p_{i,n}(t)=&\int _s^t \left[ p_{i,1}(u)\gamma (u)\left( \phi _{i,n-1}(u,t)-\phi _{i,n+1}(u,t)\right) \right. \\&\left. +p_{i,0}(u)\left( (\gamma (u)+\mu (u))\phi _n(u,t)-\phi _{n+1}(u,t)\mu -\gamma \phi _{n+2}(u,t)\right) \right] du\\&\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \quad +\phi _{-i+n}(s,t). \end{aligned}$$

Now suppose that transition rates are time-varying and periodic. Further suppose that our generating function is for the asymptotic periodic distribution of the number in the system. Then we have the generating function

$$\begin{aligned} P(z,t-1,t)&= \int _{t-1}^t\left( \pi _1(u)\gamma (u)(z-z^{-1})\right. \nonumber \\&\left. +\pi _0(u)(\gamma (u)(1-z^{-2})+\mu (u)(1-z^{-1}) )\right) \varPhi (z,u,t)du\nonumber \\&\qquad \qquad \qquad \qquad \qquad \qquad \times (1-\varPhi (z,t-1,t))^{-1} \end{aligned}$$

(14.9)

and

$$\begin{aligned} \pi _0(t)&=\int _0^t\left[ \pi _1(u)\gamma (u)\sum _{k=0}^\infty \left( \phi _{-1}(u,t+k)-\phi _{1}(u,t+k)\right) \right. \\&\qquad \qquad \quad +\pi _0(u)\left( (\gamma (u)+\mu (u))\sum _{k=0}^\infty \phi _0(u,t+k)\right. \\&\qquad \qquad \qquad \quad \quad \quad \left. \left. -\sum _{k=0}^\infty \phi _{1}(u,t+k)\mu (u)-\gamma (u) \sum _{k=0}^\infty \phi _{2}(u,t+k)\right) \right] du,\\ \pi _1(t)&=\int _0^t\left[ \pi _1(u)\gamma (u)\sum _{k=0}^\infty \left( \phi _{0}(u,t+k)-\phi _{2}(u,t+k)\right) \right. \\&\qquad \qquad \quad +\pi _0(u)\left( (\gamma (u)+\mu (u))\sum _{k=0}^\infty \phi _1(u,t+k)\right. \\&\qquad \qquad \qquad \quad \quad \quad \left. \left. -\mu (u)\sum _{k=0}^\infty \phi _{2}(u,t+k)-\gamma (u) \sum _{k=0}^\infty \phi _{3}(u,t+k)\right) \right] du, \end{aligned}$$

and more generally

$$\begin{aligned} \pi _n(t)=&\int _0^t\left[ \pi _1(u)\gamma (u)\sum _{k=0}^\infty \left( \phi _{n-1}(u,t+k)-\sum _{k=0}^\infty \phi _{n+1}(u,t+k)\right) \right. \\&\qquad \qquad \quad +\pi _0(u)\left( (\gamma (u)+\mu (u))\sum _{k=0}^\infty \phi _n(u,t+k)\right. \\&\qquad \qquad \qquad \quad \left. \left. -\sum _{k=0}^\infty \phi _{n+1}(u,t+k)\mu (u)-\gamma (u) \sum _{k=0}^\infty \phi _{n+2}(u,t+k)\right) \right] du. \end{aligned}$$

These expressions are difficult to evaluate numerically. So as in the $M_t/M_t/1$ example, we apply an asymptotic estimate of the transition probabilities.

The first step is to factor out $z-1$ since one is a root of both the numerator and the denominator. Second, we follow Krinik and Shun and find the roots of the denominator. Then following the approach outlined by Sedgewick and Flajolet [1], we approximate the integrand as a sum of geometric series. We will need to do a partial fractions decomposition.

Factorization of the numerator of Eq. (14.9) by $z-1$ yields

$$\begin{aligned} \int _{t-1}^t\left[ \gamma (u)(1+z^{-1})p_1(u)+(\gamma (u)(z^{-1}+z^{-2})+\mu (u)z^{-1})p_0(u)\right] \varPhi (z,u,t)du. \end{aligned}$$

The denominator is zero when $\varPhi (z,t-1,t)=1$, that is, when

$$\begin{aligned} \left( \bar{\beta }z^2+\bar{\lambda }z-(\bar{\beta }+\bar{\lambda }+\bar{\mu }+\bar{\gamma })+\bar{\mu }z^{-1}+\bar{\gamma }z^{-2}\right) =0. \end{aligned}$$

One root occurs at $z=1$:

$$\begin{aligned}&\left( \bar{\beta }z^2+\bar{\lambda }z-(\bar{\beta }+\bar{\lambda }+\bar{\mu }+\bar{\gamma })+\bar{\mu }z^{-1}+\bar{\gamma }z^{-2}\right) \\&\qquad \qquad \qquad \qquad \qquad \quad =(z-1)(\bar{\beta }z+\bar{\lambda }+\bar{\beta }-(\bar{\mu }+\bar{\gamma })z^{-1}-\bar{\gamma }z^{-2}). \end{aligned}$$

Factorization of the denominator of equation (14.9) by $z-1$ yields

$$\begin{aligned} (\bar{\beta }z+\bar{\lambda }+\bar{\beta }-(\bar{\mu }+\bar{\gamma })&z^{-1}-\bar{\gamma }z^{-2})\\&\times \sum _{k=1}^\infty \frac{\left( \bar{\beta }z^2+\bar{\lambda }z-(\bar{\beta }+\bar{\lambda }+\bar{\mu }+\bar{\gamma })+\bar{\mu }z^{-1}+\bar{\gamma }z^{-2}\right) ^{k-1}}{k!}. \end{aligned}$$

There are three other real roots of the denominator. These were computed by Krinik and Shun [2, Lemma 1.1]. Their reciprocals are given by

$$\begin{aligned} \frac{1}{r_1}=-\frac{a}{3}-&2\sqrt{U}\cos \left( \frac{\theta }{3}\right) ,\;\; \frac{1}{r_2}=-\frac{a}{3}-2\sqrt{U}\cos \left( \frac{\theta }{3}+\frac{4\pi }{3}\right) ,\\&\quad \frac{1}{r_3}=-\frac{a}{3}-2\sqrt{U}\cos \left( \frac{\theta }{3}+\frac{2\pi }{3}\right) , \end{aligned}$$

where $U=\frac{a^2-3b}{9}$, $V=\frac{2a^3-9ab+27c}{54}$, $\theta =\cos ^{-1}\left( \frac{V}{\sqrt{U^3}}\right)$, $a=\frac{\bar{\mu }+\bar{\gamma }}{\bar{\gamma }}$, $b=-\frac{\bar{\beta }+\bar{\gamma }}{\bar{\gamma }}$, $c=-\frac{\bar{\beta }}{\bar{\gamma }}$ and $\frac{1}{r_1}<-1<\frac{1}{r_2}<0<\frac{1}{r_3}$.

We are considering stable queues, so $r_1$ is also a root of the numerator. We apply a partial fractions decomposition to

$$\frac{1}{\left( 1-\frac{z}{r_2}\right) \left( 1-\frac{z}{r_3}\right) } =\frac{-r_3}{(r_2-r_3)\left( 1-\frac{z}{r_2}\right) }+\frac{r_2}{(r_2-r_3)\left( 1-\frac{z}{r_3}\right) }.$$

Define

$$\begin{aligned} H(z,t)=-z^2\int _{t-1}^t&\left[ \gamma (u)(1+z^{-1})p_1(u)+(\gamma (u)(z^{-1}+z^{-2})\right. \\&\left. +\mu (u)z^{-1})p_0(u)\right] \varPhi (z,u,t)du \left( \bar{\gamma }\left( 1-\frac{z}{r_1}\right) (r_2-r_3)\right) ^{-1}. \end{aligned}$$

So we may write our asymptotic estimate as

$$\begin{aligned} \pi _n(t)\approx \frac{-r_3H(r_2,t)}{r_2^n}+\frac{r_2H(r_3,t)}{r_3^n}. \end{aligned}$$

This solution is analogous to that obtained by Krinik and Shun for the steady-state distribution. They had

$$\begin{aligned} \pi _n= \frac{c_2}{r_2^n}+\frac{c_3}{r_3^n} \end{aligned}$$

for constants $c_2$ and $c_3$ which they give explicitly in their paper [2].

5 Asymptotic Estimates for Level Independent Quasi-Birth-Death Processes

The same method can be used to obtain estimates for the level distribution for QBDs with level independent transitions. Such QBDs will have infinitesimal generator with block tri-diagonal structure:

$$\begin{aligned} \mathbf{Q}(t)=\left[ \begin{array}{ccccc}{} \mathbf{B}(t)&{}\mathbf{A}_1(t)&{}0&{}0&{}\cdots \\ \mathbf{A}_{-1}(t)&{}\mathbf{A}_0(t)&{}\mathbf{A}_1(t)&{}0&{}\cdots \\ 0&{}\mathbf{A}_{-1}(t)&{}\mathbf{A}_0(t)&{}\mathbf{A}_1(t)&{}\cdots \\ 0&{}0&{}\mathbf{A}_{-1}(t)&{}\mathbf{A}_0(t)&{}\cdots \\ \vdots &{}\vdots &{}\vdots &{}\vdots &{}\ddots \end{array}\right] , \end{aligned}$$

(14.10)

where $\mathbf{A}_{-1}(t)$, $\mathbf{A}_0(t)$, $\mathbf{A}_1(t)$ and $\mathbf{B}(t)$ are square matrices of order m, and m represents the number of phases.

We partition $\varvec{\pi }(t)$ by levels into subvectors $\varvec{\pi }_n(t),$ $n\ge 0$, where $\varvec{\pi }_n(t)$ has m components. The QBD system satisfies the Chapman–Kolmogorov forward equations

$$\begin{aligned} \dot{\varvec{\pi }}_0(t)= & {} \varvec{\pi }_0(t)\mathbf{B}(t)+\varvec{\pi }_1(t)\mathbf{A}_{-1}(t)\\ \dot{\varvec{\pi }}_n(t)= & {} \varvec{\pi }_{n-1}(t)\mathbf{A}_1(t)+\varvec{\pi }_n(t)\mathbf{A}_{0}(t)+\varvec{\pi }_{n+1}(t)\mathbf{A}_{-1}(t), \end{aligned}$$

with the additional requirement that

$$\begin{aligned} \sum _{n=0}^\infty \varvec{\pi }_n(t)\mathbf{1}=1. \end{aligned}$$

For periodic rates with period of length one, if stability conditions are met, there will be a solution of the Chapman–Kolmogorov equations such that

$$\begin{aligned} \varvec{\pi }_n(t)=\varvec{\pi }_n(t+k), \end{aligned}$$

$k\in \mathbb {Z}$.

The generating function for the random walk corresponding to this QBD satisfies

$$\begin{aligned} \varPhi (z,s,t)&=\sum _{n=-\infty }^\infty \varvec{\phi }_n(s,t)z^n,\\ \frac{\partial }{\partial t}\varPhi (z,u,t)&=\varPhi (z,u,t)\left( z^{-1}\mathbf{A}_{-1}(t)+\mathbf{A}_0(t)+z\mathbf{A}_1(t)\right) , \end{aligned}$$

where $\phi _n(s,t)$ is an $m\times m$ matrix of transition probabilities. The (i, j) component represents the probability of traveling to phase j by time t and remaining there until at least time t and traveling to a level n units to the right of the level occupied at time s given that the random walk process was in phase i at time s. For more details on the set up and analysis of such systems with time-varying periodic transitions, see [4] or [5]. For more background on quasi-birth-death processes in general see [3].

The generating function for the levels of the QBD solves the differential equation

$$\begin{aligned} \frac{\partial }{\partial t}P(z,s,t)=P(z,s,t)&\left( z^{-1}\mathbf{A}_{-1}(t)+\mathbf{A}_0(t)+z\mathbf{A}_1(t)\right) \\&\qquad \qquad \qquad +\varvec{\pi }_0(t)\left( \mathbf{B}(t)-z^{-1}{} \mathbf{A}_{-1}(t)-\mathbf{A}_0(t)\right) , \end{aligned}$$

so

$$\begin{aligned} P(z,s,t)=\int _s^t \varvec{\pi }_0(u)\left( \mathbf{B}(u)-z^{-1}\mathbf{A}_{-1}(u)-\mathbf{A}_0(u)\right) \varPhi (z,u,t)&du\\ +&P(z,s,s)\varPhi (z,s,t), \end{aligned}$$

and for the periodic case with period 1,

$$\begin{aligned} P(z,t-1,t)&=\\&\int _{t-1}^t \varvec{\pi }_0(u)\left( \mathbf{B}(u)-z^{-1}\mathbf{A}_{-1}(u)-\mathbf{A}_0(u)\right) \varPhi (z,u,t)du\times \\&\qquad \qquad \qquad \qquad \qquad \qquad \qquad \left( \mathbf{I}-\varPhi (z,t-1,t)\right) ^{-1}. \end{aligned}$$

There will be poles in the determinant of the matrix $\left( \mathbf{I}-\varPhi (z,t-1,t)\right)$. These poles will reveal the geometric behavior of the level distribution.

6 Conclusion

This approach to the analysis of time-varying queues with periodic transition rates offers considerable promise for improving the understanding of the behavior of such systems. In particular, it shows that such queues are asymptotically geometric in the queue length distribution. Future work will involve extending these results and further analyzing quasi-birth-and-death problems that fit this framework. For scalar queueing models, computation of the roots is straightforward. For quasi-birth-and-death processes, computation of the roots is feasible in special cases, but is challenging for general QBDs.