Keywords

1 Introduction

Many queueing systems are subject to time-dependent changes in system parameters. This feature is very important to cover the problems with seasonality and periodicity of stochastic processes. Particularly it happens with an arrival rate which is used for modelling of arrivals of calls and inquires at call centres, arrival of packets at routers of the telecommunication systems, of time changing air traffic at airports, different arrival rates of trucks to the warehouses, goods depot or seaports and so on. A very good literature overview on this subject can be found in [4]. This paper surveys and classifies the results on performance evaluation approaches for time-dependent queueing systems and their applications and identifies the links between different approaches. The performance analysis of multi-server queueing system subject to breakdowns was studied in [1]. There are several approaches to analyse such systems. The dynamic behaviour of Markovian queueing systems is described by a system of Kolmogorov differential equations (KDEs). Analytical solution of such systems exists only for special cases. Numerical approaches are based on a Runge-Kutta method. The systems with an infinite buffer are normally approximated by using a finite buffer system. The numerical solution of KDEs is used for example for the performance evaluation of a M(t)/M/1/N system in [3].

In many cases the time-dependent system parameters must be combined with some controllable problems. The paper [5] deals with optimal allocation of such resources as beds in emergency departments of a hospital. For the mathematical modelling the queueing system with losses of the type is used. It was shown that the periodic variation of arrival rates makes a hysteretic policy time-dependent and periodic with the same period. To find the optimal decisions dynamic programming is used. The same approach was used in [2] for the multi-server queueing system with a controllable number of homogeneous servers.

The contribution of the present work is an evaluation of the optimal number of servers in multi-server queueing system with homogeneous and heterogeneous servers and time-dependent arrival rate. The discretization of a continuous-time Markov process is performed to apply the Runge-Kutta method and the iterative dynamic programming algorithm over a finite horizon. The decisions are chosen at specified moments of time which divide the observation time interval into so called stages. The number of available servers is assumed to be a constant within each stage. The paper provides comparison analysis of stationary and transient solutions as well as homogeneous and heterogeneous systems.

The rest of the paper is organized as follows. In Sect. 2 we describe a mathematical model and formulate a optimization problem for transient and stationary case. Section 3 deals with a description of a time-dependent arrival rate. In Sect. 4 a forth-order Runge-Kutta method is adopted for the model under study. The recursive dynamic programming algorithm is shown in Sect. 5. Some illustrative numerical examples are discussed in Sect. 6. Conclusions are given in Sect. 7.

2 Mathematical Model

Consider the controllable multi-server queueing system M(t)/M/K with K servers. This system features Poisson arrival stream with time dependent arrival rate \(\lambda (t)\). The servers are assumed to be heterogeneous with servers intensities \(\mu _j, j=1,2,\dots ,K\). In special case when all intensities are equal, \(\mu _j=\mu , j=1,2,\dots ,K\), we get the homogeneous system. The control consists in specification of the number of servers K(t) at any decision epoch which will be specified later.

Denote by N(t) the number of customers in the system at time t. The dynamics of the system is described by means of the controllable continuous-time inhomogeneous Markov chain \(\{N(t)\}_{t\ge 0}\) with a set of states \(E=\{n;n\in \mathbb {N}_0\}\) and set of control actions \(A=\{1,2,\dots ,K\}\). Define additional cost structure with the following components: \(c_1\) – the waiting cost per unit of time for each customer in the queue, \(c_{2,j}\) – the idle state cost per unit of time when the server j is idle. In homogeneous case it is assumed that \(c_{2,j}=c_2\), \(j=1,2,\dots ,K\). The servers are enumerated in such a way that

$$\begin{aligned} \mu _1\ge \mu _2\ge \dots \ge \mu _K,\quad c_{2,1}\ge c_{2,2}\ge \dots \ge c_{2,K}. \end{aligned}$$
(1)

In accordance with the given cost structure, the mean total cost criterion is denoted by

$$\begin{aligned} J^f(n)=\mathbb {E}^f[\int _0^{T}c(N(t),K(t),\lambda (t),t)dt|N(0)=n]. \end{aligned}$$
(2)

Here f is a Markov control policy which depends on the current state and time only, i.e. \(K(t)=f(t,n(t))\), the expectation \(\mathbb {E}^f\) is taken with respect to the probability distribution \(\mathbb {P}^f\) over the state-action sequence under control policy f. The immediate cost function \(c(N(t),K(t),\lambda (t),t)\) is defined as

