최근 수정 시각 : 2024-08-13 00:55:23

대기행렬이론

대기행렬 이론에서 넘어옴
1. 개요2. 상세
2.1. 용어2.2. 성능척도2.3. Little의 공식
3. 종류
3.1. (M/M/1):(FCFS/∞/∞) 모형3.2. (M/M/s):(FCFS/∞/∞) 모형3.3. (M/M/s):(FCFS/K/∞) 모형3.4. (M/M/s):(FCFS/∞/N) 모형3.5. (M/M/s):(FCFS/K/N) 모형3.6. M/G/1 모형3.7. 응용 대기행렬이론(Advanced Queueing Theory)
3.7.1. 랴푸노프 최적화(Lyapunov Optimization)3.7.2. 최적의 정지(Optimal stopping)
4. 관련 도구5. 관련 문서

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μ~(n<s) \\ sμ~(n≥s) \end{cases})] 이므로 [math(ρ=\dfracλ{sμ})]라고 할 때,
[math(P_n=\begin{cases} \dfrac{(sρ)^n}{n!}•P_0~(n<s) \\ \dfrac{s^s}{s!}ρ^n•P_0~(n≥s) \end{cases})]이다.

따라서 이 시스템의 성능척도는 다음과 같다.
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} λ~(n<K) \\ 0~(n=K) \end{cases})] 이고
[math(μ_n=\begin{cases} nμ~(n<s) \\ sμ~(s≤n≤K) \end{cases})] 이므로 [math(ρ=\dfracλ{sμ})]라고 할 때,
[math(P_n=\begin{cases} \dfrac{(sρ)^n}{n!}•P_0~(n<s) \\ \dfrac{s^s}{s!}ρ^n•P_0~(s≤n≤K) \end{cases})]이다.

따라서 이 시스템의 성능척도는 다음과 같다.
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μ~(n<s) \\ sμ~(s≤n≤N) \end{cases})] 이므로 [math(ρ=\dfracλ{sμ})]라고 할 때,
[math(P_n=\begin{cases} {}_N{\rm P}_n\dfrac{(sρ)^n}{n!}•P_0~(n<s) \\ \dfrac{s^s}{s!}{}_N{\rm P}_nρ^n•P_0~(s≤n≤N) \end{cases})]이다.

따라서 이 시스템의 성능척도는 다음과 같다.(단, ρ=[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)λ~(n<K) \\ 0~(n=K) \end{cases})] 이고
[math(μ_n=\begin{cases} nμ~(n<s) \\ sμ~(s≤n≤K) \end{cases})] 이므로 [math(ρ=\dfracλ{sμ})]라고 할 때,
[math(P_n=\begin{cases}{}_N{\rm P}_n \dfrac{(sρ)^n}{n!}•P_0~(n<s) \\ \dfrac{s^s}{s!}{}_N{\rm P}_nρ^n•P_0~(s≤n≤K) \end{cases})]이다.

따라서 이 시스템의 성능척도는 다음과 같다.(단, ρ=[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)]

3.6. M/G/1 모형

도착 트래픽 분포는 기존 M/M/1과 동일한 지수분포, 서비스 분포는 포아송 분포 형태를 띤 대기행렬 모델
  • Pollaczek-Khinchine (P-K) formula

3.7. 응용 대기행렬이론(Advanced Queueing Theory) [2]

3.7.1. 랴푸노프 최적화(Lyapunov Optimization)

큐를 최적화하는 도구

3.7.2. 최적의 정지(Optimal stopping)

최적의 시스템 정지 지점을 확률론 적으로 판단가능한 기술

4. 관련 도구

  • MATLAB 이산사건 시뮬레이터 Simevent #
  • 네트워크 시뮬레이터 3 (NS3) #

5. 관련 문서


[1] 코펜하겐 대학교에서 수학을 전공했으며 특히 확률과 통계 분야를 연구했다. 1946년에 CCITT는 국제 전화 트래픽 단위를 'erlang'이라고 명명했음[2] 큐잉이론 최근 트렌드에 대해, 보통 대학원에서 많이 배운다. 응용확률론 이라는 과목으로도 많이 개설되어 있다.[3] 대기행렬 모델을 세우고 수학적 최적화로 해결하는 방식도 많이 활용한다.

분류