1 Introduction

Until the mid-sixties, a queueing problem was considered solved if the solution was given in some form of a generating function or Laplace transform. This is because the inversion of a generating function was either considered unnecessary or a trivial problem. However, the inversion of transforms arising in queueing and other stochastic models (except for simple cases) is not as easy as it was once thought and hence such results can be difficult to exploit in solving practical problems. Many users expressed concerns that such solutions were inadequate. Kendall (1964) made a famous remark that queueing theory wears the Laplacian curtain. Kleinrock (1975) states “one of the most difficult parts of this method of spectrum factorization is to solve for the roots.” In a similar account, Neuts (see Stidham Jr. (2001)) states “In discussing matrix-analytic solutions, I had pointed out that when the Rouché’s roots coincide or are close together, the method of roots could be numerically inaccurate. When I finally got copies of Crommelin’s papers, I was elated to read that, for the same reasons as I, he was concerned about the clustering of roots. In 1932, Crommelin knew; in 1980, many of my colleagues did not....” In this connection, see also Neuts (1981).

The preconceived notion of the above said risks associated with root-finding has carried through to the modern literature of queueing theory. In 2005, Mejia-Téllez makes the following statement: “If the batch size is large, the determination of these roots is difficult….” In a recent paper by Bar-Lev et al. (2007) that analyzes the M/G(m, M)/1 queue, they introduce their model’s characteristic equation as A(M)(z) − zM where M is the maximum batch size. The polynomial A(M)(z) is the probability generating function (p.g.f) of the random variable \( {Y}_n^{(M)} \) which corresponds to the number of job arrivals during the bulk-service period of M jobs from the n-th batch arrival. Bar-Lev et al. (2007) state that “this general solution requires the calculation of the zeros of A(M)(z) − zM which in practice can result in numerical inaccuracies especially when the decision variable M assumes a large value….” In a recent work by Harris et al. (2000), they state that “the standard root-finding problem gets complicated particularly when the inter-arrival time distribution possesses a complicated non-closed form or non-analytic Laplace-Stieltjes transform (L-ST).”

It is evident that the idea of root-finding, an imperative step in inverting a generating function, continues to be dismissed by a large body of researchers based on the perceived risk of numerical inaccuracies and previous remarks made by prominent figures. New methodologies have emerged as workaround solutions. These include numerical convolutions (say, R∗n which is not easy to calculate for large n), the matrix-analytic method (which simplifies to a matrix-geometric method when the underlying distributions are of phase type (Neuts 1981)), not to mention different iterative algorithms or approximation methods. Abate and Whitt (1992) use a Fourier-series method to numerically invert generating functions as well as Laplace transforms. The Fourier-series method involves numerically integrating the transform by means of the trapezoidal rule. The greatest difficulty in this case is approximately calculating the infinite series obtained from the inversion integral.

Historically, when numerical software such as MAPLE and Mathematica could not find a large number of roots (they do now), a software package called QROOT developed by Chaudhry (1991) was used by him and his collaborators to find the roots and use them in solving several queueing models. The algorithm for finding such roots is available in some of their papers. It may be remarked here that MAPLE can now not only find roots that are close to each other (a concern expressed by several researchers) but even repeated roots. As root-finding algorithms continued to be refined, several researchers revisited the problem of inverting a generating function via root-finding. Gouweleeuw (1996) states that it is more efficient to use the roots method to get explicit expressions for probabilities from generating functions. Similarly, Janssen and van Leeuwaarden (2005), who have successfully used the roots method, make the comment, “initially, the potential difficulties of root-finding were considered to be a slur on the unblemished transforms since the determination of the roots can be numerically hazardous and the roots themselves have no probabilistic interpretation. However, Chaudhry et al. (1990) have made every effort to dispel the skepticism towards root-finding in queueing theory.” Daigle and Lucantoni (1991) state that “whenever the roots method works, it works blindingly fast.”

