줄 합치기의 함정: 손님이 줄을 보고 고르면 한 줄 서기가 진다

은행은 한 줄, 마트는 여러 줄 — 줄 합치기가 지는 순간

창구가 여럿일 때 줄을 어떻게 세울지를 두고 은행과 마트는 정반대의 답을 낸다. 은행은 창구가 여럿인데 줄은 하나고, 앞사람이 빠지면 맨 앞 손님이 그때 비는 창구로 간다. 마트는 계산대마다 줄이 따로 서고, 어느 줄에 설지는 손님이 고른다. 창구가 여러 개라는 조건은 똑같은데 답이 갈려 있다.

대기행렬 이론은 이 둘 중 한쪽 편을 확실히 든다. 창구 두 개에 창구당 부하 0.75, 그러니까 창구 하나가 처리할 수 있는 양의 75%만큼 손님이 들어오고, 그 손님은 줄 길이와 상관없이 무조건 선다고 두자. 시간은 서비스 한 번에 걸리는 시간을 1로 놓고 잰다. 이 조건을 우리 모형에 넣으면 줄에서 기다리는 시간이 3.00에서 1.29로 준다. 57.1% 감소다. 창구를 합치는 쪽이 이긴다는 이 결과는 교과서에 실려 있다.

바뀐 것은 손님 쪽이다. 콜센터는 예상 대기시간을 읽어 주고, 병원 접수 앱은 앞에 몇 명이 남았는지를 띄우고, 배달 앱은 도착 예정 시각을 먼저 보여 준다. 줄의 길이가 숫자로 보이면 손님은 그것을 보고 돌아설 수 있다. 그러면 앞의 계산이 딛고 선 전제 하나가 사라진다 — 손님이 무조건 줄을 선다는 전제다.

그래서 두 구조를 직접 굴려 봤다. 창구 4개, 창구당 도착률이 서비스율의 두 배인 조건에서 한 줄은 각자 줄보다 체류시간이 20.2% 길었고, 들어온 손님이 남긴 이득의 합인 후생은 73.2% 작았다. 창구를 32개로 늘리면 후생 격차는 95.5%까지 벌어진다. 반전이 시작되는 곳은 창구당 도착률이 서비스율을 넘어서는 부근이고, 그보다 한산하면 여전히 한 줄이 이긴다. 왜 한 줄이 원래 이기는지부터 짚어야 이 반전이 어디서 오는지가 보인다.

한 줄이 원래 이기는 이유

각자 줄에서 손해가 생기는 순간은 눈으로 짚을 수 있다. 한쪽 창구가 방금 손님을 보내고 비었는데 옆줄에는 사람이 서 있는 순간이다. 그 손님은 자기가 선 줄의 창구가 끝나기를 기다리고, 빈 창구는 그동안 아무도 처리하지 않는다. 처리 능력 하나가 놀고 있는데 기다리는 사람은 그대로 기다린다.

줄을 하나로 합치면 이 순간이 생기지 않는다. 맨 앞 손님은 어느 창구든 먼저 비는 곳으로 가면 되기 때문이다. 창구가 놀면서 동시에 누군가 기다리는 시간이 사라진다. 창구가 노는 것 자체가 없어지지는 않는데, 계에 있는 손님이 창구 수보다 적으면 남는 창구는 그대로 논다. 줄마다 제각각 들쭉날쭉하던 길이를 하나로 묶어 평평하게 만드는 셈이다.

그리고 이 이득은 창구가 많을수록 커진다. 줄이 여덟 개면 창구는 노는데 옆줄에는 사람이 서 있는 시간이 여덟 군데에서 따로 생기고, 합치면 그 여덟 군데가 한꺼번에 없어지기 때문이다. 합치는 이득이 계가 클수록 커진다는 것은 널리 받아들여진 생각이고, 논문 초록도 그 통념을 그대로 적어 둔 다음 뒤집는다. 뒤에서 보겠지만 그 통념이 무너지는 지점도 정확히 여기다.

