1 Introduction

Time-varying queueing system has been widely used to model complex service systems such as communication [1,2,3], transportation [4,5,6], healthcare [7,8,9] etc. Steady-state analysis of time-varying general queueing systems in the literature mainly focuses on analytical approximation methods and simulation methods, since exact mathematical analysis of such systems is intractable. Transient analysis of general queueing models is considered challenging and becomes much more complex when we account for the arrival and/or service rates changing over time. Bertsimas and Mourtzinou [10] focused on transient version of Little’s Law, which is one of the fundamental principles of queueing theory. Fralix and Riano [11] extended the time-varying generalisation of Little’s Law and discussed it’s applications. Kim and Whitt [12] utilised time-varying Little’s Law(TVLL) to estimate and reduce the average waiting time in a queueing system. Whitt [13] discussed stabilising performance of a single server queueing system with time-varying arrival rate.

Over the last few decades, tandem queueing network has attracted a great deal of attention due to its widespread practical applications in real world such as communication networks, manufacturing systems, tollbooths, supply chains, traffic flows etc. Recent research on applications of tandem queueing networks includes the works of [14,15,16] and others.

The transient behaviour of a single server two-station tandem network is investigated in [17] and transient analysis of k-station tandem queuing model with load dependent service rates is discussed in [18]. Zychlinski et.al. [19] analysed tandem networks with general time-varying arrival rate and blocking, using time-varying fluid models.

In this study, we primarily consider a single server queueing system, where the arrivals constitute a time-varying counting process with general distributional assumptions. We also assume that the waiting space for the queue is unlimited, the service is time-dependant and is provided in the order of arrival. In the first section, we derive a transient distributional law that relates the virtual workload in the system to the waiting times of customers. This formula is shown to subsume Brumelle’s formula in [20] when we relax time-varying assumptions and go on with the stationary regime. In Sect. 3, we formulate transient performance measures such as, number of customers in the system and virtual workload, for a two station non-stationary Markovian tandem queueing network and we extend it to a k-station tandem queueing network in Sect. 4. In Sect. 5, we introduce an algorithm to obtain the transient performance measures discussed in previous section. In Sect. 6, we conduct a numerical study of three station tandem network model and analyse the transient behaviour of its performance measures.

2 Transient performance measures for single server queues

Consider a single server \(G_t/G_t/1\) queueing system with general time-varying arrival rate \(\lambda (t)\) and service rate \(\mu (t)\) and with First Come First Serve (FCFS) service discipline.

2.1 Number of customers

Let L(t) be the number of customers in the system at time t, \(t\ge 0\) and let W(s) be the waiting time of the customer who arrive at time s, \(0\le s\le t\). Then the time-varying number of customers in the system or transient generalisation of Little’s Law in [10] is,

$$\begin{aligned} E(L(t))=\int _{0}^{t}F_s^c(t-s) \lambda (s) ds \end{aligned}$$
(1)

where \(F_t(x)=P\{W(t)\le x|A_t\},~ x\ge 0\) is the cumulative distribution function of the waiting time for a customer who arrive at time t and \(F^c_t(x)=P\{W(t)> x|A_t\},~ x\ge 0\). \(A_t=\{A(t), t\ge 0\}\) is the arrival process to the system.

2.2 Virtual workload

Virtual workload process \(Z=\{Z(t), t\ge 0\}\) is the amount of work remaining in the system at time t. The following theorem gives an explicit integral formula for virtual workload in a single-server queueing system.

Theorem 1

Let Z(t) be the virtual workload in the system at time t and V(s) be the service requirement of the customer who arrive at time s. Then expected virtual workload at time t is,

$$\begin{aligned} E(Z(t))=\int _{0}^t F_s^c(t-s) \rho (s)ds+ \int _{0}^t \frac{E(V(s)^2)}{2}\lambda (s)ds \end{aligned}$$
(2)

Proof

Consider the interval [0, t]. We start with a reverse-time construction. Let \(T_{-k}(t )\) be the \(k^{th}\) arrival before time t. i.e., \(T_{-(k+1)}(t )<T_{-k}(t )\le t\), \(\forall ~ n\ge k\ge 1\). Let \(W_{-k}(t)=W(T_{-k}(t ))\) be the waiting time of the customer who arrive at time \(T_{-k}(t )\). Then the workload in the system at time t can be expressed as,

