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.2 In other words, try to improve from the start of the chain.
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
Solution, for real
True.
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
Solution, for real
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.
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 the queue is \(w-N\).
Solution
Solution, for real
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\). Clearly, 19 machines at station 2 are always empty.
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
Solution, for real
False. This is incorrect: the units on the LHS and RHS do not match.
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
Solution, for real
When service times at a station are nearly constant and the jobs of this station are sent to a second station for further processing, the inter-arrival times at the second station must be roughly equal. 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.
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
Solution, for real
First station 1.
labda = 2.0
S1 = 20.0 / 60
rho1 = labda * S1
ca1 = 2.0
cs1 = 0.5
EW1 = (ca1 + cs1) / 2 * rho1 / (1 - rho1) * S1
EJ1 = EW1 + S1
print(f"{EJ1=:.4f}")
EJ1=1.1667
Now station 2. We first need to compute \(C_{d1}^2\).
cd1 = (1 - rho1 ** 2) * ca1 + rho1 ** 2 * cs1
print(f"{cd1=:.4f}")
labda = 2
S2 = 25.0 / 60
rho2 = labda * S2
ca2 = cd1 # here we use our formula
cs2 = 0.5
EW2 = (ca2 + cs2) / 2 * rho2 / (1 - rho2) * S2
EJ2 = EW2 + S2
print(f"{EJ2=:.4f}")
print(f"{EJ1 + EJ2=:.4f}")
cd1=1.3333
EJ2=2.3264
EJ1 + EJ2=3.4931