$$\begin{aligned} c(N(t),K(t),\lambda (t),t)&=c_1\sum _{k=K(t)+1}^{\infty }(k-K(t))1_{\{N(t)=k\}}\\&+\sum _{k=0}^{K(t)}\sum _{j=k+1}^{K(t)}c_{2,j}1_{\{N(t)=k\}}.\nonumber \end{aligned}$$
(3)

The substitution of (3) into (2) yields the relation for the mean total cost in form

$$\begin{aligned} J^f(n)&=\int _0^T\eta (n,K(t),\lambda (t),t)dt\\&=\int _0^T\Big [c_1\bar{Q}(n,K(t),\lambda (t),t)+\sum _{k=0}^{K(t)}\sum _{j=k+1}^{K(t)}c_{2,j}\pi _k(n,K(t),\lambda (t),t)\Big ]dt.\nonumber \end{aligned}$$
(4)

The first term by \(c_1\) at the right hand side of (4) stands for the mean number of customers in the queue at time t with K(t) servers and initial state \(N(0)=n\), the second term stands for the mean idle state costs. We wish to minimize the functional \(J^f(n)\) over all control policies and find optimal policy \(f^*\) that achieves the minimal cost \(J^*(n)\), i.e.

$$\begin{aligned} J^*(n):=J^{f^*}(n)=\min _f J^f(n). \end{aligned}$$
(5)

The solution of proposed optimization problem can be performed numerically. To realize some iterative algorithm the continuous time model must be converted to a discrete one. We divide a time interval [0, T] into I equally spaced periods. The mean total cost functional in this case can be rewritten a follows,

$$\begin{aligned} J^f(n)&=\sum _{i=1}^I\eta (n,K(i),\lambda (i),i)\\&=\sum _{i=1}^I\Big [c_1\bar{Q}(n,K(i),\lambda (i),i)+\sum _{k=0}^{K(i)}\sum _{j=k+1}^{K(i)}c_{2,j}\pi _k(n,K(i),\lambda (i),i)\Big ],\nonumber \end{aligned}$$
(6)

where K(i) is a number of servers at period i, \(\bar{Q}(n,K(i),\lambda (i),i)\) is a mean number of customers in the queue at period i, \(\pi _k(n,K(i),i)\) – probability of k customers in the system with K(i) servers at period i with initial state n.

The transient solution of the problem will be compared with a stationary one. In this case the long-run average cost per unit of time

$$\begin{aligned} \eta (K,\lambda (t))=c_1\bar{Q}(K,\lambda (t))+\sum _{k=0}^K\sum _{j=k+1}^K c_{2,j}\pi _k(K,\lambda (t)) \end{aligned}$$
(7)

must be minimized over K(t) for any fixed value \(\lambda (t)\). The substitution of the stationary state probabilities of the infinite buffer system into (7) yields the relation

$$\begin{aligned} \eta (K(t),\lambda (t))&=\Big [c_1\prod _{j=1}^{K(t)}\frac{\lambda (t)}{\sum _{k=1}^j\mu _k}\frac{\lambda (t)\sum _{k=1}^{K(t)}\mu _k}{(\lambda (t)-\sum _{k=1}^{K(t)}\mu _k)^2}\nonumber \\&+\sum _{k=0}^{K(t)}\sum _{j=k+1}^{K(t)}c_{2,j}\frac{\lambda (t)^k}{\prod _{l=1}^k\sum _{j=1}^l\mu _j}\Big ]\pi _0(K(t),\lambda (t)),\end{aligned}$$
(8)
$$\begin{aligned} \pi _0(K(t),\lambda (t))&=\\&\Big [\sum _{k=0}^{K(t)-1}\frac{\lambda (t)^k}{\prod _{l=1}^k\sum _{j=1}^l\mu _j}+\prod _{j=1}^{K(t)}\frac{\lambda (t)}{\sum _{k=1}^j\mu _k}\frac{\sum _{k=1}^{K(t)}\mu _k}{\sum _{k=1}^{K(t)}\mu _k-\lambda (t)}\Big ]^{-1}.\nonumber \end{aligned}$$
(9)

3 Arrival Rate

We have chosen a similar arrival rate \(\lambda (t)\) as in the paper from [2]. The authors have studied there incoming and service of airplanes of an airport modelled via a M(t)/M/K/N queuing system. In the queueing system under study the condition

$$\begin{aligned} \lambda (t) < \sum _{j=1}^K\mu _j \end{aligned}$$
(10)

is a necessary one, since there is no cost relation for customers who get rejected. That means that the maximum number of server K can handle the average arrival rate of users. The data for \(\lambda (t)\) is given in Table 1.

Table 1. Values for the arrival rate \(\lambda (t)\)
Full size table