The procedure and results of root-finding are found to be efficient and accurate by those who advocate the use of roots, and therefore, improve the generating function method. However, despite the availability of roots, having to construct and invert a generating function remains a laborious exercise. Such issues for the use of generating functions in solving multi-server queues are noted by Chaudhry and Kim (2016) who, in reviewing the work by Zhao (1994) on the GIX/M/c queue, write “despite the detailed analysis, his derivations to construct the p.g.f.’s and their inversions are evidently lengthy and consider several conditions that can be avoided.” In solving the M/M/c/setup queue, Gandhi et al. (2014) state that “generating function approaches involve guessing the form of the solution and then solving for the coefficients of the guess, often leading to long computations.” Nevertheless, multi-server queues with removable servers (including the M/M/c/setup queue) form an important class of queues that can be used in a wide variety of contexts. Besides the applications in modeling data centres (see Krioukov et al. (2010), Qin and Wang (2007), Horvath and Skadron (2008), Maccio and Down (2015), Phung-Duc (2015), etc.), there have been applications in retail service facilities (see Berman and Larson (2004), and Terekhov and Beck (2009)), and border-crossing stations (see Zhang (2009)). In our survey of the literature on multi-server queues with removable servers, we have concluded that the generating function approach is often disadvantaged over other methods such as the Recursive Renewal Reward (RRR) method, the matrix-analytic method, and recursive methods.

While such limitations of the generating function approach are widely acknowledged in the literature, it is also our opinion that the inconveniences of the generating function approach can be remedied by an alternate approach. Instead of formulating the generating function (i.e. the z-transform of the set of balance equations), we interpret a subset of the balance equations of the model as a set of difference equations. How we proceed to choose such a subset is illustrated in an intuitive manner. By leveraging the properties of the difference equations we are able to give a solution of a general form in terms of the roots of the model’s characteristic equation. In essence, we achieve the solution in an explicit form in a straightforward manner instead of formulating and then inverting a generating function that leads to the same solution. The solution and its coefficients are entirely in terms of roots hence finding such roots is an essential step in our methodology. Once the roots are found, the coefficients can be easily computed.

The purpose of this paper is to demonstrate that our method, the difference equations approach (and therefore the use of roots), can effectively solve an advanced form of multi-server queues with removable servers. The paper is organized in the following manner: We first introduce the baseline model followed by various extensions that have either frequently appeared or are likely to be of interest (bulk arrival, non-homogenous servers, setup and delayed-off times, finite capacity, and multiple staffing levels). Each model has a unique ‘root equation’ which provides the required roots to find the steady-state distribution. This work is followed by the introduction of performance measures and then comparisons against the traditional queue (i.e. the model MX/M/c). While we conclude that the method used here is analytically simple and numerically efficient (when compared against the direct method), it is our hope that the difference equations approach can be considered as a useful tool in analyzing other variants of multi-server queueing control problems.

2 The Baseline Model: The M X/M/c + l/(m, n) Queue

Consider the MX/M/c queue with two types of servers: there are c static servers (with a common service rate μ) which remain turned on at all times. As well, there are l dynamic servers (with a common service rate μ1) that immediately turn on whenever the number of jobs in the system reaches or exceeds an upper-threshold n and are immediately turned off whenever the number of jobs in the system falls to or below a lower-threshold m. We assume the relation between lower and upper bounds (c + l ≤ m ≤ n − 2) is such that all l dynamic servers are turned off immediately whenever the number of jobs in the system becomes c + l or smaller. Upon turning off the l dynamic servers, any jobs being served by those l dynamic servers rejoin the front of the queue. When μ1 = μ, the l servers are called homogenous dynamic servers (and non-homogenous dynamic servers when μ1 ≠ μ).

Jobs arrive in batches of size X and the inter-batch arrival time distribution is exponential with rate λ. The maximum batch size is r, (r <  + ∞) and the batch-size distribution is bh = P(X = h), (1 ≤ h ≤ r) with mean E[X]. We assume that jobs are served in a First-Come-First-Served (FCFS) manner. The traffic intensity of the model is \( \rho =\frac{\lambda E\left[X\right]}{c\mu +l{\mu}_1}<1 \). We refer to this model as the baseline model or in an adaptation of Kendell’s notation, the MX/M/c + l/(m, n) queue.

2.1 Balance Equations

Let J(t) and S(t) denote the number of jobs in the system and the state of servers, respectively, at time t. We form a Markov chain {X(t) = (J(t), S(t)); t ≥ 0} on the state space φ = {(i, s); i ≥ 0, s = 0, 1} where s = 0 and s = 1 indicate that the l dynamic servers are turned off and turned on, respectively. See Fig. 1 below for a simple example of transitions among different states.

Fig. 1
figure 1

Transition diagram of the baseline model when c = 2, l = 1, r = 2, m = 3,and n = 5

Full size image

Let \( {\pi}_{i,s}=\underset{t\to \infty }{\lim }P\left\{J(t)=i,S(t)=s\right\},\left(i,s\right)\in \varphi \) be the joint steady-state distribution of {X(t)}. Note that πi, s > 0 for the following regions of (i, s): (0 ≤ i ≤ n − 1, s = 0) and (i ≥ m + 1, s = 1), and πi, s = 0 otherwise. In this section of the paper we solve for πi, s using the roots method. The system dynamics can be described in terms of the following balance equations:

$$ \lambda {\pi}_{0,0}=\mu {\pi}_{1,0} $$
(1)
$$ \left(\lambda + i\mu \right){\pi}_{i,0}=\lambda \sum \limits_{h=1}^{\mathit{\min}\left(i,r\right)}{b}_h{\pi}_{i-h,0}+\left(i+1\right)\mu {\pi}_{i+1,0},\left(1\le i\le c-1\right) $$
(2)
$$ \left(\lambda + c\mu \right){\pi}_{i,0}=\lambda \sum \limits_{h=1}^{\mathit{\min}\left(i,r\right)}{b}_h{\pi}_{i-h,0}+ c\mu {\pi}_{i+1,0},\left(c\le i\le m-1\right) $$
(3)
$$ \left(\lambda + c\mu \right){\pi}_{i,0}=\lambda \sum \limits_{h=1}^{\mathit{\min}\left(i,r\right)}{b}_h{\pi}_{i-h,0}+ c\mu \left(1-{\delta}_{i,n-1}\right){\pi}_{i+1,0}+{\delta}_{i,m}\left( c\mu +{l}_1{\mu}_1\right){\pi}_{i+1,1},\left(m\le i\le n-1\right) $$
(4)
$$ \left(\lambda + c\mu +l{\mu}_1\right){\pi}_{i,1}=\lambda \left(1-{\delta}_{i,m+1}\right)\left(I\left\{n\le i\le n+r-1\right\}\sum \limits_{h=i-n+1}^{\min \left(i,r\right)}{b}_h{\pi}_{i-h,0}+\sum \limits_{h=1}^{\min \left(i-m-1,r\right)}{b}_h{\pi}_{i-h,1}\right)+\left( c\mu +l{\mu}_1\right){\pi}_{i+1,1},\left(m+1\le i\le n+r-1\right) $$
(5)
$$ \left(\lambda + c\mu +l{\mu}_1\right){\pi}_{i,1}=\lambda \sum \limits_{h=1}^{\mathit{\min}\left(i-n,r\right)}{b}_h{\pi}_{i-h,1}+\left( c\mu +l{\mu}_1\right){\pi}_{i+1,1},\left(n+r\le i\le n+2r-1\right) $$
(6)
$$ \left(\lambda + c\mu +l{\mu}_1\right){\pi}_{i,1}=\lambda \sum \limits_{h=1}^{\mathit{\min}\left(i-n-r,r\right)}{b}_h{\pi}_{i-h,1}+\left( c\mu +l{\mu}_1\right){\pi}_{i+1,1},\left(i\ge n+2r\right) $$
(7)

where \( {\delta}_{i,j}=1\ \mathrm{if}\ i=j\ \mathrm{and}\ 0\ \mathrm{otherwise}, \) and I{a ≤ i ≤ b} is an indicator function such that I{a ≤ i ≤ b} = 1 for a ≤ i ≤ b and 0 otherwise. As a remark, the balance equations above can be analytically extended to incorporate finite capacity (see Appendix 3), set up and delayed-off times (Sections 3 and 4), and k staffing levels (Section 5).

2.2 Direct Method

Given the balance equations of the baseline model, one could find the joint steady-state distribution via the direct method; we assume that the balance equation (7) terminates at N′, where N′ is chosen such that \( {\pi}_{N^{\prime },s} \) is an extremely small probability. Similar to the direct method employed by Chaudhry et al. (2001), we establish the following condition in determining N′; there exists a positive integer N′ such that \( \left|{\pi}_{N^{\prime }-1,s}-{\pi}_{N^{\prime },s}\right|<{10}^{-50} \). A disadvantage of the direct method would be in having to solve a large number of equations. While it could be extremely time-consuming to solve a very large number of simultaneous equations, picking a threshold larger than 10−50 leads to a lower N′, but may result in numerical inaccuracies (possibly ranging from being a few decimal places off to even negative probabilities). In our baseline model, finding the joint steady-state distribution via the direct method involves solving a set of ND = N′ + n − m equations. Later in Section 6, we compare ND against that of our method for each model extension.

2.3 Root Equation

