5
$\begingroup$

Set-up: Travelers are waiting in line to be processed by immigration officers. There are N officers, each with their own counter. No assumptions about line-switching, constant processing speed, homogeneous processing speed, or homogeneous entrance rate of travelers.

Scenario A: Travelers line up in one of 3 lines, each line leading to one of the 3 counters.

Scenario B: Travelers line up in a single line. The person at the head of the line will be directed to the next available officer.

Additional assumption: All officers will be at 100% utilization rate.

I argue that average queue time will be the same in both scenarios. Many co-workers, friends, and the following quotes disagree and believe that Scenario B (single-line) will result in a shorter average queue time.

Who's right?

"Finally, a single-line, multiple-server system has better performance in terms of waiting times than the same system with a line for each server." - Reid, Sanders; Operations Management

"Research has proven that a single line, multi-server waiting system is faster than the multiple line approach." - http://blog.lavi.com/2014/08/07/single-line-queue/

"A Long Line for a Shorter Wait at the Supermarket" - http://www.nytimes.com/2007/06/23/business/23checkout.html

$\endgroup$
7
  • $\begingroup$ McDonald's had tested this and their data says that multiple lines results in shorter average wait times. However, some line waiters find multiple lines more stressful as they start to worry about being in the slower line. $\endgroup$
    – Doug M
    Commented Jan 27, 2017 at 23:03
  • 1
    $\begingroup$ I think your additional assumption weighs the scales somewhat — one likely advantage of Scenario B is that it does a better job of keeping the utilization rate up. $\endgroup$
    – Micah
    Commented Jan 27, 2017 at 23:11
  • $\begingroup$ They are certainly not always the same, as you can show directly from a simple M/M/1 type example. In general, you can upper-bound the total "unfinished work" $U_{single}(t)$ at any time $t$ in the single line system by $U_{single}(t) \leq U_{other}(t) + (n-1)L_{max}$, where $U_{other}(t)$ is the total unfinished work using any other (possibly multi-line) approach, $n$ is the number of (possibly time-varying) servers, and $L_{max}$ is the size of the largest job. This is equation (3) here: www-bcf.usc.edu/~mjneely/pdf_papers/… $\endgroup$
    – Michael
    Commented Jan 27, 2017 at 23:16
  • 1
    $\begingroup$ How can you assume $100$ percent utilization rate if there might be a point at which there are no more travelers? Note that in most such systems, it is never the case in Scenario B that a customer is waiting and a server is idle, but it is possible in Scenario A. $\endgroup$
    – Brian Tung
    Commented Jan 27, 2017 at 23:36
  • $\begingroup$ In light of that, I wonder, @DougM, how that result obtains. Maybe the servers work faster because they're competing (in a friendly way, one hopes) to clear their lines faster than their colleagues. $\endgroup$
    – Brian Tung
    Commented Jan 27, 2017 at 23:37

2 Answers 2

Reset to default
1
$\begingroup$

The average waiting time (mathematical expectation) is the same but the variation of waiting time for a single line is smaller than that of multiple lines (easy to demonstrate mathematically). Thus a risk-averse person would prefer a single line. The intuition is: if you end up in a faster server your time of waiting is much shortened; if you end up in a slow server then your time of waiting is much prolonged (multiplied by the number of people ahead of you plus you). For a single line, your waiting time is simply the server's speed, it is not exacerbated.

$\endgroup$
0
0
$\begingroup$

Note that in practice, using a single line causes extra time to get to the open counter. This decreases the effective utilization rate and, therefore, increases the queuing time.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .