대기행렬 이론

편집 역사 토론
통계 시뮬레이션 마지막 수정: 2026-09-14 04:12:40

1. 개요[편집]

대기행렬 이론
Queueing Theory
다루는 것도착 · 서비스 · 대기의 확률 모형
표기법켄들 표기 A/S/c/K/N/D
시조A. K. 얼랑(1909) — 코펜하겐 전화국의 회선 수 계산
만능 항등식리틀의 법칙 $L=\lambda W$ — 분포를 안 가린다
주인공 결론$\rho \to 1$ 에서 대기가 발산한다
해석해의 끝우선순위 · 유한버퍼 · 재작업이 끼면 곧바로 이산사건 시뮬레이션

대기행렬 이론(queueing theory)은 손님이 무작위로 도착하고 서비스에 걸리는 시간도 무작위인 계에서, 줄의 길이와 기다리는 시간이 어떤 확률분포를 따르는지를 다루는 응용확률론의 한 갈래다. 은행 창구, 콜센터, 라우터의 패킷 버퍼, 공장의 공정 간 재공품, 응급실 침상 — 「받는 쪽 용량이 유한한데 오는 쪽이 제멋대로」인 계는 전부 같은 수식으로 서술된다.

이 문서가 끝까지 밀고 갈 결론은 하나다. 가동률을 100%에 붙이려 하면 대기시간이 발산한다. 평균적으로는 처리 능력이 수요보다 크더라도, 도착과 서비스가 흔들리는 한 줄은 생긴다. 설비를 놀리지 말라는 관리 본능과 정면으로 충돌하는 결론이고, 그래서 이 이론의 실용적 가치는 대부분 “왜 우리 라인이 가동률 95%에서 갑자기 지옥이 됐는가”를 설명하는 데서 나온다.1

2. 켄들 표기[편집]

켄들(D. G. Kendall, 1953)이 제안하고 리 등이 확장한 A/S/c/K/N/D 여섯 칸이 표준이다. 뒤 세 칸은 기본값이면 생략한다.

칸뜻흔한 값
A도착 간격 분포M(지수 = 푸아송 도착) · D(결정론적) · G(일반) · Ek_k(얼랑)
S서비스 시간 분포같은 기호 체계
c서버 수1, c, ∞\infty
K계 전체 수용량(버퍼 포함)기본 ∞\infty
N손님 모집단 크기기본 ∞\infty
D대기 규율FCFS(기본) · LCFS · 우선순위 · 처리공유

M은 memoryless(무기억)의 M이다. 도착 간격이 지수분포라는 말은 도착 사건이 푸아송 과정을 이룬다는 말과 같고, “지금까지 3분 기다렸다”는 정보가 다음 도착까지의 분포를 전혀 바꾸지 못한다는 뜻이다. 이 성질 하나 덕분에 계의 상태를 「지금 몇 명 있는가」 하나로 줄일 수 있고, 그러면 전체가 마르코프 연쇄가 되어 손으로 풀린다. 무기억성을 버리는 순간 상태에 「이 손님이 서비스받은 지 얼마나 됐는가」가 추가되고, 해석해는 대개 거기서 끝난다.

3. M/M/1 — 이 분야의 수소 원자[편집]

도착률 λ\lambda, 서비스율 μ\mu, 서버 하나, 무한 버퍼, 선착순. 가동률(traffic intensity)을

ρ=λμ\rho = \frac{\lambda}{\mu}

로 두면 ρ<1\rho<1 일 때만 정상상태가 있다. 계에 nn 명 있을 확률 PnP_n 은 인접 상태 사이의 확률흐름이 균형을 이룬다는 조건 λPn=μPn+1\lambda P_n = \mu P_{n+1} 에서 바로 나온다. 등비수열이므로 정규화까지 끝내면

Pn=(1−ρ)ρ n,n=0,1,2,…P_n = (1-\rho)\rho^{\,n}, \qquad n = 0,1,2,\dots

이다. 계에 아무도 없을 확률이 1−ρ1-\rho 라는 것과, 손님 수가 기하분포를 따른다는 것이 한 줄에 다 들어 있다. 평균 재계 인원은

L=∑n≥0nPn=ρ1−ρ,Lq=ρ21−ρL = \sum_{n\ge 0} n P_n = \frac{\rho}{1-\rho}, \qquad L_q = \frac{\rho^{2}}{1-\rho}

이고(LqL_q 는 서비스 중인 사람을 뺀 대기열 길이), 시간으로 바꾸면

W=1μ−λ,Wq=ρμ−λW = \frac{1}{\mu-\lambda}, \qquad W_q = \frac{\rho}{\mu-\lambda}

가 된다.

3.1. 리틀의 법칙[편집]

LL 과 WW 를 잇는 다리가 리틀의 법칙이다.

L=λWL = \lambda W

무서운 점은 이 식이 M/M/1에 특화된 결과가 아니라는 것이다. 도착 과정이 무엇이든, 서비스 분포가 무엇이든, 대기 규율이 무엇이든, 계가 안정적이고 장기 평균이 존재하기만 하면 성립한다. 증명은 사실상 「누적 도착 곡선과 누적 이탈 곡선 사이의 면적을 두 방향으로 세어 보는 것」이고, 확률 가정이 아예 안 들어간다.2 실무에서는 이 식을 측정 도구로 쓴다 — 창고의 평균 재고를 세고 출하율로 나누면 물건이 창고에 머무는 평균 시간이 나온다. 재고 회전율 계산이 바로 리틀의 법칙이다.

4. ρ→1\rho \to 1 — 가동률 100%를 노리면 안 되는 이유[편집]

L=ρ/(1−ρ)L=\rho/(1-\rho) 에서 ρ\rho 를 1에 붙여 보자.

가동률 ρ\rho평균 재계 인원 LL평균 대기 WqW_q (서비스 시간 배수)
0.501.01.0
0.804.04.0
0.909.09.0
0.9519.019.0
0.9999.099.0

가동률을 0.5에서 0.9로 1.8배 올렸더니 줄은 9배가 됐다. 곡선이 1/(1−ρ)1/(1-\rho) 라 마지막 몇 %가 전부를 먹는 것이다. 관리자가 “설비를 놀리지 마라”를 밀어붙여 ρ\rho 를 0.95로 맞추면, 도착률이 5%만 더 늘어도(ρ=0.9975\rho=0.9975) 대기가 네 배로 뛴다. 여유 용량은 낭비가 아니라 대기시간을 사는 값이라는 것이 이 이론의 가장 비싼 교훈이고, 응급실이 평시 점유율 85%를 넘기지 않으려 하는 것도, 네트워크 링크를 70%에서 증설하는 것도 전부 이 쌍곡선 때문이다.

여기에 한 가지가 더 붙는다. ρ<1\rho<1 이어도 유한한 관측 구간에서는 일시적으로 도착이 몰려 줄이 길어지고, 그 줄은 ρ\rho 가 1에 가까울수록 늦게 빠진다. 정상상태 평균이 유한하다는 말과 “오늘 오후 두 시에 줄이 안 밀린다”는 말은 다른 이야기다.

M/M/c 대기행렬을 next-event 이산사건 시뮬레이션으로 돌린다 — 지수 도착·서비스를 역변환 난수(고정 시드 LCG)로 뽑고 ∫n dt 를 누적해 시간가중 평균 L̄ 을 해석해 L = ρ/(1−ρ) 와 대질한다. ρ 를 올리면 줄이 폭발할 뿐 아니라 그 평균을 재는 일까지 어려워진다: 20만 이벤트·시드 24개에서 |오차| 중앙값이 ρ=0.5 의 0.47 % 에서 ρ=0.9 4.28 %, ρ=0.95 7.29 % 로 커진다.

5. 평균만 보면 안 된다 — 대기시간의 분포[편집]

지금까지 구한 것은 전부 평균이다. 그런데 서비스 수준 협약(SLA)은 평균으로 쓰이지 않는다. “평균 응답 200 ms”가 아니라 “95%가 500 ms 이내”로 쓰인다. 다행히 M/M/1 선착순에서는 분포도 닫힌 형태로 나온다. 손님이 계에 머무는 총 시간 TT 는

P(T>t)=e−(μ−λ)tP(T>t)=e^{-(\mu-\lambda)t}

즉 평균 1/(μ−λ)1/(\mu-\lambda) 인 지수분포를 따른다. 도착한 손님이 보는 인원이 기하분포이고 각 서비스가 지수분포라 그 합이 다시 지수가 되기 때문이다. 지수분포의 95 백분위수는 평균의 약 3배(−ln⁡0.05≈3.0-\ln 0.05 \approx 3.0), 99 백분위수는 약 4.6배다.

실무 감각으로 이건 꽤 무서운 결과다. 평균을 목표의 1/3 아래로 눌러야 95% 목표가 겨우 맞는다. 게다가 ρ\rho 가 커지면 평균과 백분위수가 같은 비율로 함께 커지므로, 가동률을 올리면 꼬리가 평균보다 더 빨리 나빠지는 것이 아니라 꼬리 전체가 통째로 쌍곡선을 타고 올라간다. 웹 서비스의 p99 지연이 트래픽 증가 구간에서 갑자기 무너지는 현상을 설명할 때 가장 먼저 꺼내는 그림이 이것이다. 서비스 시간 분포가 지수가 아니면 꼬리는 더 나빠지며, 특히 서비스 시간이 두꺼운 꼬리를 가지면 평균 대기가 아예 무한대가 되는 경우도 있다.

6. 유한 버퍼와 손실[편집]

버퍼가 무한하다는 가정은 수학적 편의다. 실제 라우터의 큐, 대기실의 의자, 창고의 바닥은 유한하다. 계 전체 수용량이 KK 인 M/M/1/K 에서는 정규화가 유한 등비합이 되어

Pn=(1−ρ)ρ n1−ρ K+1,n=0,…,KP_n=\frac{(1-\rho)\rho^{\,n}}{1-\rho^{\,K+1}},\qquad n=0,\dots,K

가 되고, PKP_K 가 차단확률(손님이 못 들어오고 돌아갈 확률)이다. 유한 버퍼의 좋은 점은 ρ≥1\rho\ge1 이어도 정상분포가 존재한다는 것 — 과부하가 무한 대기가 아니라 손실로 나타나기 때문이다. 대기시간이 발산하는 대신 손님을 잃는 것이고, 설계자가 실제로 고르는 것은 이 둘 사이의 교환비다.

이 교환이 가장 노골적인 곳이 패킷 네트워크다. 버퍼를 크게 잡으면 손실률은 떨어지지만 큐가 길어져 지연이 늘고, 지연이 늘면 혼잡 제어가 혼잡을 늦게 알아채 상황이 더 나빠진다. “버퍼를 넉넉히”라는 직관이 오히려 성능을 망치는 이 현상에는 버퍼블로트라는 이름까지 붙어 있다. 큐 이론이 설계 지침을 뒤집은 드문 사례다.

7. M/M/c와 얼랑 C — 서버를 늘리면[편집]

콜센터 상담원 cc 명이 하나의 공용 줄에서 손님을 받는 모형이 M/M/c다. 제공부하(offered load) a=λ/μa=\lambda/\mu 를 두고 ρ=a/c<1\rho=a/c<1 이라 하면, 도착한 손님이 기다려야 할 확률이 얼랑 C 공식이다.

C(c,a)=acc!11−ρ∑n=0c−1ann!+acc!11−ρC(c,a)=\frac{\dfrac{a^{c}}{c!}\dfrac{1}{1-\rho}}{\displaystyle\sum_{n=0}^{c-1}\frac{a^{n}}{n!}+\frac{a^{c}}{c!}\dfrac{1}{1-\rho}}