In light of the transition diagram in Fig. 1, we identify the repeating portion of the state transition diagram as {πi,1, i ≥ n + r} which corresponds to the balance equation (7). While balance equation (6) also qualifies as a repeating portion, our approach is to assume a general solution at a higher i (i.e. i ≥ n + r) and then analytically exploit the balance equations backwards (i.e. 0 ≤ i ≤ n + r − 1) to see which segment(s) of the transition diagram (both repeating and non-repeating portions) can be represented by our general solution (this is described in detail in Appendix 2). Doing so also reduces the number of equations, the benefit of which is numerically shown in Section 6. Therefore, in solving the baseline queue, we select the solution of a general form πi, 1 = Czi, (i ≥ n + r) as it represents our chosen repeating portion, as well as satisfying the required properties of difference equations (Appendix 5). Substituting the solution of this general form into the balance equation (7) leads to

$$ \left(\lambda + c\mu +l{\mu}_1\right)C{z}^i=\lambda \sum \limits_{h=1}^r{b}_hC{z}^{i-h}+\left( c\mu +l{\mu}_1\right)C{z}^{i+1},\left(i\ge n+2r\right) $$

or rearranged as

$$ 1=\frac{1}{\lambda + c\mu +l{\mu}_1}\left[\lambda \sum \limits_{h=1}^r{b}_h{z}^{-h}+\left( c\mu +l{\mu}_1\right)z\right] $$
(8)

We define expression (8) as the root equation of the model. Since (8) has r roots inside the unit circle |z| = 1, let these roots be z1, z2, …, zr (see Appendix 1 for the proof). The solution of a general form becomes r-fold in that it becomes a geometric sum

$$ {\pi}_{i,1}=\sum \limits_{h=1}^r{C}_h{z}_h^i,\left(i\ge n+r\right) $$
(9)

where Ch for 1 ≤ h ≤ r are yet to be determined non-zero constants. As a remark, one may exploit the option of considering the balance equation (3) (instead of (7)) as the r-th order linear difference equation. However, doing so will lead to r roots that exist under the condition \( \frac{\lambda E\left[X\right]}{c\mu}<1 \). This results in an incomplete solution since the joint steady-state distribution cannot be computed when \( \rho <1\le \frac{\lambda E\left[X\right]}{c\mu} \). Therefore, the balance equation (3) is deemed inappropriate to be the difference equation in determining the joint steady-state distribution.

2.4 Determining the Joint Steady-State Distribution

Given (9), let NR be the total number of unknowns which is the sum of the following: The total number of unknown probabilities {πi,0, 0 ≤ i ≤ n − 1}, {πi,1, m + 1 ≤ i ≤ n + r − 1}, and the total number of unknown constant terms Ch, (1 ≤ h ≤ r). Therefore the unknown probabilities and constant terms can be found by generating NR = 2n − m + 2r − 1 equations. Intuitively, these NR equations can be generated from the balance equations (2) through (6) along with the normalizing condition:

$$ \sum \limits_{i=0}^{n-1}{\pi}_{i,0}+\sum \limits_{i=m+1}^{\infty }{\pi}_{i,1}=1 $$
(10)

The benefit of a difference equations approach is not just in being able to express the lengthy tail probabilities (i.e. πi,1 for i ≥ n + r) in terms of a single expression (9). By leveraging the root equation (8) and other properties of difference equations (Appendix 5), we can further reduce NR in a systematic way (see Appendix 2 for details). Reducing NR significantly increases the computational efficiency when compared against ND from the direct method (see Section 6).

3 Extension to the M X/M/c + l/(m, n)/setup Queue

The baseline model can be extended to feature a set up time; consider a situation where the l dynamic servers are initially turned off and then an upper-threshold has been reached due to a batch arrival. Instead of turning on immediately, all l dynamic servers go through an exponentially distributed set up time in a collective manner. After this setup time has elapsed, the l dynamic servers are turned on and begin to serve. Let A denote a generic setup time with mean \( E\left[A\right]=\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$\alpha $}\right. \). With the definition of ρ remaining unchanged, the stability condition (ρ < 1) also holds in this extended model. In Kendall’s notation we denote this extension as an MX/M/c + l/(m, n)/setup queue. It has the joint steady-state distribution {πi,0, i ≥ 0} and {πi,1, i ≥ m + 1}. The normalizing condition is defined as

$$ \sum \limits_{i=0}^{\infty }{\pi}_{i,0}+\sum \limits_{i=m+1}^{\infty }{\pi}_{i,1}=1 $$
(11)

See Fig. 2 below for a simple example of transitions among different states.

Fig. 2
figure 2

Transition diagram of the MX/M/c + l/(m, n)/setup queue when c = 2, l = 1, r = 2, m = 3,and n = 5

