1. 개요
待 機 行 列 理 論 / queueing theory시스템 내에 필연적으로 존재하는 대기 행렬을 효율적으로 통제하여 올바른 의사결정을 내리기 위해 사용하는 이론이다. 덴마크 수학자 아그너 크라우프 얼랑(Agner Krarup Erlang)[1]에 의해 창시되었다.
2. 상세
(A/B/C):(D/E/F)해당 형태로 시스템 모델을 나타내며 각각의 구성요소는 아래와 같다.
| 구성요소 | 종류 |
| A 고객 도착시간 간격 분포의 종류 |
M:
지수분포 D:상수 E:얼랑분포 G:일반분포 |
| B 서비스 시간 분포의 종류 | |
| C 서버의 수 |
단일서버(s=1) 복수서버(s>1) |
| D 서비스 규칙 |
FCFS:
선착순 LCFS:역선착순 SIRO:임의순 GD:일반적 규칙 PRP:우선순위 규칙 |
| E 시스템 규모 |
유한(K) 무한(∞) |
| F 고객 모집단 크기 |
유한(N) 무한(∞) |
일반적으로 고객의 도착시간 간격(A)과 서비스 시간(B)은 지수분포를 따른다고 가정한다.
2.1. 용어
시스템 : 고객이 도착해서 대기하고 서비스를 받고 이탈하는 일련의 총체적 과정고객 : 서비스를 받기 원하는 객체
서버 : 서비스를 수행하는 주체
서비스 시간 : 특정 서비스를 처리하는 데 소요되는 시간
고객 모집단 크기 : 서비스를 요구하는 잠재고객의 수
시스템 규모 : 시스템 내에 머무를 수 있는 최대 고객수
서비스 규칙 : 대기 중인 고객에 대한 서비스 순서
λ : 단위시간동안 도착하는 평균고객의 수
μ : 단위시간동안 1명의 서버에게 서비스를 제공받는 평균고객의 수
2.2. 성능척도
λn : 시스템 내에 n명의 고객이 있을 때 도착률μn : 시스템 내에 n명의 고객이 있을 때 서비스율
Pn : 시스템 내에 n명의 고객이 존재할 확률
U : 서버의 이용율
Pw : 도착한 고객이 서비스를 받기 위해 기다려야 할 확률
PK : 시스템 규모 초과로 고객의 도착이 봉쇄될 확률
L : 시스템에 있는 고객수의 기댓값
Lq : 대기행렬에 있는 고객수의 기댓값
W : 시스템 내에서 체류하는 시간의 기댓값
Wq : 대기행렬에서 순수하게 기다린 시간의 기댓값
2.3. Little의 공식
시스템의 성능척도 간의 관계식을 정의한 공식으로 L, Lq, W, Wq의 값 중 하나만 알고 있어도 나머지 세 값을 구할 수 있다.즉, [math(\bar{λ}=\displaystyle \sum_{n=0}^∞λ_nP_n)]이라고 할 때
[math(L=\bar{λ}W)]
[math(L_q=\bar{λ}W_q)]
[math(W=W_q+\dfrac1μ)]이 된다.
3. 종류
3.1. (M/M/1):(FCFS/∞/∞) 모형
가장 단순한 형태의 모형으로 서버의 수가 1명이고 시스템 내 수용 인원과 고객 모집단에 한계가 없는 모형이다. 현금지급기가 이 모형에 해당한다.이 모형에서는 현재 시스템 내에 몇명의 고객이 존재하든지 도착률과 서비스율이 일정하다.
즉, [math(λ_n=λ)] 이고 [math(μ_n=μ)] 이므로 [math(ρ=\dfracλμ)]라고 할 때,
[math(P_n=ρ^n•P_0)]이다.
따라서 이 시스템의 성능척도는 다음과 같다.
| U | [math(ρ)] |
| P0 | [math(1-ρ)] |
| L | [math(\dfracρ{1-ρ})] |
| Lq | [math(\dfrac{ρ^2}{1-ρ})] |
| W | [math(\dfrac1{μ(1-ρ)})] |
| Wq | [math(\dfracρ{μ(1-ρ)})] |
| Pw | [math(1-ρ)] |
3.2. (M/M/s):(FCFS/∞/∞) 모형
가장 보편적인 형태의 모형으로 서버가 다수이고 시스템 내 수용 인원과 고객 모집단에 한계가 없는 모형이다. 창구직원이 있는 은행이 이 모형에 해당한다.이 모형에서는 현재 시스템 내에 몇명의 고객이 존재하든지 도착률은 [math(λ_n=λ)]로 일정하지만 서비스율은 시스템의 상태에 따라 달라진다.
[math(μ_n=\begin{cases} nμ~
[math(P_n=\begin{cases} \dfrac{(sρ)^n}{n!}•P_0~
따라서 이 시스템의 성능척도는 다음과 같다.
| U | [math(ρ)] |
| P0 | [Math(\dfrac1{\displaystyle \sum_{n=0}^{s-1}{\dfrac{(sρ)^n}{n!}}+\dfrac{(sρ)^s}{s!(1-ρ)}})] |
| L | [math(L_q+sρ)] |
| Lq | [math(\dfrac{ρ(sρ)^s}{s!(1-ρ)^2}•P_0)] |
| W | [math(W_q+\dfrac1μ)] |
| Wq | [math(\dfrac{(sρ)^s}{μs!(1-ρ)^2}•P_0)] |
| Pw | [math(\dfrac{(sρ)^s}{s!(1-ρ)}•P_0)] |
3.3. (M/M/s):(FCFS/K/∞) 모형
시스템이 수용할 수 있는 고객의 수가 K명으로 제한되어 있는 모형으로, 특히 이 모형에서 K=s인 경우를 얼랑손실 대기행렬 시스템이라고 하는데 이는 전화 통신망에 대한 분석에서 유용하게 이용된다. 최근 사회적 거리두기로 인하여 수용인원이 정해져 있는 영업장도 이 모형에 해당한다.이 모형에서는 고객이 K명이 될 경우 더이상 고객이 도착할 수 없기 때문에 도착률, 서비스율은 다음과 같다.
[math(λ_n=\begin{cases} λ~
[math(μ_n=\begin{cases} nμ~
[math(P_n=\begin{cases} \dfrac{(sρ)^n}{n!}•P_0~
따라서 이 시스템의 성능척도는 다음과 같다.
| U | [math(\dfrac{L-L_q}s)] |
| P0 | [Math(\dfrac1{\displaystyle \sum_{n=0}^{s-1}{\dfrac{(sρ)^n}{n!}}+\dfrac{s^s(1-ρ^{K-s+1})}{s!(1-ρ)}})] |
| L | [Math(\displaystyle \sum_{n=0}^Kn•P_n)] |
| Lq | [Math(\displaystyle \sum_{n=s}^K(n-s)•P_n)] |
| W | [math(\dfrac{L}{λ(1-P_K)})] |
| Wq | [math(\dfrac{L_q}{λ(1-P_K)})] |
| Pw | [math(\dfrac{s^s(1-ρ^{K-s})}{s!(1-ρ)}•P_0)] |
| PK | [math(\dfrac{s^s}{s!}ρ^K•P_0)] |
3.4. (M/M/s):(FCFS/∞/N) 모형
특정 N명의 고객만을 대상으로 서비스를 제공하는 모형으로, 특정 공장내의 기계 전담 수리 서비스 등이 그 예이다.이 모형에서는 시스템 내에 n명의 고객이 있을 경우 시스템 외부에서 (N-n)명의 고객이 도착하게 되므로 도착률, 서비스율은 다음과 같다.
[math(λ_n=(N-n)λ)] 이고
[math(μ_n=\begin{cases} nμ~
[math(P_n=\begin{cases} {}_N{\rm P}_n\dfrac{(sρ)^n}{n!}•P_0~
따라서 이 시스템의 성능척도는 다음과 같다.(단, ρ=[math(\dfracλ{sμ})])
| U | [math(\dfrac{L-L_q}s)] |
| P0 | [Math(\dfrac1{\displaystyle \sum_{n=0}^{s-1}{}_N{\rm P}_n{\dfrac{(sρ)^n}{n!}}+\dfrac{s^s}{s!}\displaystyle \sum_{n=s}^N{}_N{\rm P}_nρ^n})] |
| L | [Math(\displaystyle \sum_{n=0}^Nn•P_n)] |
| Lq | [Math(\displaystyle \sum_{n=s}^N(n-s)•P_n)] |
| W | [math(\dfrac{L}{λ(N-L)})] |
| Wq | [math(\dfrac{L_q}{λ(N-L)})] |
| Pw | [math(\dfrac{s^s}{s!}\displaystyle \sum_{n=s}^N{}_N{\rm P}_nρ^n•P_0)] |
3.5. (M/M/s):(FCFS/K/N) 모형
N명의 고객만을 대상으로 서비스를 제공하고 시스템 내 최대 수용가능한 고객의 수가 K명으로 제한되어 있는 모형으로 군부대 내의 PX 등이 그 예이다.이 모형에서 고객의 도착률과 서비스율은 다음과 같다.(단, s≤K≤N)
[math(λ_n=\begin{cases} (N-n)λ~
[math(μ_n=\begin{cases} nμ~
[math(P_n=\begin{cases}{}_N{\rm P}_n \dfrac{(sρ)^n}{n!}•P_0~
따라서 이 시스템의 성능척도는 다음과 같다.(단, ρ=[math(\dfracλ{sμ})])
| U | [math(\dfrac{L-L_q}s)] |
| P0 | [Math(\dfrac1{\displaystyle \sum_{n=0}^{s-1}{}_N{\rm P}_n{\dfrac{(sρ)^n}{n!}}+\dfrac{s^s}{s!}\displaystyle \sum_{n=s}^K{}_N{\rm P}_nρ^n})] |
| L | [Math(\displaystyle \sum_{n=0}^Kn•P_n)] |
| Lq | [Math(\displaystyle \sum_{n=s}^K(n-s)•P_n)] |
| W | [math(\dfrac{L}{λ(1-P_K)})] |
| Wq | [math(\dfrac{L_q}{λ(1-P_K)})] |
| Pw | [math(\dfrac{s^s}{s!}\displaystyle \sum_{n=s}^{K-1}{}_N{\rm P}_nρ^n•P_0)] |
| PK | [math(\dfrac{s^s}{s!}{}_N{\rm P}_Kρ^K•P_0)] |