대기행렬이론 공식, M/M/1과 리틀의 법칙 계산법

🧮 생활 속 수학

대기행렬이론은 도착률과 처리율만으로 줄의 길이와 기다리는 시간을 계산한다. M/M/1 공식과 리틀의 법칙으로 계산대 한 개짜리 가게의 평균 대기시간을 직접 구해 본다.

대기행렬이론은 손님이 도착하는 속도와 한 명을 처리하는 속도 두 숫자만으로 줄에 서 있는 평균 인원과 기다리는 시간을 계산하는 수학이다. 계산대가 하나인 가게를 예로 들면, 도착률이 처리율의 80%일 때 평균 대기시간은 5분이고, 90%가 되면 10분으로 두 배가 된다. 이 글은 그 숫자가 어떻게 나오는지 대기행렬이론의 공식을 끝까지 계산해 보여준다.

대기행렬이론이란 무엇인가요?

대기행렬이론(queueing theory)은 은행 창구, 편의점 계산대, 콜센터, 병원 접수처처럼 줄이 생기는 모든 곳을 같은 틀로 분석하는 확률 이론이다. 덴마크의 통신 기술자 얼랑(A. K. Erlang)이 1900년대 초 전화 교환기에 필요한 회선 수를 계산하려고 만든 것이 출발점으로 알려져 있다. 지금은 서버 용량 설계, 공항 보안검색대 인원 배치, 도로 신호 설계까지 대기행렬이론이 쓰인다.

모형에는 이름표가 붙는다. M/M/1에서 첫 M은 손님이 무작위로 도착한다는 뜻(푸아송 도착)이고, 둘째 M은 한 명을 처리하는 시간이 지수분포를 따른다는 뜻이며, 마지막 1은 창구가 한 개라는 뜻이다. 현실이 이 가정과 정확히 같지는 않지만, 줄이 어떻게 부풀어 오르는지 감을 잡는 데 이만한 모형이 없다.

M/M/1 대기행렬 공식은 어떻게 쓰나요?

대기행렬이론에서 필요한 숫자는 두 개다. 도착률 \(\lambda\)는 단위 시간당 도착하는 평균 인원, 처리율 \(\mu\)는 창구가 단위 시간당 처리할 수 있는 평균 인원이다. 두 값의 비율을 이용률이라 부르고 \(\rho\)로 쓴다. 대기행렬이론의 모든 공식이 이 \(\rho\)에서 출발하며, 줄이 무한정 늘어나지 않으려면 \(\rho < 1\)이어야 한다.

$$ \rho = \frac{\lambda}{\mu} $$

이용률 \(\rho\)는 창구가 일하고 있는 시간의 비율이기도 하다. \(\rho=0.8\)이면 창구는 80%의 시간 동안 바쁘고 20%의 시간은 놀고 있다. 이제 시스템 안에 있는 평균 인원 \(L\)(줄을 선 사람과 계산 중인 사람의 합)과 한 명이 시스템에 머무는 평균 시간 \(W\)는 다음과 같다.

$$ L = \frac{\rho}{1-\rho}, \qquad W = \frac{1}{\mu-\lambda} $$

대기행렬이론에서 줄만 따지면, 계산 중인 사람을 빼고 기다리는 평균 인원은 \(L_q = \rho^2/(1-\rho)\), 기다리는 평균 시간은 \(W_q = \lambda/\big(\mu(\mu-\lambda)\big)\)다. 두 값은 계산 시간을 제외하므로 \(L\), \(W\)보다 작다.

대기행렬이론으로 계산대 하나짜리 가게의 대기시간을 계산하면?

대기행렬이론 문제로 바꿔, 편의점 계산대가 1개이고 손님이 평균 분당 0.8명 도착한다고 하자(시간당 48명). 계산 한 건에 평균 1분이 걸리면 \(\mu=1\)이다. 이용률은 \(\rho=0.8/1=0.8\)이다. 시스템 안 평균 인원은 \(L=0.8/0.2=4\)명이고, 한 명이 머무는 평균 시간은 \(W=1/(1-0.8)=5\)분이다. 줄만 보면 \(L_q=0.64/0.2=3.2\)명, \(W_q=0.8/(1\times0.2)=4\)분이다. 계산에 1분이 걸리니 4분 기다리고 1분 계산해서 5분이 된다.