Full size image

The balance equations that describe the system dynamics of the MX/M/c + l/(m, n)/setup queue are provided: While the balance equations (1) through (3) from Section 2.1 remain unchanged, the balance equation (4) is modified by replacing δn − 1, n − 1 with 0. Similarly, the balance equation (5) is modified as follows:

$$ \left(\lambda + c\mu +l{\mu}_1\right){\pi}_{i,1}=\lambda \sum \limits_{h=1}^{\mathit{\min}\left(i-m-1,r\right)}{b}_h{\pi}_{i-h,1}+\left( c\mu +l{\mu}_1\right){\pi}_{i+1,1},\left(m+2\le i\le n-1\right) $$
(12)

In addition, the following two balance equations are added:

$$ \left(\lambda +\alpha + c\mu \right){\pi}_{i,0}=\lambda \sum \limits_{h=1}^{\min \left(i,r\right)}{b}_h{\pi}_{i-h,0}+ c\mu {\pi}_{i+1,0},\left(i\ge n\right) $$
(13)
$$ \left(\lambda + c\mu +l{\mu}_1\right){\pi}_{i,1}=\lambda \sum \limits_{h=1}^{\mathit{\min}\left(i-m-1,r\right)}{b}_h{\pi}_{i-h,1}+\alpha {\pi}_{i,0}+\left( c\mu +l{\mu}_1\right){\pi}_{i+1,1},\left(i\ge n\right) $$
(14)

3.1 Root Equation and Determining the Joint Steady-State Distribution

To determine the joint steady-state distribution {πi,s, i ≥ 0, s = 0, 1} we interpret the balance equation (13) as an r-th order linear difference equation. By doing so, we select the solution of a general form πi,0 = Czi, (i ≥ n + r) given that the repeating portions of the transition diagram span the region i ≥ n + r. Substituting the solution of this general form into the balance equation (13) leads to

$$ 1=\frac{1}{\lambda +\alpha + c\mu}\left(\lambda \sum \limits_{h=1}^r{b}_h{z}^{-h}+ c\mu z\right) $$
(15)

The root equation (15) has r roots inside the unit circle |z| = 1 (this can be proved in a similar manner as described in Appendix 1). Let the roots of (15) be z1, z2, …, zr. The general solution becomes r-fold of the form

$$ {\pi}_{i,0}=\sum \limits_{h=1}^r{C}_h{z}_h^i,\left(i\ge n+r\right) $$
(16)

Depending on the size of r, (16) could also hold for (n ≤ i ≤ n + r − 1) which can be proved in a similar manner as described in Appendix 2. In solving for the joint steady-state distribution the direct method would result in having to solve a set of ND = 2N′ − m + 1 equations whereas expressing the queue length in terms of the geometric sum results in having to solve a set of NR = N′ + n − m + r equations; a numerical comparison between the values ND and NR is made in Section 6. As a remark, the rationale for choosing the balance equation (13) as the difference equation in lieu of the other balance equations that represent the repeating portions is as follows: The balance equation (3) is unsuitable for the same reasons as indicated in Section 2.3. The balance equation (12) is also unsuitable since it requires the general solution πi,1 = Czi, (m + r + 2 ≤ i ≤ n) which imposes a more stringent assumption (m + r + 2 ≤ n) while the original region is m + 2 ≤ n. Lastly, the balance equation (14) is unsuitable since it requires the general solution πi,0 + πi, 1 = Czi, (i ≥ n + r) that leads to a root equation with r − 1 roots inside the unit circle and the r-th root on the unit circle (i.e. |zr| = 1).

4 Extension to the M X/M/c + l/(m, n)/delayedoff Queue

The baseline model (or the extended model featuring a setup time) can be extended to feature a delayed-off time; consider a situation where the number of jobs in the system has dropped to m. Instead of turning off immediately, the l dynamic servers remain collectively turned on for an exponentially distributed period of time before removal. Let B denote a generic delayed-off time with mean \( E\left[B\right]=\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$\beta $}\right. \). We denote this extension as the MX/M/c + l/(m, n)/delayedoff queue with the joint steady-state distribution {πi,0, 0 ≤ i ≤ n − 1} and {πi,1, i ≥ 0}. The normalizing condition is given by

$$ \sum \limits_{i=0}^{n-1}{\pi}_{i,0}+\sum \limits_{i=0}^{\infty }{\pi}_{i,1}=1 $$
(17)

See Fig. 3 below for a simple example of transitions among different states.

Fig. 3
figure 3