$$\begin{aligned} Z(t)= \sum _{k=1}^{\infty }\left( I_{\{W(T_{-k}(t )\ge t-T_{-k}(t )\}}V(T_{-k}(t )) + \frac{V(T_{-k}(t ))^2}{2}\right) \end{aligned}$$
(3)

where \(I_{\{W(T_{-k}(t )\ge t-T_{-k}(t )\}} = {\left\{ \begin{array}{ll} \text {1} &{}~\text {if}~\,W(T_{-k}(t )\ge t-T_{-k}(t )\\ \text {0} &{}~\text {otherwise} \\ \end{array}\right. }\). The first term in (3) gives the service time of the customer who arrive at \(T_{-k}(t )\) and waiting for service at time t. \(\frac{V(T_{-k}(t ))^2}{2}\) is the remaining service time of the customer in the server who arrive at \(T_{-k}(t )\). If the server is idle then this term becomes zero.

(3) can be written as,

$$\begin{aligned} Z(t)= \int _{0}^{t}\left( I_{\{W(s)> t-s\}}V(s)+\frac{V(s)^2}{2}\right) ~dA(s) \end{aligned}$$
$$\begin{aligned} =\int _{0}^{t}\left( I_{\{W(s )> t-s)\}}V(s)\right) ~dA(s)+\int _{0}^{t}\frac{V(s)^2}{2}~dA(s) \end{aligned}$$
(4)

By using Campbell–Mecke formula in [11] for taking expectations of stochastic integrals, we get

$$\begin{aligned} E(Z(t))=\int _{0}^{t}P{\{W(s )> t-s)\}}E(V(s))\lambda (s) ds+\int _{0}^{t}\frac{E(V(s)^2)}{2}\lambda (s) ds \end{aligned}$$
(5)

For \(F^c_s(x)=P\{W(s)> x|A_s\},~ x\ge 0\) and \(\rho (s)=\frac{\lambda (s)}{\mu (s)}\)

$$\begin{aligned} E(Z(t))=\int _{0}^t F_s^c(t-s) \rho (s)ds+ \int _{0}^t \frac{E(V(s)^2)}{2}\lambda (s)ds \end{aligned}$$

By the definition of squared coefficient of variation of service time, this can also be written as

$$\begin{aligned} E(Z(t))= & {} \int _{0}^t F_s^c(t-s) \rho (s)ds+ \int _{0}^t \frac{c_s^{2}+1}{2}~\frac{\lambda (s)}{\mu (s)^2}ds\\= & {} \int _{0}^t F_s^c(t-s) \rho (s)ds+ \int _{0}^t \frac{c_s^{2}+1}{2~\mu (s)}~\rho (s)ds \end{aligned}$$

\(\square\)

Remark 1

If we relax the time-varying conditions, we can see that the well-known Brumelle’s formula in [20] immediately follows from this result. i.e., If we assume that \({\tilde{Z}}= \{{\tilde{Z}}(t);t\ge 0\}\) is stationary, then

$$\begin{aligned} E({\tilde{Z}}(0))= & {} \int _{-\infty }^0 P_s({\tilde{W}}(s )> -s) \rho ~ ds+ \int _{-\infty }^0 \frac{c_s^{2}+1}{2\mu }\rho ~ds \\= & {} \rho \int _{-\infty }^0 P_0({\tilde{W}}(0 )> -s) ~ ds+ \int _{-\infty }^0 \frac{c_s^{2}+1}{2\mu }\rho ~ds \\ E({\tilde{Z}}(0))= & {} \rho E({\tilde{W}}(0))+\rho \frac{c_s^{2}+1}{2\mu } \end{aligned}$$

3 Transient performance measures for tandem queueing network of two stations

In this section, we develop transient performance measures for two-station tandem queueing network. We model a queueing network with two stations in tandem and unlimited waiting capacity at each queue, as illustrated in Fig. 1. Arrival and service processes in each queue in the system are time-dependant and we restrict the distributional assumptions associated with the system to Markovian(\(M_t/M_t/1\)) supposition.

Fig. 1
figure 1

A two station tandem queueing network model

Full size image

The model is characterised by the following parameters;

  1. 1.

    Arrival process \(A_i=\{A_i(t),t\ge 0\}\), \(A_i(t)\) represents number of arrivals at time t with \(E(A_i(t))=\lambda _i(t)\); where \(\lambda _i(t)\) is the arrival rate of station i at time t, for \(i=1,2\).

  2. 2.

    Service process \(V_i=\{V_i(t),t\ge 0\}\), \(V_i(t)\) is the service requirement of a customer who arrive at time t with service rate \(\mu _i(t)\)(mean=\(1/\mu _i(t)\)), \(i=1,2.\)

  3. 3.

    Transition from station 1 to station 2 occurs with probability p, \(0\le p\le 1\) and customer departs from station 1 with probability \(1-p\).

  4. 4.

    Number of servers, \(N_i=1\), \(i=1,2.\)

  5. 5.

    \(W_i(t)\) is the waiting time of a customer who arrive at time t, \(i=1,2.\)

  6. 6.

    \(Z_i(t)\) is the virtual workload in the \(i^{th}\) station at time t.

  7. 7.

    The counting process \(L_i=\{L_i(t),t\ge 0\}\), the number of customers present in station i waiting for service, \(i=1,2.\)

  8. 8.

    Departure process \(D_i=\{D_i(t),t\ge 0\}\), \(D_1(t)\) denote departure of customers from station 1 to station 2, therefore \(D_1(t)\) is merely the pattern of arrivals to the station 2(\(A_2(t)\)). \(D_2(t)\) denote the departures from station 2 and \(D_3(t)\) denote the departures from station 1 to out of the network.

    $$\begin{aligned} L_1(t)= & {} \int _{0}^{t}I_{\{W_1(s )> t-s)\}}~dA_1(s)\nonumber \\ E(L_1(t))= & {} \int _{0}^{t}(P{\{W_1(s )> t-s)\}})~\lambda _1(s)~ds \nonumber \\= & {} \int _{0}^{t}F_1^c(t-s)~\lambda _1(s)~ds\nonumber \end{aligned}$$
    (6)
    $$\begin{aligned} L_2(t)= & {} \int _{0}^{t} I_{\{W_2(s )> t-s)\}}~dD_1(s) \\E(L_2(t))= & {} \int _{0}^{t}(P{\{W_2(s )> t-s)\}})~\lambda _2(s)~ds \nonumber \\= & {} \int _{0}^{t}F_2^c(t-s)~p~\mu _1(s) ~ds \end{aligned}$$
    (7)