평균 대기는 Wq=C(c,a)/(cμ−λ)W_q = C(c,a)/(c\mu-\lambda) 로 깔끔하게 떨어진다. 버퍼가 아예 없어서 꽉 차면 손님이 돌아가는 M/M/c/c 손실계에서는 대신 얼랑 B 공식 B(c,a)=ac/c!∑n=0can/n!B(c,a)=\dfrac{a^{c}/c!}{\sum_{n=0}^{c} a^{n}/n!} 이 차단확률을 준다. 얼랑이 1917년에 유도한 이 식이 20세기 내내 전화 교환기의 회선 수를 정했다.

실무 감각으로 기억할 결론은 제곱근 인력배치 법칙이다. 목표 서비스 수준을 유지하려면 상담원 수를

c≈a+βac \approx a + \beta\sqrt{a}

로 두면 된다(β\beta 는 서비스 수준이 정하는 1 안팎의 상수). 부하가 100 에르랑이면 10명쯤, 400 에르랑이면 20명쯤의 여유만 얹으면 된다는 뜻으로, 규모가 커질수록 필요한 여유 비율이 줄어든다. 작은 창구 열 개를 합쳐 큰 창구 하나로 만들면 같은 인원으로 대기가 줄어드는 「풀링 이득」의 정체가 이것이다.3

8. M/G/1 — 분산이 대기를 키운다[편집]

서비스 시간 분포를 지수에서 풀어 주면 폴라첵-힌친 공식(Pollaczek–Khinchine)이 나온다. 평균 E[S]E[S], 2차 적률 E[S2]E[S^2] 인 임의 분포에 대해

Wq=λE[S2]2(1−ρ)=ρ1−ρ⋅1+Cs22⋅E[S]W_q=\frac{\lambda E[S^{2}]}{2(1-\rho)} =\frac{\rho}{1-\rho}\cdot\frac{1+C_s^{2}}{2}\cdot E[S]

이며 Cs2=Var⁡(S)/E[S]2C_s^2=\operatorname{Var}(S)/E[S]^2 는 서비스 시간의 변동계수 제곱이다. 오른쪽 형태가 이 문서에서 두 번째로 중요한 식이다. 세 인자가 혼잡 × 변동성 × 시간 으로 정확히 분리된다.

  • Cs2=1C_s^2=1(지수) → M/M/1의 Wq=ρE[S]/(1−ρ)W_q=\rho E[S]/(1-\rho) 를 그대로 회복한다.
  • Cs2=0C_s^2=0(M/D/1, 서비스가 항상 정확히 같은 시간) → 대기가 정확히 절반이 된다.
  • Cs2=4C_s^2=4 (가끔 아주 오래 걸리는 작업이 섞임) → 대기가 2.5배가 된다.

평균 처리 시간을 한 톨도 줄이지 않고 분산만 줄여도 대기가 반 토막 난다는 것. 표준작업·배치 크기 축소·정비 계획화 같은 린 생산의 처방이 왜 먹히는지에 대한 정량적 근거가 여기 있다. 반대로 “평균 처리시간은 개선했는데 체감이 더 나빠졌다”는 흔한 현장 보고는 대개 분산이 커진 경우다.

도착 쪽까지 일반화하면 닫힌 해는 사라지고 킹만 근사(G/G/1)로 간다.

Wq≈Ca2+Cs22⋅ρ1−ρ⋅E[S]W_q \approx \frac{C_a^{2}+C_s^{2}}{2}\cdot\frac{\rho}{1-\rho}\cdot E[S]

생산관리 교과서가 VUT 공식(Variability × Utilization × Time)이라 부르는 것이 이것이다. 정확한 값은 아니지만 ρ→1\rho\to1 에서 점근적으로 맞고, 세 손잡이(변동성·가동률·처리시간) 중 어디를 돌릴지 결정하는 데는 충분하다.

9. 순서를 바꾸면 — 우선순위와 보존 법칙[편집]