Transition diagram of the MX/M/c + l/(m, n)/delayedoff queue when c = 2, l = 1, r = 2, m = 3,and n = 5

Full size image

The balance equations that describe the system dynamics of the MX/M/c + l/(m, n)/delayedoff queue are obtained by modifying the earlier ones. From Section 2.1, we replace δm + 1, m + 1 with 0 and replace the expression ‘min(i − m − 1, r)’ with ‘min(i, r)’ in the balance equation (5). The balance equations (6) and (7) remain unchanged. In addition the balance equations (1) through (4) are modified as follows:

$$ \lambda {\pi}_{0,0}=\mu {\pi}_{1,0}+\beta {\pi}_{0,1} $$
(18)
$$ \left(\lambda +\beta \right){\pi}_{0,1}=\left( c\mu +l{\mu}_1\right){\pi}_{1,1} $$
(19)
$$ \left(\lambda + i\mu \right){\pi}_{i,0}=\lambda \sum \limits_{h=1}^{\mathit{\min}\left(i,r\right)}{b}_h{\pi}_{i-h,0}+\left(i+1\right)\mu {\pi}_{i+1,0}+\beta {\pi}_{i,1},\left(1\le i\le c-1\right) $$
(20)
$$ \left(\lambda + c\mu \right){\pi}_{i,0}=\lambda \sum \limits_{h=1}^{\mathit{\min}\left(i,r\right)}{b}_h{\pi}_{i-h,0}+ c\mu {\pi}_{i+1,0}+\beta {\pi}_{i,1},\left(c\le i\le m\right) $$
(21)
$$ \left(\lambda + c\mu +l{\mu}_1+\beta \right){\pi}_{i,1}=\lambda \sum \limits_{h=1}^{\mathit{\min}\left(i,r\right)}{b}_h{\pi}_{i-h,1}+\left( c\mu +l{\mu}_1\right){\pi}_{i+1,1},\left(1\le i\le m\right) $$
(22)
$$ \left(\lambda + c\mu \right){\pi}_{i,0}=\lambda \sum \limits_{h=1}^{\mathit{\min}\left(i,r\right)}{b}_h{\pi}_{i-h,0}+ c\mu \left(1-{\delta}_{i,n-1}\right){\pi}_{i+1,0},\left(m+1\le i\le n-1\right) $$
(23)

As a remark, the balance equations for the MX/M/c + l/(m, n)/setup/delayedoff queue can be easily obtained by combining the balance equations (18) through (22) with (13), (14), and the following modified balance equations: Balance equation (23) is modified by replacing δn − 1, n − 1 with 0. The lower bound of the range for balance equation (12) is modified to i ≥ m + 1 (versus i ≥ m + 2) and in balance equations (12) and (14), each instance of ‘min(i − m − 1, r)’ is replaced with ‘min(i, r)’. The normalizing condition for the MX/M/c + l/(m, n)/setup/delayedoff queue is \( \sum \limits_{i=0}^{\infty }{\pi}_{i,0}+\sum \limits_{i=0}^{\infty }{\pi}_{i,1}=1 \). See Fig. 4 below for a simple example of transitions among different states.

Fig. 4
figure 4

Transition diagram of the MX/M/c + l/(m, n)/setup/delayedoff queue when c = 2, l = 1, r = 2, m = 3,and n = 5

Full size image

4.1 Root Equations and Determining the Joint Steady-State Distribution

The general solutions and the root equations of the MX/M/c + l/(m, n)/delayedoff and the MX/M/c + l/(m, n)/setup/delayedoff queues are identical to that of the baseline and the MX/M/c + l/(m, n)/setup queue, respectively. Let NR be the total number of unknown probabilities and unknown constant coefficients of the solution. In the model MX/M/c + l/(m, n)/delayedoff there are NR = 2(n + r) (versus ND = N′ + n + 1) unknowns whereas in the model MX/M/c + l/(m, n)/setup/delayedoff there are NR = N′ + n + r + 2 (versus ND = 2(N′ + 1)) unknowns. The same number of equations can be generated from the respective balance equations and the normalizing condition.

5 Extension to the M X/M/c + l/(m, n) Queue with k Staffing Levels

The baseline model (or all previous extensions) can be extended to feature k (k ≥ 2) staffing levels such that groups of servers (say l1, l2, …, lk each with service rate μ1, μ2, …, μk) are turned on sequentially in an aggregate manner as the number of jobs in the system grows to surpass a sequence of increasing upper-thresholds (say n1, n2, …, nk). These server groups are then turned off in the reverse order (i.e. lk, lk − 1, …, l1) as the number of jobs in the system drops below a decreasing sequence of lower-thresholds (say mk, mk − 1, …, m1). With these additional staffing levels, the following properties must hold: \( c+\sum \limits_{s=1}^k{l}_s\le {m}_s\le {n}_s-2 \) for (1 ≤ s ≤ k) and the traffic intensity \( \rho =\frac{\lambda }{c\mu +\sum \limits_{s=1}^k{l}_s{\mu}_s}<1 \). We call this extended system an MX/M/c + l/(m, n) queue with k staffing levels. The corresponding joint steady-state distribution is given by {πi,s, i ≥ 0, 0 ≤ s ≤ k}. The normalizing condition is

$$ \sum \limits_{i=0}^{n_1-1}{\pi}_{i,0}+\sum \limits_{s=1}^{k-1}\sum \limits_{i={m}_s+1}^{n_{s+1}-1}{\pi}_{i,s}+\sum \limits_{i={m}_k+1}^{\infty }{\pi}_{i,k}=1 $$
(24)

The balance equations that describe the system dynamics of the MX/M/c + l/(m, n) queue with k staffing levels can be derived in a similar manner to previous models. The balance Equations (1) and (2) from Section 2.1 remain unchanged and the remainder of the balance equations are provided in Appendix 3.

5.1 Root Equation and Determining the Joint Steady-State Distribution

In solving the MX/M/c + l/(m, n) queue with k staffing levels via the difference equations approach, we substitute the general solution πi,k = Czi, (i ≥ nk + r) into the balance equation (44) such that it leads to the root equation

$$ 1=\frac{1}{\lambda + c\mu +\sum \limits_{s=1}^k{l}_s{\mu}_s}\left[\lambda \sum \limits_{h=1}^r{b}_h{z}^{-h}+\left( c\mu +\sum \limits_{s=1}^k{l}_s{\mu}_s\right)z\right] $$
(25)

equation (25) has r roots inside the unit circle |z| = 1 (this can be proved similarly to the result in Appendix 1); let these roots be z1, z2, …, zr. The general solution becomes r-fold of the form

$$ {\pi}_{i,k}=\sum \limits_{h=1}^r{C}_h{z}_h^i,\left(i\ge {n}_k+r\right) $$
(26)

where Ch, (1 ≤ h ≤ r) are non-zero constants. The joint steady-state distribution of the MX/M/c + l/(m, n) queue with k staffing levels can be found by solving the \( {N}_{\mathrm{R}}={m}_1+\sum \limits_{s=1}^{k-1}\left({n}_s-2{m}_s-1+{m}_{s+1}\right)+2\left({n}_k-{m}_k\right)+r-1 \) equations. As a remark, NR can be systematically reduced by leveraging (25) and (26) in a similar manner as shown in Appendix 1.

6 Numerical Comparison against the Direct Method

In this section we show numerical comparisons between NR and ND for each model. Results were verified by evaluating a state probability independently at N′ (i.e. direct and difference equations method) and then matching them.

As a remark, in Table 1, a significant reduction from ND to NR is achieved in rows 1, 3, and 5, whereas the reduction from ND to NR is approximately halved in rows 2 and 4. The reason for such numerical behaviour is as follows. The presence of setup times (i.e. rows 2 and 4) results in partial expression of the queue length in terms of roots. In other words, we can express πi,0 = Czi, (i ≥ n + r) but the expression πi,0 + πi, 1 = Dyi, (i ≥ n + r) does not hold (see Section 3.1 for further explanation). Therefore, we must treat {πi,1, i ≥ n + r} as unknowns while we are able to express {πi,0, i ≥ n + r} entirely in terms of the roots of equation (15). Because we have nearly halved the number of unknowns, NR in our approach, when compared against ND, is approximately halved. On the contrary, in rows 1, 3, and 5 both {πi,1, i ≥ n + r} and {πi,0, i ≥ n + r} are entirely expressed in terms of the roots. This results in a greater reduction in NR.

Table 1 λ = 2.0, c = 5, l = 5, μ = 0.5, μ1 = 0.5, m = c + l, n = m + 2, b1 = 0.5, b2 = 0.5
Full size table

7 Performance Measure and Trade-off Analysis

