제 10 장 대기행렬 분석
제 10 장 대기행렬 분석
대기행렬
대기행렬
– 고객의 불규칙한 도착과 서비스 시간의 불균형으로 인하여 기다리는 상 태를 초래
– 은행창구, 매표소, 터미널, …
2
대기행렬의 분석법
– (1) 물리적 관찰을 통한 결과 분석법
비용이 많이 들지만 가장 보편적으로 이용되는 방법
– (2) 시뮬레이션을 이용한 분석법√
현실적 모형을 만들어서 실험 및 결과 예측에 이용
복잡한 문제의 분석에 자주 이용되는 방법
– (3) 대기행렬의 수학적 분석법 √
Queuing Theory
확률이론과 수리적 모델을 이용한 분석법
대기행렬 모형
모형의 요소
(1) 고객의 도착 형태
: 도착시간의 확률 분포 (2) 봉사자의 서비스 형태
: 서비스시간의 확률 분포
(4) 서비스 규칙
: FCFS, LCFS, RANDOM,...
(5) 대기행렬 용량
: 대기행렬의 최대 길이
…..
봉사자 봉사자 봉사자 .…...
도착고객 대기행렬
서비스 시설
떠나는 고객 분석 시스템
: 서비스시간의 확률 분포 (3) 봉사자의 수
: 대기행렬의 최대 길이 (6) 투입요소의 수
: 도착고객의 한계
대기행렬 모형
Kendall-Lee의 기호 (1/2/3):(4/5/6)
1, 2 : 고객 도착 및 서비스 형태
M: 지수분포
D: 일정시간간격을 두고 발생 E: Erlang 분포
4 E: Erlang 분포
G: 일반 분포
3: 종사자의 수 4: 서비스 규칙
FCFS, LCFS, SIRO(Service In Random Order) …
5: 대기행렬 용량 6: 투입요소 한계
예) (M/M/1):(FCFS/∞/∞)
분포의 가정
도착 시간(간격)의 분포
빈도 a
c b
무작위 도착
=> 지수분포: f(t) = λe-λt
지수 분포
– 다음 고객의 도착은 이전 고객의 도착과 무관하다.
– 다음 고객의 서비스 시간은 이전 고객의 서비스 시간과 무관하다.
도착시간 간격
=> 지수분포: f(t) = λe-λt
2 2
분산 1 1 ,
평균 ,
: , )
(
분산 1
1 , 평균
도착률, :
, )
(
µ µ µ
µ
λ λ λ
λ
µ λ
=
=
=
=
=
=
−
−
서비스율
t t
e t
g
e t
f <정의>도착률: 단위시간당 도착하는 평균인원수
서비스율: .. 서비스할 수 있는 능력
지수분포의 특성
지수분포의 도착형태
– [0,T] 동안 고객이 하나도 도착하지 않을 확률
= 첫 고객이 T시간 이후에 도착할 확률
– [0,T] 동안 고객이 도착하지 않은 상태에서 [0, T+h] 동안 고객이 아무도
∫
∞ − = −=
≥ T
T tdt e e
T t
P0( )
λ
λ λ6
도착하지 않을 확률
=> 임을 알 수 있고, 이것은 T라는 시점과 무관 하게 시간 간격 h에만 관계됨을 의미함.(memoryless)
– 매우 작은 시간 간격 h 동안 도착이 없을 확률
=> h 동안 1명이 도착할 확률
h T
h T
T
t h T
t
e e e dt e
dt e T
t h T t
P λ λ
λ λ
λ
λ
λ
−− +
−
∞ −
∞ +
−
=
=
=
≥ +
≥
∫
∫
( )0( | )
h h h h
e h
P h
λ λ λ
λ
λ
− + ≅ −− + +
− +
=
= − ... 1
! 3
) (
! 2
) ) (
( 1 )
(
3 2
0
) (
)
|
( 0
0 t T h t T P t h
P ≥ + ≥ = ≥
∑
∞=
=
0 !
) (
k
k ax
k e ax
h h
P h
P1( ) ≅1− 0( ) =
λ
순수 탄생 모형
순수 탄생 모형
– 시스템을 떠나는 사람이 없이 도착만 발생하는 모형 – T시간 동안 n명이 도착할 확률 P(n,T) = ?
“시스템 내에 T시간이 지나 n명이 존재할 확률”
) ( )]
( [
) , 1 (
)]
( 1
[ ) , ( )
,
(n T h P n T h o h P n T h o h o h
P(n,T +h) = P(n,T)⋅[1−
λ
⋅h +o(h)]+ P(n −1,T)⋅[λ
⋅h +o(h)]+o(h)P + = ⋅ −
λ
⋅ + + − ⋅λ
⋅ + +! ) ) (
,
( n
e T T
n P
T n − ⋅
= ⋅
λ
λ) , 1 (
) , ( )
, (
: 0
) ) (
, 1 (
) , ) (
, ( )
, (
T n
P T
n P T
n dT P
h d
h h T o
n P T
n h P
T n P h
T n P
−
⋅ +
⋅
−
=
→
+
−
⋅ +
⋅
−
− = +
λ λ
λ λ
이면
통해서 귀납법을
수학적 때,
일 )
, 0 (
0이라면 )
0 , ( 대해서 에
정수 양의
이고, 1
) 0 , 0 ( 만약
e T
T P
n P n
P
⋅
= −
=
=
λ
Poisson 분포 평균 =λT ,분산 =λT
[예] 순수 탄생 모형
휴일의 서울대공원에는 사람과 자동차로 뒤덮힌다. 공원측은 앞으로 자동차가 늘어날 것에 대비하여, 현재 8,000대가 주차할 수 있는 공간의 확장 여부를 결정 하고자 한다. 보통 휴일에는 입장객이 8시부터 들어오기 시작하여, 오후 1시 이 후에는 거의 들어오지 않는다. 이때까지는 입장객만 있을 뿐 공원을 떠나는 사람 이 거의 없다. 지금까지의 자료에 의하면 시간당 평균 1000대씩 입장하는데, 공 원측은 현재의 주차 공간이 포화될 확률이 5% 이하가 되도록 확장하고자 한다.
주차 공간을 1000대 단위로 증가 시킨다면, 몇 대 수준으로 확장하여야 하는가?
단위를 1000대로 하면, 도착률 λ=1, 기간은 T=5시간이 된다.
8
단위를 1000대로 하면, 도착률 λ=1, 기간은 T=5시간이 된다.
따라서 5시간동안의 입장객 수에 대한 확률분포는
! 5
! ) 5 1 ) (
5 , (
5 5
1
n e n
n e P
n
n − ⋅ −
⋅ =
=
032 . 0 ) 5 , (
, 068 . 0 ) 5 , (
, 133 . 0 ) 5 , (
10 9
8
=
=
=
∑ ∑
∑
∞=
∞
=
∞
= n n
n
n P n
P n
P
시스템 내에 10000대 이상의 자동차가 있을 확률이 0.032로 5%보다 작기 때문에 주차 공간을 2000대 더 확장하면 원하는 수준을 맞출 수 있게 된다.
입장객이 10000명 이상일 확률(n=10 이상)
이고,
포아송 분포
예
–
특정도시의 1주일동안 교통사고로 인한 사망자수,
–
대기업의 교환대에서 한 시간동안 걸려오는 전화의 수,
–
시험발사된 인공위성이 한번의 궤도를 운행 중에 부딪치는 운석 의 수,
–
제조품 중 불량품의 수 등
(M/M/1):(FCFS/ ∞/∞)
확률의 유도
–
(M/M/1):(FCFS/∞/∞)
도착/봉사 지수모델, 봉사자 1명, FCFS, 대기행렬 ∞, 도착고객 ∞
–
도착률 λ, 봉사율 µ의 지수분포 모델
(임의의 T 시점에서 매우 작은 시간 t가 흐르는 동안의 상태전이)10
0 1 2
….
n-1 n n+1λ ·t λ ·t λ ·t λ ·t λ ·t λ ·t λ ·t
µ ·t µ ·t µ ·t µ ·t µ ·t µ ·t µ ·t
….
) 1
( ) ( ) ( )
1 ( ) ( )
( 0 1
0 T t P T t P T t t
P + = ⋅ −
λ
+ ⋅µ
⋅ −λ
) 1
( ) ( ) ( )
1 ( ) 1
( ) ( )
1 ( ) ( ) ( )
(T t P 1 T t t P T t t P 1 T t t
Pn + = n− ⋅ λ ⋅ − µ + n ⋅ − µ ⋅ − λ + n+ ⋅ µ ⋅ − λ
만약 위의 식들이 T값에 영향 받지 않는 통계적 평형(statistical equilibrium) 상태, 즉 아래의 조건을 만족한다고 가정하면, 다음과 같이 변형된다.
일 때 0
), ( )
( ) (
) ( )
(
) ( )
( )
(
1 1
1 0
0
>
⋅ +
⋅ +
−
⋅
=
⋅ +
⋅
−
=
+
− T P T P T n
P T
dT P d
T P T
P T
dT P d
n n
n
n
λ λ µ µ
µ λ
dT T T P dP
T P T
Pn n n n
T ( ) 0,
, )
( , )
(
lim < ∞ = = ∀
∞
→
일 때 0
, )
( 0
0
1 1
1 0
>
⋅ +
⋅ +
−
⋅
=
⋅ +
⋅
−
=
+
− P P n
P
P P
n n
n
λ µ µ
λ
µ λ
P0
P
n
n ⋅
=
µ λ
µ
−
λ
=
∑
∞ ==
1
1 0
0
P P
n
n 이므로
−
⋅
=
∴
µ
λ µ
λ
1n
Pn
라면
<1 µ λ
이용률(ρ = λ/µ)
(M/M/1):(FCFS/ ∞/∞) 분석
(M/M/1):(FCFS/ ∞/∞)의 분석
–
시스템 내부의 평균 인원수
–
대기행렬에서 기다리는 평균 인원수 λ µ
λ µ
λ µ
λ
= −
−
⋅
⋅
=
⋅
=
∑ ∑
∞=
∞
=0 0
1
n
n
n
n n
P n L
12
–
시스템 내에서 보내는 평균 시간
–
대기행렬에서 기다리면서 보내는 평균 시간
) ) (
1 (
0
2
1 0
1
0
µ µ λ
λ µ
λ
−
= ⋅
−
=
−
⋅
=
⋅
− +
⋅
=
∑ ∑ ∑
∞=
∞
=
∞
=
L P
P n P
n P
L
n n n
n n
n q
λ µ λ
= −= L 1 W
) (
1
λ µ µ
λ µ
= ⋅ −− Wq = W
고속버스 매표소의 줄이 점점 더 길어지고 있다는 느낌이 들어서, 현재 매표소의 서비스에 대한 수리적 분석을 해 보고자 한다. 조사해 본 결과 매표소에는 평균 1분 당 8명 꼴로 도착하고 있으며, 매표소는 1분에 10명까지 표를 팔 수 있는 용량이 된 다고 한다. 이 매표소에서 표를 구입하기까지의 전체 시간(W), 줄을 서서 기다리는 데 보내는 평균 시간(Wq), 매표소에 평균적으로 있는 사람(L)과 줄 서서 기다리는 사람의 수(Lq)를 파악하여라.
λ=8, µ=10이므로
분 분
명 명
4 . 10 0
5 1 . 1 0
5 . 8 0
10 1 1
2 . 10 3
4 8 8 4 10
8
=
−
=
−
=
− =
− =
=
=
−
=
−
=
− =
− =
=
µ λ µ
µ λ λ µ
λ
W W
W
L L
L
q q
(M/M/1):(FCFS/N/ ∞)
확률의 유도
– 도착율 λ, 봉사율 µ의 지수분포 모델 – 대기행렬의 용량이 N까지 제한됨
– (M/M/1):(FCFS/ ∞/∞)에서 n = N 일 때의 제약 추가
14
– (M/M/1):(FCFS/ ∞/∞)에서 n = N 일 때의 제약 추가
– (M/M/1):(FCFS/ ∞/∞)와는 달리 이용률(ρ = λ/µ)이 1보다 작 지 않더라도 항상 정상해가 존재한다.
때 일
때 일 때
일
, 0
1 ,....,
2 , 1
, )
( 0
1
, 0
1
1 1
1 0
N n
P P
N n
P P
P
n P P
N N
n n
n
=
⋅
−
⋅
=
−
=
⋅ +
⋅ +
−
⋅
=
=
⋅ +
⋅
−
=
−
+
−
µ λ
µ µ
λ λ
µ λ
추가
P N N
−
= −
−
−
= + +
1 1 1
1
1 1
0
ρ
ρ µ
λ µ λ
이므로 이고
경우
일 : , 1
1 ]
1 [
0
0 =
⋅
=
≠
=
∑
= N
n n
n P P
P
µ
λ µ
ρ λ
N n P
P
P n
n
n ⋅ = ⋅ ≤ ≤
= 0
ρ
0, 1µ
λ
N N n
Pn ≤ ≤
= + , 0 1
1
이므로 경우
일 : , 1 1
] 2 [
0
1 ∀ =
=
=
=
∑
= +
N
n n i
i P i P
µ
Pρ λ
(M/M/1):(FCFS/N/ ∞) 분석
(M/M/1):(FCFS/N/∞)의 분석
– 시스템 내부의 평균 인원수
때 일
때 일
1
,
1
1 , ) 1 (
1
1 1
1
0
=
=
− ≠
+ +
⋅ −
= −
⋅
= +
+
∑
=ρ ρ ρ
ρ ρ
ρ ρ N
N P N
n
L N
N N N
n
n
16
– 대기행렬에서 기다리는 평균 인원수
실제 입력되는 부분 vs. 실제 처리되는 부분
일 때 1
2 ,
= N ρ =
' (1 ) '
q N
L = − = − L a L ρ − P a = real process load
(1 ) :
, ' (1 ) ( .)
e N
N
P effective arrival rate
a a P blocking prob
λ λ
ρ λ µ ρ
= −
= = = − ∵
–
시스템 내에서 보내는 평균 시간
–
대기행렬에서 기다리면서 보내는 평균 시간
(1 )
e N
L L
W = λ = λ − P
–
대기행렬에서 기다리면서 보내는 평균 시간
1
(1 )
q q
q
e N
L L
W W
µ λ λ P
= − = =
−
[예] (M/M/1):(FCFS/N/∞)
학교 이발관은 이발사 한 사람이 일을 하고 있다. 이발하는 데에는 평균 20분이 소요 되며, 한시간에 2명 꼴로 손님이 오고 있다. 이발소에는 의자가 5개 있는데, 손님들은 빈 의자가 없으면 이발을 다음 기회로 미룬다고 한다. 이 이발소에 갔을 때 평균적인 손님의 수, 의자에서 기다리는 손님의 평균 수, 이발을 받고 나올 때까지의 시간 및 기다리는데 소비되는 시간을 구하여라. 단, 손님의 도착시간 간격과 봉사시간은 지수 분포를 따른다고 한다.
N = 5
단위를 1시간으로 하면 λ=2, µ=3 이므로 ρ = 2/3
≠
1이다.18
단위를 1시간으로 하면 λ=2, µ=3 이므로 ρ = 2/3
≠
1이다.ρ ρ ρ
ρ
q
S
L L L
S P L S
−
=
− +
⋅
= − 2 +1 0
)!
1 (
) (
(M/M/S):(FCFS/ ∞/∞)
(M/M/S):(FCFS/∞/∞)의 분석
) / 1
(
!
!
1
1
0 0
S S
n
P S S
n
n
ρ ρ ρ
− + ⋅
=
∑
−=
ρ
ncf.
19
λ λ
q q
W L W L
=
=
봉사자 수 L W Lq Wq
10 15.0 1.6 6.0 0.7
20 9.0 1.0 0.01 0.0001
∞ 9.0 1.0 0 0
–
봉사자 수의 효과
봉사자 수에 따라 대기 행렬이 급격히 줄어든다.
단, ρ=9일 때
S n n
P P
n
n
= , ≤
0
! ρ
S S n
P S P
n S n
n
= ≥
−
! ,
0
ρ
[예] (M/M/S):(FCFS/∞/∞)
공대 식당이 새로 만들어져 학생 식당의 고객을 빼앗길 위험이 발생했다. 현재 학생 식당에서는 1개의 배식대로 1분에 약 25명의 학생에게 배식을 하고 있다. 학생들은 매분 20명씩 식당을 찾는다고 한다. 만약 기다리는 줄이 길면 학생들이 공대 식당으로 옮길 가능성이 커서, 식당 주인은 배식대의 개수를 늘려서 줄을 서서 기다리는 학생의 수를 평균 1명 이하로 떨어뜨리고자 한다. 이 시스템을 분석해서 몇 개의 배식대를 추가로 설치해야 될지 결정하시오.
λ=20, µ=25 이므로 ρ = 20/25 = 0.8 < 1이다.
20
16분 . 0 2 . 3
2분 . 20 0
4
2명 . 3 8 . 0 4
4명 20
25 20
=
=
=
=
=
=
=
−
=
−
=
− =
− =
=
λ λ
ρ λ µ
λ
q q
q
W L W L
L L
L
현재 1개의 배식대로 운영할 때
배식대를 2개로 할 때
97명 . 0 8 . 0 46 . 8 0
. 0
46 . 0
2 25 / 1 20
! 2
25 20
25 1 20
1
) / 1 (
!
!
1
3 0
1 1 2
0 0
≅ +
⋅
= +
=
≅
−
⋅
+
+
=
− + ⋅
=
+
−
∑
=ρ ρ
ρ ρ ρ
S S S
n
n
P L
S S
n P
01분 . 20 0
17 . 0
05분 . 20 0
97 . 0
17명 . 0 8 . 0 97 . 0
97명 . 0 8 . 0 46 .
! 0 1 ) 8 . 0 2 ( )!
1 ( )
( 2 0 2
≅
≅
=
≅
≅
=
=
−
=
−
=
≅ +
⋅ ⋅
= −
− +
⋅
= −
λ λ
ρ ρ ρ
q q
q
W L W L
L L
S P L S
배식대를 2개만 운영해도 평균 대기인수가 1명 이하로 떨어지므로 배식대를 1개만 더 설치하면 된다.