이용률이 오를 때 평균 체류시간 \(W\) (\(\mu=1\)명/분 기준)

• \(\rho=0.5\): \(W=2\)분, 평균 \(L=1\)명
• \(\rho=0.8\): \(W=5\)분, 평균 \(L=4\)명
• \(\rho=0.9\): \(W=10\)분, 평균 \(L=9\)명
• \(\rho=0.95\): \(W=20\)분, 평균 \(L=19\)명
• \(\rho=0.99\): \(W=100\)분, 평균 \(L=99\)명

이 표가 대기행렬이론이 주는 가장 중요한 교훈이다. 이용률이 50%에서 80%로 오를 때 체류시간은 2.5배가 되지만, 90%에서 99%로 오를 때는 10배가 된다. 창구가 거의 쉴 틈이 없을 정도로 바빠지면 손님이 조금만 늘어도 줄이 폭발적으로 길어진다.

리틀의 법칙은 무엇이고 왜 편리한가요?

대기행렬이론의 핵심 정리인 리틀의 법칙(Little’s law)은 1961년 존 리틀이 증명한 관계로, 시스템 안의 평균 인원 \(L\), 도착률 \(\lambda\), 평균 체류시간 \(W\) 사이에 다음이 성립한다는 내용이다.

$$ L = \lambda W $$

위의 대기행렬이론 예에서 \(\lambda=0.8\)명/분, \(W=5\)분이므로 \(L=0.8\times5=4\)명으로 앞서 구한 값과 정확히 일치한다. 리틀의 법칙이 편리한 이유는 도착이 푸아송이든 처리 시간이 어떤 분포든 상관없이 성립한다는 점이다. 그래서 병원 응급실에 평균 30명이 머물고 분당 1.5명이 들어온다면 평균 체류시간은 \(30/1.5=20\)분이라고 곧바로 읽을 수 있다.

줄을 줄이려면 창구를 늘려야 하나요, 속도를 높여야 하나요?

대기행렬이론으로 같은 가게를 다시 보자. 계산 속도가 25% 빨라져 \(\mu=1.25\)이 되면 이용률은 \(\rho=0.8/1.25=0.64\)가 되고, 체류시간은 \(W=1/(1.25-0.8)\approx2.2\)분으로 5분에서 절반 아래로 떨어진다. 처리 속도를 25% 올렸을 뿐인데 대기시간은 55% 가까이 줄어드는 것이다. 이용률이 높은 구간일수록 작은 개선이 크게 작용한다는 대기행렬이론의 비선형성이 그대로 드러난다.

반대로 손님이 몰리는 시간대에는 \(\rho\)가 1에 가까워져서 평균 계산으로는 감당이 안 된다. 그래서 가게들은 피크 시간에 창구를 임시로 늘리거나 셀프 계산대를 연다. 다만 현실의 손님은 시간대별로 도착률이 달라서, 이 글의 M/M/1 대기행렬이론 계산은 도착률이 일정한 구간의 근삿값으로만 읽어야 한다. 실제 의사결정에는 매장의 실측 자료가 필요하다.

대기행렬이론을 확인하려고 직접 줄을 서며 시간을 재 본 적이 있다. 점심시간 구내식당에서 앞사람 수와 평균 계산 시간을 세어 보니 예상 대기시간이 실제와 비슷하게 맞았고, 사람이 한두 명만 더 늘어도 대기가 확 길어지는 체감이 위 표의 비선형성과 닮아 있었다.

함께 읽으면 좋은 글

손익분기점 뜻과 계산 공식, 판매량·매출액 구하는 법치킨 게임 뜻과 유래, 게임이론으로 푸는 균형 계산이항분포 뜻과 공식, 평균·분산 유도와 예제 정리

참고 자료

Wikipedia — Queueing theoryWikipedia — Little's law