효과는 이 모형에서도 그대로 나온다. 창구 두 개, 창구당 부하 0.75, 손님은 이탈 없이 무조건 서는 조건으로 두 구조를 계산해 봤다. 계에 머무는 전체 시간은 4.00에서 2.29로 줄어든다. 앞에서 본 줄 대기 3.00에서 1.29도 같은 계산에서 나온 값이다.

이 결과에는 조건이 하나 붙어 있다. 손님이 줄 길이와 무관하게 무조건 선다는 조건이다. 줄이 길면 안 서고 가 버리는 손님을 모형에 넣으면 계산이 어떻게 달라지는지, 그것이 이 글의 질문이다.

Sunar·Tu·Ziya는 2021년 논문에서 그 답을 내놨다. 손님이 지연에 민감해서 도착할 때 줄을 보고 들어갈지 정하는 계를 다뤘다. 어떤 조건에서는 각자 줄이 한 줄보다 평균 체류시간이 짧고 후생도 크다는 것이 초록의 주장이다. 논문 본문은 폐쇄 접근이라 조건식도 수치 실험도 열어 보지 못했다. 그래서 초록이 말하는 방향이 이 모형에서도 나오는지를 직접 굴려 확인하기로 했다.

손님의 규칙과 두 개의 문턱

손님에게 규칙을 하나만 준다. 도착해서 지금 줄을 보고 자기가 기다릴 시간을 셈한 다음, 그 시간이 서비스에서 얻는 이득보다 크면 돌아서고 작으면 들어간다. 계 전체가 어떻게 되는지는 이 규칙에 들어 있지 않다. 손님은 자기 앞의 숫자만 본다.

여기에 숫자를 붙인다. 서비스는 평균 1의 시간이 걸리고, 기다리는 비용은 단위시간당 1, 서비스에서 얻는 이득은 5.3으로 뒀다. 그러면 규칙은 기대 체류시간이 5.3을 넘으면 돌아선다는 한 줄로 정리된다. 창구는 4개, 도착은 창구당 부하 2.0으로 뒀다. 창구 하나가 처리할 수 있는 양의 두 배가 들어온다는 뜻이다.

두 구조에서 갈리는 것은 한 자리 뒤로 밀릴 때 늘어나는 대기다. 각자 줄에서는 내 앞에 한 명이 더 있으면 내 차례가 서비스 하나만큼, 그러니까 1.0만큼 뒤로 간다. 한 줄에서는 창구 네 개가 동시에 손님을 내보낸다. 한 자리가 0.25에 지나지 않는다. 아래 식에서 $n$은 도착했을 때 계에 이미 있는 손님 수, $k$는 창구 수, $\mu$는 창구 하나의 서비스율이다. $R$은 이득, $C$는 단위시간당 대기 비용이다.

식 1의 부등식이 그대로 문턱을 정한다. 각자 줄은 한 자리가 1.0이라 줄 하나에 5명이 차면 그다음 손님의 기대 체류가 6.0이 되고, 5.3을 넘으니 돌아선다. 한 줄은 한 자리가 0.25라 21명이 차야 그 지점에 닿는다. 문턱 5와 문턱 21, 이 차이가 나머지를 전부 만든다.

문턱이 네 배 넘게 벌어진 것은 창구 수 하나 때문이다. 한 줄에서는 앞에 한 명이 더 있어도 창구 네 개가 나눠 처리하니 내 차례는 4분의 1만큼만 밀린다. 손님이 보기에는 같은 5.3의 이득으로 훨씬 긴 줄을 감당할 수 있다는 뜻이고, 그래서 줄은 그만큼 길어진 다음에야 멈춘다.

이제 두 구조를 한 수로 비교해야 한다. 단위시간당 들어온 손님 수에 이득을 곱하고, 그동안 계 안에서 기다린 사람들의 대기 비용을 뺀다. 이 값을 후생이라 부르며, 들어온 손님들이 남긴 이득의 합과 같다.

