대기행렬이론

왜 배우는가: 대기행렬이론은 설비 배치, 정비, 자재 공급처럼 고객과 서버가 있는 생산 시스템에서 기다림을 수치로 계산하게 해 준다. 여러 회차에 걸쳐 출제된 개념이므로 M/M/1 모형의 가정, 식의 적용, 켄들 표기법 분류를 먼저 틀로 잡아 두어야 한다.

출제 이력: 제103회 2교시 3번, 제97회 3교시 5번, 제91회 3교시 5번

1. 한 줄 정의와 핵심 키워드

대기행렬이론은 서비스를 기다리는 고객의 줄을 확률적으로 분석해 시스템의 성능을 구하는 이론이다.

이 이론의 분석 대상은 고객이 줄을 서는 현상 자체이고, 결과물은 평균 고객 수와 평균 대기시간 같은 성능 척도이다. 설계자는 이 척도를 계산해 서버 수와 처리 속도를 정하므로, 대기행렬이론은 설비 용량을 결정하는 근거를 제공하는 도구로 쓰인다.

핵심 키워드는 다음과 같다.

• 대기행렬: 하나 이상의 서버에 서비스를 요구하며 기다리는 고객의 줄이다.
• 도착률: 단위시간당 평균 도착 고객 수이며 기호는 λ로 쓴다.
• 서비스율: 단위시간당 서비스를 마치는 평균 고객 수이며 기호는 μ로 쓴다.
• 대기규칙: 대기 고객의 서비스 순서를 정하는 규칙이며 선입선출이 기본이다.
• 켄들 표기법: 대기행렬 모형을 A/S/c 형식으로 분류하는 표준 체계이다.
• M/M/1 모형: 도착 간격과 서비스 시간이 모두 지수분포를 따르는 단일 서버 모형이다.
• 리틀의 법칙: 평균 고객 수를 도착률과 평균 체류시간의 곱으로 나타내는 법칙이다.

2. 개념 풀이

대기행렬이론은 고객이 도착하고 기다리고 서비스를 받는 과정을 확률 모형으로 기술해, 시스템의 운영 특성을 계산하는 이론이다. 여기서 운영 특성은 시스템 내 고객 수의 확률분포, 대기 고객 수, 평균 체류시간, 평균 대기시간, 서버가 바쁠 확률 등을 말한다. 따라서 대기행렬 모형은 이 값들을 계산하는 것을 목표로 하며, 모형의 구조는 도착과 서비스의 확률적 성질로 정해진다.

원리는 도착률과 서비스율의 상대적 크기에서 나온다. 서버가 처리할 수 있는 양보다 도착이 많으면 줄은 끝없이 늘어나므로, 평균 도착률이 평균 서비스율보다 작아야 줄이 일정한 수준에서 안정된다. 정상상태가 존재하려면 도착률이 서비스율보다 작아야 한다. 이 조건이 대기행렬 분석의 출발점이다.

대기행렬 시스템은 모집단, 도착 과정, 대기규칙, 서비스 과정의 네 요소로 기술한다. 모집단은 고객이 유한한지 무한한지를 정하고, 도착 과정은 도착 간격의 확률분포를 정한다. 대기규칙은 선입선출 같은 서비스 순서를 정하며, 서비스 과정은 서버 수와 서비스 시간의 분포를 정한다.

켄들 표기법은 모형의 구조를 A/S/c로 나타낸다. A는 도착 간격의 분포, S는 서비스 시간의 분포, c는 서버 수이며, M은 지수분포(마르코프 과정)를, G는 일반 분포를 뜻한다. 뒤에 용량 K, 모집단 N, 서비스 순서 D가 붙지만 생략되면 K와 N은 무한, D는 선입선출로 본다.

M/M/1 모형은 이 네 요소를 가장 단순하게 정한 모형이다. 도착 과정은 도착률 λ의 푸아송 과정이고, 서비스 시간은 평균 1/μ인 지수분포를 따른다. 서버는 한 명이며 선입선출로 고객을 처리하고, 대기 공간은 무한하다고 가정한다. 상태 n은 서비스 중인 고객을 포함한 시스템 내 고객 수이며, 이 모형은 생멸과정(birth-death process)과 같은 연속시간 마르코프 체인으로 기술된다.

교통 강도는 ρ = λ/μ로 정의되며, 정상상태 조건은 λ < μ이다. 정상상태에서 주요 운영 특성은 다음 식으로 구한다. L_S는 시스템 내 평균 고객 수(명), L_q는 대기 고객 평균 수(명), W_S는 시스템 내 평균 체류시간, W_q는 평균 대기시간(λ와 μ의 시간 단위에 맞춘 단위), ρ는 무차원 교통 강도이다.

$L_S = ρ/(1-ρ) = λ/(μ-λ)$

$L_q = ρ²/(1-ρ)$

$W_S = 1/(μ-λ)$

$W_q = λ/(μ(μ-λ))$

리틀의 법칙은 평균 고객 수를 도착률과 평균 체류시간의 곱으로 구하는 법칙이며 $L = λW$ 로 나타낸다. 시스템이 에르고딕 조건을 만족하면 도착 과정이나 서비스 순서와 관계없이 성립한다. 따라서 L_S와 W_S는 λ를 매개로 서로 환산된다.

핵심 용어는 다음과 같다.

• 교통 강도: 도착률을 서비스율로 나눈 값으로, 서버의 부하 정도를 나타낸다. 1보다 작아야 정상상태가 존재한다.
• 시스템 내 평균 고객 수: 서비스 중인 고객과 대기 고객을 모두 포함한 평균 고객 수이다.
• 대기 고객 평균 수: 서비스를 받지 않고 줄에서 기다리는 평균 고객 수이다.
• 정상상태: 시간이 지나도 시스템의 상태 확률분포가 변하지 않는 상태이다.

3. 등장 배경과 필요성

서비스 시설에 대한 수요가 서비스 제공 능력을 넘어서면 기다림이 생긴다. 서버가 너무 바빠서 도착하는 고객이 즉시 서비스를 받을 수 없을 때 대기행렬이 발생하며, 도착 시간과 서비스 시간이 함께 변동하기 때문에 어느 시스템에서도 대기를 완전히 없앨 수 없다. 대기는 예외적 현상이 아니라 서비스 시스템의 기본 특성이다.