선착순은 공평하지만 최적이 아니다. 응급실이 도착 순서로 진료한다면 그건 의료 사고다. 손님을 k=1,…,Kk=1,\dots,K 등급으로 나누고 낮은 번호를 먼저 받는 비선점 우선순위 M/G/1에서, 등급 kk 의 평균 대기는 코브햄의 공식으로 나온다.

Wq,k=W0(1−σk−1)(1−σk),W0=∑iλiE[Si2]2,σk=∑i≤kρiW_{q,k}=\frac{W_0}{(1-\sigma_{k-1})(1-\sigma_k)},\qquad W_0=\sum_i \frac{\lambda_i E[S_i^2]}{2},\quad \sigma_k=\sum_{i\le k}\rho_i

W0W_0 는 도착 순간 이미 서버에 남아 있는 일의 평균량(잔여 작업)이고, 분모의 σ\sigma 는 자기보다 우선인 등급들의 부하만 센다. 즉 1등급 손님에게 2등급 이하는 거의 존재하지 않는 것과 같다.

그런데 공짜는 없다. 클라인록의 보존 법칙이 그 값을 못 박는다. 서버가 일을 놀리지 않는 한(work-conserving), 비선점 규율을 어떻게 바꾸든

∑kρkWq,k=일정\sum_k \rho_k W_{q,k} = \text{일정}

이 변하지 않는다. 순서를 바꾸는 것은 대기를 없애는 것이 아니라 누구에게 떠넘길지 고르는 것이다. 1등급의 대기를 줄인 만큼 정확히 부하 가중치로 환산해 아래 등급이 뒤집어쓴다. 이 한 줄을 알고 있으면 “우선순위 큐를 넣어 성능을 개선하겠다”는 제안을 정확히 평가할 수 있다 — 개선되는 것은 총량이 아니라 배분이다.

그렇다면 총량을 줄일 방법은 없나. 있다. 목표를 평균 대기로 잡으면 짧은 작업 우선(SPT)이 최적이고, 등급마다 지연 비용 ckc_k 가 다르면 ckμkc_k\mu_k 가 큰 순서로 처리하는 cμc\mu 규칙이 가중 평균 비용을 최소화한다. 보존 법칙과 모순되지 않는다 — 보존되는 것은 ρ\rho 로 가중한 합이고, SPT는 그 가중치가 작은(짧은) 작업을 앞으로 보내 단순 평균을 줄이는 것이기 때문이다. 대가는 긴 작업의 기아(starvation)이고, 그래서 실무 스케줄러는 대기 시간에 따라 우선순위를 올려 주는 에이징을 끼워 넣는다.

10. 줄이 여럿일 때 — 대기행렬망[편집]

공정이 줄줄이 이어진 공장이나 라우터가 얽힌 네트워크는 노드 하나가 아니라 망이다. 겁나 보이지만 놀라운 결과가 하나 있다. 버크의 정리(1956)에 따르면 정상상태 M/M/c의 출발 과정은 다시 푸아송 과정이고, 그 덕분에 개방형 잭슨 망(Jackson, 1957)에서는 각 노드의 인원 분포가 마치 독립적인 M/M/1인 것처럼 곱 형태로 분리된다. 각 노드의 실효 도착률은 흐름 방정식

λj=γj+∑iλipij\lambda_j=\gamma_j+\sum_i \lambda_i p_{ij}

를 풀어 얻고(γj\gamma_j 는 외부 도착, pijp_{ij} 는 라우팅 확률), 그다음은 노드마다 M/M/1 공식을 적용하면 끝이다. 곱 형태는 노드들이 실제로 독립이라는 뜻이 아니다 — 정상분포만 그렇게 인수분해된다는 대수적 사실이다.

문제는 이 우아함이 지독하게 깨지기 쉽다는 것이다. 버퍼가 유한해서 뒷 공정이 막히면 앞 공정이 멈추는 블로킹이 생기는 순간, 도착 과정이 더 이상 푸아송이 아니고 곱 형태도 무너진다. 실제 공장은 거의 전부 유한 버퍼다.

