7.1 \(G/G/c\) Queues in Tandem

Often, queues appear in sequence. In such cases, customers are interested in the mean sojourn (and waiting times) of their jobs in the entire chain. For this reason, we need a formula for dealing with networks.

Consider two \(G/G/1\) stations in tandem.1`In tandem’ means `in line’, i.e., one station after the other. Suppose we have the financial means to reduce the variability of the service times at one of the stations, but not at both. Clearly, we would like to improve the one that has the most impact on the total sojourn time in the line.

For the waiting time of the first machine, we can use Sakasegawa’s formula, but to apply this to the second machine, we need \(C^2_{a,2},\) i.e., the scv of the inter-arrival times at the second station. Now, noting that the output of the first machine forms the input of the second machine, it is clear that \(C^2_{a,2}=C^2_{d,1},\) where \(C^2_{d,1}\) is the scv of the inter-departure times of the first station.

Consider the inter-departure times of a \(G/G/1\) queue. Suppose that the utilization \(\rho\) is very high. Then the server will seldom be idle, so that most of the inter-departure times are equal to the service times of the first station. However, if the utilization is low, the server will be idle most of the time and the inter-departure times must be approximately equal to the inter-arrival times of the first station. By interpolating between these two extremes, we obtain the following approximation for the scv of the inter-departure times of a \(G/G/c\) queue:

\begin{equation*} C_{d,1}^2 \approx 1 + (1-\rho^2)(C_{a,1}^2-1) + \frac{\rho^2}{\sqrt{c}}(C_{s,1}^2-1). \end{equation*}

It is simple to see that for the \(G/G/1\) queue this reduces to

\begin{equation*} C_{d, 1}^2 \approx (1-\rho^2) C_{a, 1}^2 + \rho^2 C_{s, 1}^2. \tag{7.1.1} \end{equation*}

Next, we can use this formula for each station in the tandem network.

Combining Sakasegawa’s formula with this expression provides us with a very useful insight for a line of queues. If we reduce \(C^2_{s,1},\) i.e., the scv of service times at the first station, \(\E{\W_1}\) and \(C^2_{d,1}\) become smaller. Since \(C^2_{a,2}=C^2_{d,1},\) \(\E{\W_2}\) also becomes lower, but also \(C^2_{d,2},\) etc. In other words, the entire chain benefits from an improvement in service variability at the first station.2This makes an early station a natural candidate for improvement, but the best choice also depends on the stations’ loads and service variability.

TF 1.

Suppose that in a tandem network of \(G/G/c\) queues we can reduce \(C_{s}^2\) of just one station by a factor 2. To improve the average waiting time throughout the chain, it is best to reduce \(C_{s,1}^2.\)

Solution

Did you actually try? Write your solution down first for comparison.

Show the solution

False. Improving the first station helps downstream stations too, but need not give the largest reduction in total waiting time. For the parameters of Exercise 6, halving \(C_{s,1}^2\) reduces the approximate total waiting time by \(0.199\) hour, whereas halving \(C_{s,2}^2\) reduces it by \(0.260\) hour.

TF 2.

A production system consists of 2 stations in tandem. The first station has one machine, the second has two identical machines. Machines never fail and service times are deterministic. Jobs arrive at a rate of 1 per hour. The machine at the first station has a service time of 45 minutes per job, and a machine at the second station has a service time of 80 minutes. We claim that the second station is the bottleneck.

Solution

Did you actually try? Write your solution down first for comparison.

Show the solution

False. The second station has a utilization of \(80/(2*60) = 8/12 = 2/3,\) while the first has a utilization of \(45/60 = 3/4,\) which is higher.

TF 3.

Consider a network with \(n\) stations in tandem. At station \(i,\) the service times \(S_i\) for all machines at that station are the same and constant; station \(i\) contains \(N_i\) machines. The number of jobs required to keep all machines busy is \(N=\sum_{i=1}^n N_i,\) and the raw service time is \(T_0=\sum_{i=1}^n S_i.\) Thus, if the number \(w\) of jobs allowed in the system is greater than \(N,\) the number of jobs waiting somewhere in queue is \(w-N.\)

Solution

Did you actually try? Write your solution down first for comparison.

Show the solution

False. In general, the number of jobs in queue is much higher than \(w-N.\) Consider the example \(S_1=10\) and \(N_1=10,\) and \(S_2=1, N_2=20,\) and \(n=2.\) Even if station 1 is fully occupied, its output rate is only one job per unit time, so the mean number of busy machines at station 2 is only \(1\).

TF 4.

We have two \(M/M/1\) stations in tandem. Claim: The average queueing time for the network is given by

\begin{equation*} \E{\W} = \frac{\rho_1}{1-\rho_1} + \frac{\rho_2}{1-\rho_2}. \end{equation*}
Solution

Did you actually try? Write your solution down first for comparison.

Show the solution

False. This is incorrect: the units on the LHS and RHS do not match.

Exercise 5.

In a manufacturing setting, the Poisson process is not always a suitable model for the arrival process of jobs at a production station. Can you provide an example to show why this is the case?

Hint

Think about the inter-departure time of a machine that produces jobs every 10 minutes. What inter-arrival times will a downstream machine see?

Solution

Did you actually try? Write your solution down first for comparison.

Show the solution

When a station is kept busy and its service times are nearly constant, the jobs sent downstream have nearly equal inter-arrival times. But then the inter-arrival times are not well approximated by the exponential distribution, consequently, the arrival process is not well described by a Poisson process.

Exercise 6.

Consider two \(G/G/1\) stations in tandem. Suppose \(\lambda=2\) per hour, \(C_{a,1}^2=2,\) \(C_{s,1}^2=C_{s,2}^2 = 0.5,\) and \(\E{S_1}=20\) minutes, and \(\E{S_2}=25\) minutes. Compute \(\E\J = \E{\J_1}+ \E{\J_2}.\)

Solution

Did you actually try? Write your solution down first for comparison.

Show the solution

At station 1, \(\E{S_1}=1/3\) hour and \(\rho_1=\lambda\E{S_1}=2/3.\) Sakasegawa’s formula gives

\begin{align*} \E{W_1} &= \frac{C_{a,1}^2+C_{s,1}^2}{2} \frac{\rho_1}{1-\rho_1}\E{S_1} = \frac{2+1/2}{2}\cdot 2\cdot\frac13 = \frac56\text{ hour}, \\ \E{J_1} &= \E{W_1}+\E{S_1}=\frac76\text{ hours}. \end{align*}

The departures from station 1 are the arrivals at station 2. Therefore, \[ C_{a,2}^2=C_{d,1}^2 \approx (1-\rho_1^2)C_{a,1}^2+\rho_1^2C_{s,1}^2 =\rb{1-\frac49}2+\frac49\cdot\frac12 =\frac43. \] At station 2, \(\E{S_2}=5/12\) hour and \(\rho_2=\lambda\E{S_2}=5/6.\) Thus,

\begin{align*} \E{W_2} &\approx \frac{C_{a,2}^2+C_{s,2}^2}{2} \frac{\rho_2}{1-\rho_2}\E{S_2} =\frac{4/3+1/2}{2}\cdot5\cdot\frac5{12} =\frac{275}{144}\text{ hours}, \\ \E{J_2} &\approx \E{W_2}+\E{S_2} =\frac{335}{144}\text{ hours}. \end{align*}

Hence, the expected sojourn time in the two-station line is \[ \E J=\E{J_1}+\E{J_2} \approx\frac{503}{144}\text{ hours} \approx3.4931\text{ hours}. \]