식 2에서 $L$은 계에 있는 손님 수의 평균이다. 돌아선 손님은 이득도 대기 비용도 0이라 이 식에 들어오지 않는다. 문턱과 이 값을 구하는 코드는 짧다. 상태별 정상분포를 구해 평균을 내는 것이 전부다. 출력에는 두 구조의 문턱과 거기서 나오는 체류시간·후생이 나란히 찍힌다.

from math import floor
mu, C, R, k, a = 1.0, 1.0, 5.3, 4, 2.0

def chain(up, down):                       # 출생-사멸 사슬의 정상분포
    w = [1.0]
    for u, d in zip(up, down):
        w.append(w[-1] * u / d)
    return [x / sum(w) for x in w]

# 각자 줄: 줄 하나가 M/M/1, 도착률 a*mu. 상태 n 에서 기대 체류 (n+1)/mu
last = floor(R / C * mu) - 1                # 마지막으로 들어오는 상태
pd = chain([a * mu] * (last + 1), [mu] * (last + 1))
eff = a * mu * (1 - pd[-1])
L = sum(i * p for i, p in enumerate(pd))
print("각자 줄  문턱", last + 1, " W", round(L / eff, 2), " 후생", round((eff * R - C * L) * k, 2))

# 한 줄: M/M/k. 기대 체류 = 1/mu (n<k), (n-k+1)/(k*mu)+1/mu (n>=k)
soj = lambda n: 1 / mu if n < k else (n - k + 1) / (k * mu) + 1 / mu
N = 0
while soj(N) <= R / C + 1e-12:
    N += 1                                  # 상태 N 에서 처음 돌아선다
pp = chain([a * k * mu] * N, [min(i + 1, k) * mu for i in range(N)])
effp = a * k * mu * (1 - pp[-1])
Lp = sum(i * p for i, p in enumerate(pp))
print("한 줄    문턱", N, " W", round(Lp / effp, 2), " 후생", round(effp * R - C * Lp, 2))

각자 줄  문턱 5  W 4.16  후생 4.48
한 줄    문턱 21  W 5.0  후생 1.2

출력을 읽으면 이렇다. 한 줄은 체류시간이 4.16에서 5.0으로 20.2% 길고, 후생은 4.48에서 1.2로 73.2% 작다. 처리율은 오히려 한 줄이 조금 높다. 단위시간당 3.937명 대 4.0명이고, 돌아서는 손님의 비율도 0.508 대 0.5로 거의 같다. 손님을 조금 더 받고, 대기시간은 더 길고, 남는 이득은 4분의 1 남짓이다.

처리율과 체류시간을 같이 놓고 보면 이유가 드러난다. 들어온 사람 수가 거의 같은데 그 사람들이 계 안에 머무는 시간이 길어지면, 이득의 합에서 빼는 대기 비용이 그만큼 커진다. 한 줄이 손님을 더 받고도 후생에서 지는 이유가 여기 있다.

줄이 어디까지 차는가

문턱이 뒤로 밀린 결과는 줄의 길이 분포에 그대로 나온다. 계를 오래 굴리면 각 상태에 머무는 시간의 비율이 일정한 값으로 수렴하는데, 이것을 정상분포라 부른다. 재실 인원이 0명인 시간이 몇 퍼센트, 5명인 시간이 몇 퍼센트 하는 식이다.

그림 1의 왼쪽 봉우리가 각자 줄이다. 상태 0부터 5까지의 확률은 0.0159 · 0.0317 · 0.0635 · 0.1270 · 0.2540 · 0.5079다. 뒤로 갈수록 두 배씩 커지다 5에서 끊긴다. 줄이 꽉 차 있는 시간이 절반이라는 뜻인데, 그 꽉 찬 상태가 5명이다.

한 줄은 같은 모양이 훨씬 뒤에서 만들어진다. 재실 인원이 17명 이상인 시간의 비율이 0.9688이고, 문턱인 21명에 정확히 걸려 있는 시간이 0.5000이다. 열일곱 명 넘게 차 있는 것이 이 계의 평상시 모습이라는 말이다.