11. 해석해가 끝나는 곳[편집]

위 공식들이 다루는 세계는 생각보다 좁다. 다음 중 하나만 들어가도 닫힌 해는 대개 사라진다.

  • 우선순위(응급실 중증도 분류), 선점 여부
  • 유한 버퍼와 블로킹, 이탈(balking)·포기(reneging)
  • 시간에 따라 변하는 도착률(점심시간 첨두 — 정상상태 자체가 없다)
  • 서버의 고장·정비, 배치 처리, 재작업 루프
  • 손님 종류별로 다른 경로

그래서 실무의 표준 탈출구가 이벤트 구동 시뮬레이션이다. 도착·서비스 시작·서비스 종료·이탈 네 종류의 사건만 큐에 넣고 돌리면 위 항목들을 전부 그냥 코드로 적을 수 있다. 대가는 답이 수가 아니라 표본이라는 것이고, 그래서 몬테카를로 방법의 통계 관리가 통째로 따라붙는다.

  • 초기 과도구간을 잘라라. 텅 빈 계에서 출발하면 초반 통계가 정상상태보다 낙관적이다. 이 구간(warm-up)을 버리지 않으면 ρ=0.9\rho=0.9 짜리 계를 0.7 짜리로 보고하게 된다. 구간 길이는 여러 번 돌린 평균 궤적을 눈으로 보고 정하는 것이 아직도 표준이며, ρ\rho 가 1에 가까울수록 과도구간이 길어진다는 점이 고약하다. 하필 가장 궁금한 영역에서 가장 오래 돌려야 한다.
  • 신뢰구간을 붙여라. 한 번 돌린 결과는 점 추정이 아니라 표본 하나다. 독립 반복을 여러 번 돌리거나, 긴 한 번의 실행을 배치로 쪼개 배치 평균들의 분산으로 구간을 만든다(배치 평균법). 배치가 짧으면 자기상관 때문에 구간이 실제보다 좁게 나오는데, 큐 시스템은 자기상관이 지독하게 길어서 이 함정이 특히 잘 발생한다.
  • 공통 난수를 써라. 설계안 A와 B를 비교할 때 같은 도착 열을 먹이면 두 결과의 차이에서 공통 잡음이 상쇄되어, 같은 예산으로 훨씬 좁은 비교 구간이 나온다. 난수 스트림을 사건 종류별로 분리해 두어야 이게 성립한다.

해석 모형을 완전히 버리라는 말은 아니다. 현업의 건강한 조합은 해석식으로 자릿수와 방향을 잡고, 시뮬레이션으로 구체적인 설계안을 비교하는 것이다. 시뮬레이션 결과가 ρ→1\rho\to1 에서 킹만 근사와 자릿수도 안 맞으면 모형이든 코드든 어딘가 틀렸다고 보면 된다. 이런 식의 상호 검증은 검증 및 확인의 기본기다.

12. 어디에 쓰이나[편집]

  • 통신·전산. 얼랑의 전화 회선 계산이 그대로 패킷 버퍼와 서버 스레드 풀로 이어졌다. 웹 서비스의 꼬리 지연(p99)이 평균보다 훨씬 나쁜 이유도 1/(1−ρ)1/(1-\rho) 와 분산 항으로 설명된다.
  • 콜센터. 얼랑 C가 아직도 인력 배치 소프트웨어의 엔진이다. 다만 실제 콜센터는 포기하는 손님이 있어서 순수 M/M/c보다는 포기를 넣은 변형(얼랑 A)을 쓴다.
  • 생산·물류. VUT 공식이 재공품(WIP)·리드타임·가동률의 삼각관계를 지배한다. 재고 회전율은 리틀의 법칙 그 자체다.
  • 교통. 신호 교차로의 지체, 톨게이트 대기, 램프 미터링이 전형적인 큐 문제다. 다만 차량은 공간을 차지해서 줄이 상류로 물리적으로 번지므로(교통 흐름의 spillback), 점 하나로 보는 고전 큐 모형은 거기서 한계에 부딪힌다. 병목 하나를 큐로 보고 시간대 선택까지 묶은 모형이 혼잡통행료의 비크리 병목 모형이고, 망 전체를 차량 단위로 돌리는 쪽이 SUMO 같은 미시 시뮬레이터다.
  • 의료. 응급실 병상, 수술실 스케줄, 중환자실 가용률. 여기서는 ρ\rho 를 올리라는 압력과 대기시간의 쌍곡선이 가장 극적으로 충돌한다.

