대기행렬이론(待機行列理論, queueing theory)은 대기행렬(queue, waiting line)을 수학적으로 분석하고 모델링하는 이론이다. 이 이론은 서비스를 받기 위해 대기하는 고객(또는 작업, 패킷 등)의 도착 과정, 대기 과정, 서비스 과정, 그리고 이탈 과정을 확률론적 방법으로 분석하여 시스템의 성능을 정량적으로 평가하고 예측하는 것을 목적으로 한다.
역사
대기행렬이론은 1909년 덴마크의 수학자이자 엔지니어였던 아그너 크라루프 얼랑(Agner Krarup Erlang)이 코펜하겐 전화 교환소의 시스템을 모델링하기 위해 처음 개발하였다. 얼랑은 포아송 프로세스(Poisson process)를 이용하여 교환기에 도착하는 전화 호출의 수를 모델링하였고, 이후 M/D/1 큐(1917년)와 M/D/k 큐(1920년) 모델을 해결하였다. 1946년 국제전화전신자문위원회(CCITT)는 국제 전화 트래픽 단위를 '얼랑(erlang)'으로 명명하였다. 이후 1953년 데이비드 조지 켄달(David George Kendall)이 켄달 표기법(Kendall's notation)을 도입하였고, 1961년 존 리틀(John D. C. Little)이 리틀의 법칙(Little's Law)을 증명하였다.
기본 구성 요소
대기행렬 시스템은 다음과 같은 요소로 구성된다.
- 고객(customer): 서비스를 받기 위해 시스템에 도착하는 객체. 사람, 차량, 통신 패킷, 작업 단위 등이 해당될 수 있다.
- 서버(server): 서비스를 수행하는 주체. 계산원, 기계, CPU 코어, 통신 채널 등이 해당된다.
- 대기행렬(queue): 서버가 사용 중일 때 고객이 서비스를 기다리는 공간.
- 도착 과정(arrival process): 고객이 시스템에 도착하는 패턴. 일반적으로 단위시간당 평균 도착률 λ(람다)로 표현된다.
- 서비스 과정(service process): 서버가 고객을 처리하는 데 소요되는 시간의 분포. 단위시간당 평균 서비스율 μ(뮤)로 표현된다.
켄달 표기법(Kendall's Notation)
대기행렬 시스템은 켄달 표기법을 사용하여 A/B/C : D/E/F 형식으로 표현된다.
- A: 고객 도착시간 간격의 확률분포 (M: 지수분포/마르코프, D: 결정론적 상수, E: 얼랑분포, G: 일반분포)
- B: 서비스 시간의 확률분포
- C: 서버의 수 (단일서버 s=1, 복수서버 s>1)
- D: 서비스 규칙 (FCFS: 선착순, LCFS: 역선착순, SIRO: 임의순, PRP: 우선순위)
- E: 시스템 규모 (유한 K, 무한 ∞)
- F: 고객 모집단 크기 (유한 N, 무한 ∞)
리틀의 법칙(Little's Law)
안정 상태의 대기행렬 시스템에서 다음 관계가 성립한다.
- L = λW (L: 시스템 내 평균 고객 수, λ: 평균 도착률, W: 평균 체류 시간)
- Lq = λWq (Lq: 대기행렬 내 평균 고객 수, Wq: 평균 대기 시간)
이 법칙은 도착 분포나 서비스 분포의 형태와 무관하게 성립하는 보편적 관계식이다.
주요 모형
- (M/M/1) : (FCFS/∞/∞) 모형: 가장 단순한 형태로, 서버 1개, 포아송 도착, 지수분포 서비스 시간, 무한 대기 용량을 가정한다. 현금인출기(ATM)가 대표적 예시이다.
- (M/M/s) : (FCFS/∞/∞) 모형: 다수의 서버를 가진 모형으로, 복수 창구가 있는 은행이 대표적 예시이다.
- (M/M/s) : (FCFS/K/∞) 모형: 시스템이 수용할 수 있는 고객 수가 K명으로 제한된 모형이다. K=s인 경우를 얼랑손실 시스템(Erlang loss system)이라고 하며, 전화 통신망 분석에 사용된다.
- (M/M/s) : (FCFS/∞/N) 모형: 특정 N명의 고객만을 대상으로 서비스를 제공하는 모형으로, 공장 내 기계 전담 수리 서비스 등이 예시이다.
- (M/G/1) 모형: 도착은 포아송 분포를 따르지만 서비스 시간이 일반 분포를 따르는 모형이다. 폴라체크-킨친 공식(Pollaczek-Khinchine formula)이 적용된다.
성능 척도
대기행렬 시스템의 주요 성능 척도는 다음과 같다.
- ρ(로): 서버 이용률 (ρ = λ / sμ, 안정 조건은 ρ < 1)
- Pn: 시스템 내에 n명의 고객이 존재할 확률
- L: 시스템 내 고객 수의 기댓값
- Lq: 대기행렬 내 고객 수의 기댓값
- W: 시스템 내 체류 시간의 기댓값
- Wq: 대기행렬에서 순수하게 기다린 시간의 기댓값
- Pw: 도착한 고객이 서비스를 받기 위해 기다려야 할 확률
- PK: 시스템 규모 초과로 고객의 도착이 봉쇄될 확률
응용 분야
대기행렬이론은 운영과학(operations research)의 한 분야로 간주되며, 다음과 같은 다양한 분야에서 활용된다.
- 경영학 및 산업공학: 생산 공정에서의 작업자·기계·자재의 대기시간 최소화, 적정 인력 및 설비 규모 결정
- 통신 네트워크: 패킷 스케줄링, 자원 관리, 네트워크 성능 분석 및 설계
- 교통 시스템: 교통 흐름 분석, 신호 제어, 병목 지점의 대기행렬 길이 산정
- 컴퓨터 시스템: CPU 스케줄링, 서버 용량 계획, 데이터베이스 성능 분석, 클라우드 컴퓨팅 자원 관리
- 콜센터: 상담원 수 결정, 대기 시간 예측, 서비스 수준 관리
- 공공 서비스: 병원 응급실, 항만, 공항 시설 규모 결정
대기행렬이론은 시스템의 평균 대기시간, 대기행렬 길이, 서버 이용률 등을 확률적으로 예측함으로써, 대기 비용과 서비스 비용 간의 균형을 최적화하는 의사 결정을 지원하는 도구로 사용된다.