마지막으로 들어온 손님이 무엇을 남기는지를 보면 차이가 분명해진다. 각자 줄에서 마지막으로 들어오는 자리의 기대 체류는 5.00이고, 이득 5.3에서 0.30이 남는다. 한 줄에서 그 자리는 5.25이고 남는 것은 0.05다. 들어온 손님 한 명이 평균으로 남기는 잉여도 1.14 대 0.30으로 갈린다. 한 줄은 이득이 거의 남지 않는 자리까지 손님을 받아들이고, 각자 줄의 성긴 문턱은 그 자리에 닿기 전에 손님을 돌려세운다.

부하가 임계를 넘는 지점

지금까지는 부하 하나만 봤다. 창구당 부하를 0.25에서 4.0까지 훑으면 두 구조의 후생 곡선이 어디서 갈리는지 볼 수 있다. 나머지 조건은 창구 4개, 이득 5.3으로 그대로 뒀다.

한산할 때는 교과서가 맞다. 그림 2의 왼쪽 구간을 보면 창구당 부하 0.5에서 체류시간은 한 줄이 40.9% 짧고 후생은 23.7% 크다. 부하 1.0에서도 후생은 여전히 한 줄이 14.5% 크고, 체류시간은 0.3% 차이로 거의 같아진다.

역전은 그 바로 위에서 시작된다. 한 줄의 체류시간은 부하가 1.0을 넘자마자 각자 줄을 넘어선다. 후생이 뒤집히는 부하는 조금 더 위인 1.05와 1.1 사이에 있다. 0.05 간격으로 훑은 격자에서는 1.05와 1.1이 첫 역전 점이다. 부하 1.5에서 후생 격차는 이미 62.7%이고, 2.0에서 73.2%, 4.0에서 78.8%로 벌어진다. 창구당 도착률이 서비스율을 넘는 근처가 경계라는 것은 논문 초록이 적은 조건과도 같은 방향이다.

내려오는 속도도 두 구조가 다르다. 부하가 1.0에서 1.5로 올라가는 한 구간 동안 한 줄의 후생은 8.78에서 2.19로 주저앉는다. 같은 구간에서 각자 줄은 7.67에서 5.87로 완만하게 준다. 한 줄은 부하가 조금만 더 올라가도 문턱까지 줄이 차 버리고, 그 뒤로는 들어온 손님이 남기는 것이 거의 없기 때문이다.

창구가 늘수록 커지는 손실, 그리고 선택권의 역설

앞에서 말한 통념을 이제 수로 확인할 차례다. 창구가 많을수록 합치는 이득이 커진다던 그 이야기다. 부하를 2.0에 고정하고 창구 수만 1에서 32까지 늘려 보면 반대 방향이 나온다.

그림 3의 맨 위에는 이음선이 없다. 창구가 하나면 두 구조가 같은 계라서 후생도 1.12로 같기 때문이다. 둘로 늘리면 격차가 29.3%로 벌어지고, 넷에서 73.2%, 서른둘에서 95.5%가 된다.

각자 줄의 후생은 창구 수를 따라 35.86까지 올라간다. 한 줄의 후생은 창구가 둘에서 서른둘로 늘어나는 동안 1.2와 1.8 사이를 오르내릴 뿐이다. 한 줄의 문턱이 5에서 169로 밀려나는 동안, 늘어난 처리 능력이 전부 더 긴 줄에 흡수된 것이다.

체류시간 쪽 격차는 이만큼 벌어지지 않는다. 창구가 둘일 때 8.3%이던 것이 넷에서 20.2%, 여덟에서 23.2%, 서른둘에서 26.2%로 올라가다 거의 멈춘다. 후생 격차만 계속 벌어지는 것은 각자 줄의 후생이 창구 수를 따라 커지는 동안 한 줄의 후생이 제자리이기 때문이다.

