Two Heads Are Better Than One ... And m

In the GCaP class, one of the homework exercises refers to a grocery store checkout where the customer arrival rate is 1 customer every 2 minutes and the mean service time for the cashier to ring up groceries is 1.5 minutes. The first question is: What is the mean residence time for each customer?

From Little's law, the utilization of the cashier is ρ = λ S = 0.5 × 1.5 = 0.75 or 75%. The residence time is given by R₁ = S/(1 − ρ) = 6.0 minutes.

A later question asks what happens if another cashier is employed to service the same aisle under the condition that the amount of traffic in the store is also doubled? In other words, the same waiting line now has 2 servers but the arrival rate into that waiting line has also increased by a factor of 2. The result is R₂ = S/(1 − ρ²) = 3.4286 minutes.

This result is surprising on several levels:

1. You'd expect that adding more capacity (2 servers) with the same arrival rate would produce a better residence time than for a single server. And it does. In that case, R₂ = 1.7455 minutes, which is smaller by better than a factor of 3.
2. Even with double the store traffic, the residence time per customer is better than the single cashier time (R₁) by almost a factor of 2. That is remarkable and unintuitive.
3. Is there a rule of thumb (RoT) here? Something like R₂ ≈ R₁/2.
   
4. And if that's true, can we generalize it to arbitrary m servers: R_m ≈ R₁/m?

These questions came up in the most recent GCaP class.

The answer to (3) is a qualified yes. It's like the old adage: two heads are better than one or, in this case, two cashiers. The answer to (4), however, is an unqualified no. The same RoT with m heads (or cashiers) is rot and does not produce a valid estimate. The following plot shows why.

The y-axis shows the residence time (R) normalized by the service time (S) plotted against the server load or utilization (ρ). Normalizing the residence time is a convenient way to compare across different server configurations without getting tied up in knots about the actual service time (Here, it's the same S = 1.5 minutes, anyway).

The blue curve toward the upper left is the single cashier case (aka M/M/1 in queueing parlance). The middle pair of curves (solid and dashed) pertain to the 2-cashier case (M/M/2). The third pair of curves are for 10-cashiers (M/M/10); chosen arbitrarily to represent more than 2 cashiers.

Notice first that all three solid curves approach R/S = 1 on the left side of the plot, i.e., at low cashier loads. That's because at low loads, the traffic in the store is so light that there are hardly any arrivals at the cashier, so no waiting line forms.

The dashed curve in the middle corresponds to half the M/M/1 residence time. You can see that although it's close to the actual M/M/2 residence time, it gets even closer for loads above 60% or 70%. We were considering 75% in the GCaP homework exercise above.

The dashed curve for M/M/10, however, is way off unless we are considering loads very close 100%, which is not much use for CaP predictions. Let's check that the curve itself is correct and we didn't make a mistake in calculating it. At ρ = 0.8, R/S = 5 for the M/M/1 curve and 1/10th of that value is R/S = 0.5, which is precisely on the dashed line for M/M/10. So, the dashed curve is correct.

The RoT R_m = R₁/m fails because it pushes the estimated residence time (the dashed curve) closer and closer to the x-axis as the number of cashiers (m) is increased. In other words, the estimated R/S ratio gets closer and closer to zero. Something like 100th of R₁ is going to be indistinguishable from the x-axis, for example. In reality, however, as the number of m servers is increased, the actual R/S ratio remains close to 1.0 (not zero) at higher and higher loads. That's the whole point of using a multiserver M/M/m queue.