where \(I_{\{W_i(s )> t-s)\}}\) represents the number of customers entered at station i at time s and waiting for service at time t, \(0\le s\le t\) and \(F_i^c(t-s)=1-F_i(t-s)=P(W_i(s )> t-s))\). In equation (7) arrival rate to the station 2, \(\lambda _2(t)\) is replaced by \(p~\mu _1(s)\).

$$\begin{aligned} Z_1(t)= & {} \int _{0}^{t}I_{\{W_1(s )> t-s)\}}~V_1(s)~dA_1(s)+\int _{0}^{t}\frac{V_1(s)^2}{2}~dA_1(s) \nonumber \\ E(Z_1(t))= & {} \int _{0}^{t}F_1^c(t-s)~\frac{\lambda _1(s)}{\mu _1(s)}~ds+\int _{0}^t \frac{c_1^{2}+1}{2}~\frac{\lambda _1(s)}{\mu _1(s)^2}ds \end{aligned}$$
(8)

Similarly, for the second station,

$$\begin{aligned} Z_2(t)= & {} \int _{0}^{t}I_{\{W_2(s )> t-s)\}}~V_2(s)~dD_1(s)+\int _{0}^{t}\frac{V_2(s)^2}{2}~dD_1(s)\nonumber \\ E(Z_2(t))= & {} \int _{0}^{t}F_2^c(t-s)~ \frac{\lambda _2(s)}{\mu _2(s)}~ds+\int _{0}^t \frac{c_2^{2}+1}{2}~\frac{\lambda _2(s)}{\mu _2(s)^2}ds \nonumber \\= & {} p\Big (\int _{0}^{t}F_2^c(t-s)~ \frac{\mu _1(s)}{\mu _2(s)}~ds+\int _{0}^t \frac{c_2^{2}+1}{2\mu _2(s)}~ \frac{\mu _1(s)}{\mu _2(s)}~ds\Big ) \end{aligned}$$
(9)

where \(c_i^{2}\), \(i=1,2\) is the coefficient of variation of service process in station i.

4 A tandem network of k stations

We extend the two station non-stationary Markovian tandem model in section 3 to a k station tandem network model, as illustrated in Fig. 2. The transition probability \(p_{i,i+1}\) denotes the probability that a customer transfer from station i to station \(i+1\) after service, \(i=1,2,3,....,k-1\). Let \(A_i=\{A_i(t), t\ge 0\}\) and \(D_i=\{D_i(t), t\ge 0\}\), \(i=1,2,3,..., 2k-1\) be the arrival and departure processes respectively. Here \(D_i(t)\) for \(i= 1,3,5,....,2k-3\) are departure processes as well as arrival processes and \(D_i(t)\) for \(i= 2,4,6....,2k-2\) and \(2k-1\) are departures from the network.

Fig. 2
figure 2

A k station tandem queueing network model

Full size image
$$\begin{aligned} E(L_1(t))= & {} \int _{0}^{t}F_1^c(t-s)~\lambda (s)~ds\nonumber \\ E(L_i(t))= & {} \int _{0}^{t}F_i^c(t-s)~p_{i-1,i}~\mu _{i-1}(s) ~ds\nonumber \\ E(L_k(t))= & {} \int _{0}^{t}F_k^c(t-s)~p_{k-1,k}~\mu _{k-1}(s) ~ds \end{aligned}$$
(10)
$$\begin{aligned} E(Z_1(t))= & {} \int _{0}^{t}F_1^c(t-s)~\frac{\lambda _1(s)}{\mu _1(s)}~ds+\int _{0}^t \frac{c_1^{2}+1}{2}~\frac{\lambda _1(s)}{\mu _1(s)^2}ds\nonumber \\ \nonumber \\ E(Z_i(t))= & {} p_{i-1,i}\Big (\int _{0}^{t}F_i^c(t-s)~\frac{\mu _{i-1}(s)}{\mu _i(s)}~ds+\int _{0}^t \frac{c_i^{2}+1}{2\mu _i(s)}~\frac{\mu _{i-1}(s)}{\mu _i(s)} ~ds \Big ) \nonumber \\ E(Z_k(t))= & {} p_{k-1,k}\Big (\int _{0}^{t}F_k^c(t-s)~ \frac{\mu _{k-1}(s)}{\mu _k(s)}~ds+\int _{0}^t \frac{c_k^{2}+1}{2\mu _k(s)}~\frac{\mu _{i-1}(s)}{\mu _i(s)}~ds\Big ) \end{aligned}$$
(11)

where \(c_i^{2}\) \(i=1,2,3,....,k\) is the coefficient of variation of service process in station i

Remark 2

The set of equations (10) and (11) derived in this section can be easily generalised to k-station tandem queueing network with non-stationary non-Markovian ( \(G_t/G_t/1\)) queues by proceeding on similar lines as outlined above.

5 Algorithm for k station tandem model

In this section, we propose an algorithm to obtain transient performance measures such as number of customers and average virtual workload for a k-station tandem network model with non-stationary Markovian queues. Here we consider some prerequisites for developing the algorithm.

  • We utilise the principle of rate-matching control, discussed in [13], for choosing the service rate function. In rate-matching control, we choose the service rate to be proportional to the arrival rate, for fixed traffic intensity \(\rho\). ie., for a given traffic intensity \(\rho _i\), the service rate becomes,

    $$\begin{aligned} \mu _i(t)\equiv \lambda _i(t)/\rho _i,~~~i=1,2,3,....,k~~~t\ge 0 \end{aligned}$$
    (12)

  • For an \(M_t/M_t/1\) model, distribution of the waiting time W(u), i.e., the probability that the waiting time of a customer who arrives at u, is larger than x is,

    $$\begin{aligned} P(W(u)>x)=\rho e^{-(1-\rho )\Lambda _t(u)/\rho } \end{aligned}$$
    (13)

    where \(\Lambda _t(u)=\Lambda (t+u)-\Lambda (u)\), \(\Lambda (.)\) is the cumulative arrival rate function defined as,

    $$\begin{aligned} \Lambda (u)=\int _0^u \lambda (r) dr,~~ r\ge 0 \end{aligned}$$

    and \(\Lambda _t(u)\) need to be strictly increasing and continuous, see [13]. Therefore, the expected waiting time, E(W(t)) in the \(M_t/M_t/1\) model is,

    $$\begin{aligned} E(W(t))=\int _{0}^{\infty } P(W(u)>x)=\rho \int _{0}^{\infty } e^{-(1-\rho)\Lambda _{t}(u)/\rho} \end{aligned}$$
    (14)

  • Probability that the waiting time of a customer who arrives at time s will be greater than \(t-s\) is,

    $$\begin{aligned} P(W(s)>t-s)=\rho e^{-(1-\rho )\Lambda _t(s)/\rho } \end{aligned}$$

    where \(\Lambda _t(s)=\Lambda (t)-\Lambda (s)\). Here for station i, \(\Lambda _{t,i}(s)=\Lambda _i(t)-\Lambda _i(s)\) and

    $$\begin{aligned} P(W_i(s)>t-s)=\rho _i e^{-((1-\rho _i)\Lambda _{t,i}(s))/\rho _i} ~~~i=1,2,3,....,k \end{aligned}$$

  • The term squared coefficient of variation of service time(\(c^2\)) is involved in (11). Since we considered non-stationary Markovian queueing model, \(c^2\) can be assumed to be 1.