The arrival rate will be divided into three equidistant stages. It means that each stage lasts eight hours, which is a normal working shift cycle. At the beginning of a stage, the number of customers n in the system is known. This value will be called initial state of the current stage. A natural question, one can ask is, how many servers (in this context workers) should be hired at current and following stage(s) so that the expected costs are minimized. Obviously the number of necessary operators are depending on the initial state n.

4 Fourth-Order Explicit Runge-Kutta Method

Since there is no way to solve the system of Kolmogorov forward equations

$$\begin{aligned} \pi ^\prime (t)=\pi (t)A(t) \end{aligned}$$
(11)

analytically a numerical algorithm is needed to get an approximate solution. For this task we have used the standard fourth order explicit Runge-Kutta procedure which is a widely used one-step method. It considers differential equations of the form

$$\begin{aligned} y^\prime (t)=f(t,y(t))\quad \forall t \in (0,T) \end{aligned}$$
(12)

with given initial condition

$$\begin{aligned} y(t_0)=y_0. \end{aligned}$$
(13)

Algorithm 1

The explicit fourth-order Runge-Kutta method.

Step 1. Computation of five parameters \(\kappa _1,\kappa _2,\kappa _3,\kappa _4\) and \(\kappa \):

$$\begin{aligned} \kappa _1&= f(t_n, y_n) \varDelta t \\ \kappa _2&= f(t_n + \frac{\varDelta t}{2}, y_n + \frac{\kappa _1}{2}) \varDelta t \\ \kappa _3&= f(t_n + \frac{\varDelta t}{2}, y_n + \frac{\kappa _2}{2}) \varDelta t\\ \kappa _4&= f(t_n + \varDelta t, y_n + \kappa _3) \varDelta t\\ \kappa&= \frac{1}{6} (\kappa _1 + 2 \kappa _2 + 2 \kappa _3 + \kappa _4) \end{aligned}$$

Step 2. Evaluation of \(y_{n+1}\) by the recursive relation,

$$\begin{aligned} y_{n+1}=y_n +\kappa . \end{aligned}$$

For solving the Kolmogorov forward equations (11) interpret \(f(t) \pi (t)\) as \(f(\pi (t),t)\), choose a appropriate step size \(\varDelta t\) and apply this Runge-Kutta method directly on the function \(f(\pi (t),t)\). Obviously the error between the calculated and the real solution gets less if one selects a smaller step size. On the other hand a greater step size means less computing time. We have chosen \(\varDelta t = 0.005\). This value for the step size seems to have a reasonable balance between computing time and computation error.

To solve the system (11) we use a truncation of the buffer capacity by assuming that N is the maximum allowable number of customers in the system.

5 Optimisation Problem

Let \(T=24\,\mathrm{{h}}\) be an observation cycle and a finite horizon for the dynamic programming. The decision epochs occur each 8 h, hence we get \(S=3\) stages with \(\frac{I}{S}\) periods i within each stage s. A strategy at a decision epoch \(d=(S-s)I/S+1\) which depends on a current stage s is donated by f(d, n), where n stands as before for the initial state. A strategy is equal for any period i from the interval

$$\begin{aligned} d\le i\le d+\frac{I}{S}-1. \end{aligned}$$

Denote by \(V_n(s)\) the optimal cost function for s stages left which we refer to as value function:

$$\begin{aligned} V_n(s)=\min _{f}\mathbb {E}^f[\sum _{i=1}^Ic(N(i),K(i),\lambda (i),i)\,|\,N(s)=n],\,s=1,2,\dots ,S,\,n\in E. \end{aligned}$$
(14)

The minimum must be taken over tail policies