13. 실무에서 조심할 것[편집]

  • 평균만 보고 용량을 정하지 마라. “평균 처리량이 수요보다 크니까 괜찮다”는 문장이 이 분야에서 가장 비싼 오답이다. 변동성이 있으면 ρ<1\rho<1 이어도 줄은 생긴다.
  • ρ\rho 를 정확히 재라. 가동률 분모에 정비·휴식·전환 시간이 빠져 있으면 실제 ρ\rho 는 보고서보다 훨씬 1에 가깝다. 현장이 “숫자상 80%인데 왜 이렇게 밀리죠”라고 말할 때 거의 항상 이 문제다.
  • 도착이 정말 푸아송인지 의심해라. 예약제·셔틀버스·배치 투입은 도착을 뭉치게 만들어 Ca2C_a^2 를 1보다 훨씬 키운다. 반대로 예약이 잘 지켜지면 Ca2C_a^2 가 0에 가까워져 오히려 유리해진다.
  • PASTA를 기억해라. 푸아송 도착에서는 「도착하는 손님이 보는 계의 상태 분포」가 「시간 평균 분포」와 같다(Poisson Arrivals See Time Averages). 그래서 PnP_n 을 그대로 손님 관점 확률로 써도 된다. 도착이 푸아송이 아니면 이 등식이 깨지고, 시뮬레이션 통계를 시간 가중으로 낼지 손님 가중으로 낼지가 실제로 답을 바꾼다.
  • 줄을 합칠 수 있으면 합쳐라. 창구마다 따로 줄 서는 방식보다 단일 대기열(뱀줄)이 같은 인원으로 평균 대기도 짧고 분산도 작다. 제곱근 인력배치 법칙이 말하는 풀링 이득이 공짜로 굴러 들어오는 거의 유일한 경우다.

14. 관련 문서[편집]

15. Footnotes[편집]

  1. 이 이론이 태어난 곳도 딱 그 질문이었다. 1909년 코펜하겐 전화국의 A. K. 얼랑은 “회선을 몇 개 깔아야 통화가 안 끊기나”를 답해야 했고, 그 답이 오늘날까지 통신 용량 단위 에르랑(Erlang)으로 이름이 남았다. 100년 뒤 클라우드 엔지니어가 오토스케일링 임계값을 정하며 하는 고민이 정확히 같은 문제라는 점이 이 분야의 수명을 말해 준다. ↩

  2. 그래서 리틀의 법칙은 “증명이 한 장짜리인데 존 리틀이 1961년에야 제대로 썼다”는 이유로 수업 시간에 종종 놀림받는다. 억울한 놀림이다 — 그 전까지는 “너무 당연해 보여서 아무도 조건을 명확히 안 적었다”가 진실에 가깝고, 실제로 어떤 극한이 존재해야 하는지를 못 박은 것이 논문의 기여다. ↩

  3. 풀링 이득의 반대급부는 공평성과 심리다. 뱀줄은 평균 대기가 짧지만 “내 앞에 몇 명”이 눈에 다 보여서 체감이 더 나쁘다는 보고가 흔하다. 그래서 놀이공원은 줄을 굽이굽이 접어 길이를 숨기고, 콜센터는 대기 순번을 읽어 준다. 이쯤 되면 이론이 아니라 인테리어의 영역이다. ↩