In this section we first introduce a list of performance measures (Table 2) followed by a trade-off analysis between those performance measures (Tables 3, 4, 5 and 6). The performance measures can be largely divided into two categories; system performance and resource consumption. The system performance indicates how well the system is performing whereas the resource consumption indicates the efforts consumed in achieving the corresponding level of system performance. There is a trade-off between the two categories, the extent of which also depends on other factors such as the upper-threshold, mean batch size, and traffic intensity. Using the joint steady-state distribution from earlier sections of this paper we are able to derive all performance measures. As a remark, while some of our performance measures are deducible from a p.g.f., others, such as the switching cost rate, are more conveniently found from the distribution itself.

Table 2 Performance measures under the two categories
Full size table
Table 3 E[X] < c with b1 = 1.0
Full size table
Table 4 c < E[X] < c + l with b1 = 0.5 and b3 = 0.5
Full size table
Table 5 E[X] = c + l with b1 = 0.5 and b11 = 0.5
Full size table
Table 6 E[X] > c + l with b1 = 0.5 and b15 = 0.5
Full size table

Using our performance measures in Table 2, we conducted a trade-off analysis between the system performance and resource consumption. Throughout Tables 3, 4, 5 and 6, we have taken the MX/M/c + l/(m, n)/K (and MX/M/c/K) queues where for each upper-threshold (n = 8, 13, 18, 23, 28, 33,and 38) we have represented each corresponding performance measure as a horizontal colour-coded bar (different colours represent different performance measures while the height of each bar corresponds to the magnitude of that performance measure). The height of each bar is based on the ratio to the maximum entry of that metric in the table such that a full bar height corresponds to the maximum entry in that table. We have utilized the parameters c = 2, l = 4, μ = 2.0, μ1 = 2.5, λ = 1.5, m = c + l, K = 70, and \( \varepsilon =\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$\lambda $}\right. \) throughout Tables 3, 4, 5 and 6. Our findings are summarized in four observations.

  • Observation 1: Across all tables the MX/M/c/K queue results in the largest PPJL and Lq. As the mean batch size increases, the probability of dynamic server utilization becomes larger. Conversely, as the mean batch size decreases, the probability of dynamic server utilization becomes smaller.

  • Observation 2: A high switching cost rate coincides with a high chance of the number of customers in the system crossing above and below the upper and lower-thresholds, respectively. It is observed that the switching cost rate is highest when the mean batch size is identical to the system’s lower-threshold (i.e. Table 5); a higher chance of crossing above and below the upper and lower-thresholds requires moderately sized batches as well as a moderate rate of batch arrivals. While all tables have identical rates of batch arrivals, each table has different mean batch size. Table 5 appears to have the most moderate mean batch size which contributes to it having the highest switching cost rate.

  • Observation 3: The impact of dynamic servers on the system is more pronounced when the mean batch size is higher: When the mean batch size is smaller than the system’s total capacity (i.e. Tables 3 and 4), adding dynamic servers leads to a relatively small drop in Lq while Is remains relatively unchanged. When the mean batch size is larger than the system’s total capacity (i.e. Tables 5 and 6), adding dynamic servers leads to a sharp decrease in Lq.

  • Observation 4: PPJL increases with n at a modest rate; it is expected that PPJL will increase at a much faster rate when the mean batch size is larger.

To conclude, we summarize our findings in terms of when the dynamic servers appear to be effective (or ineffective). When the mean batch size is very small (i.e. E[X] < c), the dynamic servers appear to be ineffective across all values of n. When the mean batch size is relatively small (i.e. c < E[X] < c + l) the dynamic servers contribute effectively in lowering the queue size only when they are turned on at smaller values of n. For higher values of n, the dynamic servers appear to be ineffective. For larger mean batch size (i.e. E[X] ≥ c + l), in general, the dynamic servers effectively contribute to reducing the queue size even at smaller values of n.

8 Conclusion

In this paper, we have demonstrated that the difference equations approach stands as a reliable tool in treating advanced forms of multi-server bulk arrival queues. Through this work, what would have otherwise been done via the generating functions approach has been greatly simplified by intuitively choosing a set of balance equations as difference equations. Doing so relies heavily on the finding of Rouché’s roots; a critical step in a solution procedure that has been heavily criticized by some researchers due to the perceived risk of numerical inaccuracies, and the laborious and ambiguous steps involved in constructing and inverting a generating function (see Section 1). Such issues are compounded when extending to bulk arrival queues as multiple roots are often involved. Nevertheless, we have successfully demonstrated that our method can handle an advanced form of quasi birth and death process that features bulk arrival, setup and delayed-off times, finite capacity, non-homogenous dynamic servers, and k staffing levels. In the future, our plan is to apply our method in solving non-Markovian and semi-Markovian models that feature working vacations and are formulated in discrete-time.