$$\begin{aligned} (f(1,K(1)),f(I/S+1,K(I/S+1)),\dots ,f((S-1)I/S+1,K((S-1)I/S+1)). \end{aligned}$$

Obviously, \(V_n(S)=J^*(n)\).

Algorithm 2

The finite horizon dynamic programming:

Step 1. Backward recursion: \(V_n(0)=0\), \(n\in E\), and

$$\begin{aligned} V_n(s)=\min \limits _{1\le k\le K}\Big \{r(n,k,s)+\sum _{m=0}^N p_{nm}(k,s) V_m(s-1)\Big \}, \end{aligned}$$
(15)

where r(n, k, s) is the total average cost per stage,

$$\begin{aligned} r(n,k,s)=\sum _{i=d}^{d+\frac{I}{S}-1}\eta (n,k,\lambda (i),i),\,s=1,2,\dots ,S, \end{aligned}$$
(16)

and the transition probabilities between the stages are defined as

$$\begin{aligned}&p_{nm}(k,s)= \mathbb {P}\Big [N(d+I/S)=m\Big |N(d)=n,f(d,n)=k\Big ],\end{aligned}$$
(17)
$$\begin{aligned}&s=2,\dots ,S. \end{aligned}$$
(18)

Step 2. Any Markov policy \(f^*\) that satisfies

(19)

is an optimal control policy.

The values \(p_{nm}(k,s)\) in (17) have to be interpreted in the following way. They stand for the probability to be in state m at the beginning of the next stage under the condition that the initial state of the previous stage was n.

Algorithm 3

The following basic steps are involved into the computation procedure:

  • Step 1. Compute the state probabilities \(\pi (n,k,\lambda (i),i)\) for each n, k and i via the Runge-Kutta fourth order method.

  • Step 2. Compute the cost function \(\eta (n,k,\lambda (i),i)\) for each n, k and i.

  • Step 3. Compute r(n, k, s) for each n, k and s by accumulating \(\eta (n,k,\lambda (i),i)\) over all periods i within the corresponding stage.

  • Step 4. Compute the transition probabilities \(p_{nm}(k,s)\) for each n, m, k and s via Runge-Kutta fourth order method.

  • Step 5. Evaluation of the optimal strategy for any s and n by means of Algorithm 2.

The number of servers \(k^*=f(s,n)\) defined by (19) for which the expression in the right hand side of (15) is minimal is called the best or optimal strategy at stage s given the initial state is n.

Remark 1

Notice that in this queueing model rejecting of customers is not a valid option. If, for example, the initial state n at the current stage is the capacity of the buffer plus 2, the best strategy cannot be one server. However if the one choose the waiting room capacity high enough, restrict n up to this value and condition (10) is clearly fulfilled there will be no dropping of users.

6 Numerical Realisation and Results

The main goal in this paper is to compare the operating costs for the M(t)/M/K queue between homogeneous and heterogeneous servers when optimal policies are used. Further the difference between transient and stationary solution will be contrasted for both philosophies. For this computations the following assumptions are used:

  1. 1.

    The maximum number of servers is \(K=6\).

  2. 2.

    The buffer capacity is \(N-K=10\).

  3. 3.

    The waiting cost \(c_1=10\).

  4. 4.

    The service rate of the server in homogeneous case is \(\mu =4\).

  5. 5.

    The service intensities \(\mu _j\), \(j=1,2,\dots ,K\), of heterogeneous servers are listed in Table 2.

  6. 6.

    The idle state cost in homogeneous case is \(c_2=2.1\).

  7. 7.

    The idle state costs \(c_{2,j}\), \(j=1,2,\dots ,K\), for heterogeneous servers are listed in the Table 2.

To get comparability with the homogeneous case we have chosen the service rates and operator idle costs for heterogeneous servers so that they satisfy the following conditions,

$$\begin{aligned} \sum _{j=1}^K\mu _j=K\mu ,\quad \,\sum _{j=1}^K \frac{c_{2,j}}{\mu _j}= \frac{c_{2}}{\mu } \end{aligned}$$
(20)

together with the ordering (1). That means that the server 1 is the fastest one but has the highest mean standing costs. Followed by server 2 and so forth. This is a quite reasonable assumption because a faster operator needs more resources. If this server is idle more costs are generated as for a slower one. In heterogeneous case the fastest free server policy is used for the allocation mechanism. If more then one operator is free and a new customer enters the queue the fastest free server will be entrusted with this task. This must be considered in the calculation of \(\eta (n,k,\lambda (i),i)\). To calculate the best stationary policy the long-run average cost \(\eta (k,\lambda (i))\) must be minimized for k, \(1\le k\le K\). For homogeneous servers the service intensities \(\mu _j\) as well as idle state costs \(c_{2,j}\) in homogeneous case must be set to be equal as was discussed before.

Table 2. Values of \(\mu _j\) and \(c_{2,j}\) for heterogeneous servers
Full size table

In Figs. 1(a) and (b) we illustrate the mean number of customers in the buffer \(\bar{Q}(n,K(t),\lambda (t),t)\) in homogeneous and heterogeneous cases for different number of servers K(t). The queue length for \(K(t)=4,5,6\) servers are not shown in these figures, since the values are very small (especially when heterogeneous servers are used). In Fig. 1(a) and (b) the initial state \(N(t)=n\) at time \(t=0\) is set to be zero. That means the queueing system is at start empty. The mean number of waiting customers, which is needed in (6), is calculated via the formula

$$\begin{aligned} \bar{Q}(n,K(i),\lambda (i),i)=\sum _{k=K(i)+1}^N (k-K(i)) \pi _{k}(n,K(i),\lambda (i),i), \end{aligned}$$
(21)

where K(i) is fixed in period i, k is a state at period i and N is the maximum number of customers in the system. The state probabilities in this expression are the solution of the system (11) performed by the fourth-order Runge-Kutta method for each given number of servers K(i) at each period i.

Fig. 1.
figure 1

\(\bar{Q}(n,K,\lambda (t),t)\) for (a) homogeneous and (b) heterogeneous system

Full size image
Fig. 2.
figure 2

Transient/stationary \(\bar{Q}(n,K,\lambda (t),t)/\bar{Q}(K,\lambda (t))\) for (a) homogeneous and (b) heterogeneous system

Full size image
Table 3. Optimal policy f
Full size table

Figures 2(a) and (b) illustrate how the mean queue length (21) differs from the stationary solution in the homogeneous and heterogeneous case which can be calculated by expression from (8). Again the mean queue length for 4, 5 and 6 servers are not shown because of the small values. The continuously plotted lines belong to the transient and the dashed lines to the stationary solution.

These pictures illustrate clearly the behaviour of the queuing system. When the transient solution is off and \(\lambda (t)\) is a constant value for a certain period it converges to the stationary result as time goes by. This is not astonishing because a stationary queuing system can be interpreted as a long running transient system with a constant arrival rate.

To compare the minimum expected costs between homogeneous/heterogeneous servers in stationary/transient case simply evaluate \(\eta (n,k^*,\lambda (i),i)\) and \(\eta (k^*,\lambda (i))\) for each period i and corresponding optimal number of servers \(k^*\). The calculated values of the optimal policy are listed in Table 3. To get more server variety in the transient solutions one can increase the waiting room capacity and adjust \(c_1\) and \(c_2\).

Fig. 3.
figure 3

(a) \(\eta (K(t),\lambda (t))\) in stationary case and (b) \(\eta (n,K(t),\lambda (t),t)\) in transient case for \(n=0\)

Full size image
Fig. 4.
figure 4

\(\eta (n,K(t),\lambda (t),t)\) in transient case for (a) \(n=5\) and (b) \(n=10\)

Full size image
Fig. 5.
figure 5

\(\eta (n,K(t),\lambda (t),t)\) with homogeneous servers for (a) \(n=0\) and (b) \(n=5\)

Full size image

Figures 3(a), (b) and 4(a), (b) show the minimum expected costs \(\eta (n,K(i), \lambda (i),i)\) in homogeneous and heterogeneous case. The first one deals with a stationary case. Here the initial state n is without any significance. The second, third, fourth one is dedicated to the transient solution of the optimizing problem with initial state n at each stage equal to 0, 5 and 10. In the following pictures the stages should be interpreted severally.

As one would expect, the queuing system with heterogeneous servers is superior in terms of running costs. A similar gap to the homogeneous costs as in Figs. 3(b), 4(a) and (b) can be seen for different initial states n at the end of every stage.

The Figs. 5(a), (b) and 6(a), (b) deal with homogeneous and number Figs. 7(a), (b) and 8(a) and (b) with heterogeneous operators. They picture the minimum expected costs \(\eta (n,K(i),\lambda (i),i)\) and \(\eta (K(i),\lambda (i))\) which were induced in the stationary and transient case respectively for chosen initial states.

Fig. 6.
figure 6

\(\eta (n,K(t),\lambda (t),t)\) with homogeneous servers for (a) \(n=9\) and (b) \(n=10\)

Full size image
Fig. 7.
figure 7

\(\eta (n,K(t),\lambda (t),t)\) with heterogeneous servers for (a) \(n=0\) and (b) \(n=5\)

Full size image
Fig. 8.
figure 8

\(\eta (n,K(t),\lambda (t),t)\) with heterogeneous servers for (a) \(n=7\) and (b) \(n=10\)

Full size image

At a close look at Figs. 5(a) up to 8(b) one can see that the costs induced by the transient queuing system converges to the expenses of the stationary model if and only if the computed optimal policies for this stage are the same.

7 Conclusions

In this paper we have provided performance analysis of the Markovian controllable queueing system with a time-dependent arrival rate. The control policy prescribes the number of allowable servers and is time-dependent as well. The transient and stationary analysis for homogeneous and heterogeneous systems with preemption is provided. It is shown that the optimal policy differs in transient and stationary case. For the same control policy the corresponding cost functions take very close values. It is confirmed that the heterogeneous queueing systems are superior in performance comparing to the homogeneous case.