5.1 Algorithm

A general framework of the algorithm for obtaining transient performance measures in a k-station tandem network model is presented in this section.

figure a

Algorithm 1

6 Numerical study

In this section, we discuss two examples of tandem networks. We utilise the algorithm developed in previous section to compute performance measures and study the transient behaviour of the models. Specifically, we analyse the effects of traffic intensity on the transient performance measures.

6.1 A three-station example

Here we consider a three-station tandem network of non-stationary Markovian \(M_t/M_t/1\) queues with following characteristics;

  • Let the external arrival rate to station 1, \(\lambda _1(t)\) be the identity function, t, \(t\ge 0\).

    $$\begin{aligned} \lambda _i(t)=p_{i-1,i} \mu _{i-1}(t),~~~ i=2,3, \end{aligned}$$
    (15)

    where \(\mu _i(t)\), \(i=1,2,3\) is the service rate function obtained from (12) and \(p_{i-1,i}\) is the transition probability from station i to \(i+1\), \(i=1,2\). Here we take \(p_{i-1,i}=p=0.75\), ie., equal probability for all transitions.

  • In this study, we consider four cases, A, B, C and D by taking arbitrary values for traffic intensities, as shown in Table 1. Stations with traffic intensities close to 1 are considered bottleneck stations. Case D is more challenging because of two bottleneck stations, whereas all the other cases have only one bottleneck station.

Table 1 Four cases of traffic intensities
Full size table
Fig. 3
figure 3

Average number of customers at time t for four different cases considered in this study

Full size image

The results are illustrated by implementing algorithm 1 in Wolfram Mathematica 12.3. Fig. 3 presents the time-varying number of customers in each station in the three-station tandem network. As can be seen from the figure, stations with high traffic intensity have a large number of customers in the queue. Fig. 4 shows the average virtual workload in each station. The workload is heavy for bottleneck stations when compared to other stations. If the bottleneck station is located in the first position, the workload becomes heavier than if it is located in the second or third position.

Fig. 4
figure 4

Average workload at time t for different cases. Here blue, red and green figures represent station 1, station 2 and station 3 respectively

Full size image

6.2 A five-station example

We consider another example of five-station tandem network model with similar external arrival rate and transition probability. We look at four different cases of traffic intensity for each station and summarised in Table 2. As in the previous example, Fig. 5 illustrates the time-varying number of customers and Fig. 6 presents the average virtual workload in the five-station tandem queueing network.

Table 2 Four cases of traffic intensities
Full size table
Fig. 5
figure 5

Average number of customers at time t for four different cases considered in this study

Full size image
Fig. 6
figure 6

Average workload at time t for different cases. Here blue, red, green, brown and purple figures represent stations 1, 2, 3, 4 and 5 respectively

Full size image

The results from the numerical study provide insight into the relation between location of bottleneck stations and transient performance measures. It is evident in this example that if the bottleneck station is located first, the workload in both the first station and the next stations will be heavy. As a result, customers will have to spend more time in the system. Interestingly, when the bottleneck station is at the end of the series, there is no effect on the average workload in the previous stations; hence, customers can obtain service without any delay. Whereas, when there are multiple bottleneck stations within the system, the average workload is consistently high.

7 Conclusion

In this paper, we discussed some transient distributional laws that characterise the performance of a time-varying tandem queueing network. To derive the virtual workload in the system, we initially considered a general single server queueing system with unlimited waiting capacity. Subsequently, we extended our model from single server queue to tandem queueing network of k servers and formulated transient performance measures such as, number of customers and average virtual workload in stations. We further introduced an algorithm that  provides a general framework for obtaining transient performance measures in a k-station tandem network, and we implemented the algorithm through numerical study. The results clearly demonstrated the relationship between performance measures and traffic intensities.

Although time-varying queueing systems are widely used in many real life applications, their transient analysis requires more attention in the queueing systems literature. Through this paper, we have attempted to advance the field further. Implementation of finite buffer case and extending the results to different queueing disciplines are some interesting avenue for future research.