줄을 효율적으로 채울수록 결과가 한 줄 쪽에 가까워진다. 창구를 노는 시간 없이 쓰는 설계일수록 손님이 줄의 더 뒤쪽까지 들어온다. 거기까지 들어온 손님이 남기는 것은 거의 없다.

언제 합치고 언제 나누나

세 가지가 동시에 성립할 때 줄 합치기가 진다. 창구당 도착률이 서비스율을 넘어야 한다. 서비스에서 얻는 이득이 기다리는 비용에 비해 충분히 커야 한다. 손님이 도착해서 줄을 보고 들어갈지 정할 수 있어야 한다. 하나라도 빠지면 결과가 도로 뒤집힌다.

대조군이 그 뒤집힘을 보여 준다. 손님이 줄 길이와 무관하게 무조건 서는 조건에서는 창구 두 개짜리 계에서 줄 대기가 3.00에서 1.29로 줄어, 합치는 쪽이 이긴다. 부하가 낮을 때도 마찬가지다. 창구당 부하 0.5에서는 한 줄의 후생이 23.7% 크다.

사람이 서는 줄이 없는 곳에도 같은 계산이 돈다. API 레이트리밋이 응답 헤더에 남은 요청 수를 실어 보내면, 클라이언트는 그 숫자를 읽고 재시도 간격을 늘리거나 요청을 아예 접는다. 도착해서 줄을 보고 돌아서는 손님과 규칙이 같다. 그래서 서버를 한 대기열 뒤에 묶을지 클라이언트마다 몫을 떼어 둘지도 여기서 갈린다.

콜센터의 예상 대기 안내나 병원 접수 앱의 대기 인원 표시에서도 같은 규칙이 작동한다. 기다리는 쪽이 남은 대기를 숫자로 읽을 수 있으면 그때부터 각자 자기 문턱을 갖는다. 그 문턱이 어디에 놓이는지는 창구를 어떻게 묶어 뒀는지가 정한다. 이 계산에서 각자 줄이 이긴 것도 문턱이 앞쪽에 있었기 때문이다.

그래서 줄 구조와 대기 정보는 한 벌로 정해야 한다. 세 조건이 함께 성립하는 계에서 합치는 설계는 대기시간을 늘리고 남는 이득을 깎는 쪽으로 작동한다. 이 모형에서 그 손실은 창구 4개에 73.2%, 32개에 95.5%였다.

이 결과가 닿는 범위는 창구가 사람인지 서버인지를 가리지 않는다. 기다리는 쪽에 남은 대기를 알려 주는 계라면 같은 뒤집힘이 따라붙고, 계가 클수록 합치는 쪽이 잃는 몫도 커진다. 대기 정보를 띄울지 정하는 순간에 자원을 어떻게 묶을지의 답도 함께 정해지는 셈이다.

한 줄 서기가 이긴다는 결론은 이 블로그의 옆줄이 빨라 보이는 이유 편에서 냈다. 그 글의 손님은 줄을 무작위로 골랐다. 손님이 줄 길이를 보고 고르기 시작하면 그 결론이 뒤집히는 구간이 생기고, 이 글이 잰 것이 그 구간이다.

더 읽기

• Sunar, N., Tu, Y., Ziya, S., "Pooled vs. Dedicated Queues when Customers Are Delay-Sensitive", Management Science 67(6), 2021, 3785–3802. https://doi.org/10.1287/mnsc.2020.3663 — 본문은 폐쇄 접근이라 이 글은 초록의 문장만 인용했다.
• 2017년 SSRN 판 요약 페이지 — https://kenaninstitute.unc.edu/publication/pooled-or-dedicated-queues-when-customers-are-delay-sensitive/ — 체류시간 80% 문구는 이 판 초록에만 있다.
• Naor, P., "The Regulation of Queue Size by Levying Tolls", Econometrica 37(1), 1969, 15–24. https://doi.org/10.2307/1909200 — 도착 시 줄을 보고 들어갈지 정하는 손님의 문턱을 다룬 원전.