대기행렬이론 개념과 용어 정리
대기행렬이론(Queueing Theory)은 예측 가능한 Queue Length, Waiting Line을 모델링하기 위한 학문이다.
OR(Operation Research)의 한 분야
ㄴ선형계획법, 정수계획법, 대기행렬이론 등이 포함된 최적화 과목
대기행렬이론을 정의하기 위해선 크게 3가지로 구분한다.
1. Interarrival Time Distribution (Rate = 𝜆, AVG = 1/𝜆) -> 손님이 어떤 분포로 도착하느냐
2. Processing Time Distribution -> 서버의 서비스 제공 시간 분포가 어떻게 되느냐
3. Service Discipline (FIFO, LIFO, Least PT, etc) -> 서비스 제공 규칙
Calling Population = 전체 고객 집단을 의미한다.
Open Queuing System -> 고객이 아주 많은 것을 의미함
Closed Queuing System -> 고객 도착율이 entity(고객)의 수에 영향을 받는다. 고객이 한정적
Non-homogenous customers -> 고객 집단은 대개 서로 다른 서비스를 요구한다.
Arrival Process
ㄴ> 보통 inter arrival process로 정의
1. 도착시간분포 (일정한가? 계획적인가? 확률분포를 따르는가?)
2. 시간을 고려한 도착률 (식당의 경우 항상 일정한 분포를 따르는게 아니라 점심/저녁시간에 고객 집중 분포)
3. 배치사이즈 - (일정할 수도 있고, 매 고객마다 랜덤할 수도 있고(doubly stochastic))
Queue (Waiting Line)
Queue Capacity란 서비스를 기다릴 수 있는 entity(고객) 수의 최대값을 의미한다.
시뮬레이션 툴 Simio에선 Server.InputBuffer이 Queue를 의미.
- Queue Discipline(Ranking Rule)
o FIFO – First In First Out
o LIFO – Last In First Out
o Largest/Smallest Value First: 우선 순위 규칙을 직접 정해서 설정할 수 있다.
- Queue Behaviors
o Balk – 서버에 도착했지만 줄은 서지 않은 entity
o Renege – 서버에 도착하여 줄을 섰다가 중간에 나가는 entity
o Jockey – 서버에 도착하여 줄을 섰다가 대기 시간이 더 짧은 줄로 옮기는 entity
Server Process
Server Capacity – 사용가능한 각 자원(resource)의 단위 수
Implicit Resource Modeling - 동일한 서버, 고객들이 아무 서버나 골라도 같은. 비통계적
Explicit Resource Modeling - 서버마다 각 자원 단위가 다르다. 어렵다. 통계적.
- 서버 자원은 Seize/Release 태도를 가진다 (고객이 서버를 이용할 땐 Seize, 이용 마치면 Release)
고객이 동시에 여러 서버 seize 가능 / 꼭 동시에 release 할 보장 없음 / 여러 단계 동안 지속적으로 seize할 수도 있음.
preemption - 특정 entity 우선권 제공
failure - 서버 고장나서 이용 불가할 수도 있음
Synchronized vs Buffered -> 동시에 여러 일 처리하거나, 동시에 할 수 없어서 대기가 생기거나
Queueing System Notation (Kendall)
A / B / C / N / K
A – Inter-arrival time distribution
B – Service time distribution
C – Number of parallel servers
N – 시스템 용량 (queue capacity + number of servers). 보통 무한.
K – size of calling population. 보통 무한.
N과 K는 누락되는 경우가 많다. (default값 무한대)
- A와 B의 분포는 아래의 경우로 나뉜다.
o M – Markovian (지수분포)
o D – 일정하거나 상수로 정해져있음.
o G – 일반적인 경우 (지수분포를 제외한 다른 모든 분포)
o GI – general independent
o PH – phase type
o Ek – Erlang with k stages
대기행렬이론에서 주요 측정 지표
o 𝑃𝑛 : Steady state probability of having n entities in system (이 대기행렬에 n명이 있을 확률)
o 𝜆: Arrival rate (단위 시간 당 이벤트 발생 수. 이미 평균의 개념이 들어가있다.)
o 1/𝜆: Inter-arrival time (고객과 고객 도착 시간 사이의 평균 간격)
o 𝜆𝑒: Effective arrival rate (기다리는 공간이 한정적일 때)
o 𝜇: Service rate of one server (단위 시간 당 서비스 제공 수)
o 1/𝜇: Average Proccess Time
o 𝜌: Server utilization (𝜆/𝜇) (긴 시간 동안 서버 이용률, 0 < 𝜆 < 𝜇이므로 1보다 작다)
시스템에서 평균 서비스 받고 있는 entity의 숫자와 동일
올라가면 안 좋고, 내려가면 좋음 (서버 이용률이 올라가면 대기시간이 길어짐을 의미하므로)
o 𝐿: Long-run average number of entities in system
시스템 안의 평균 entity 수
o 𝐿𝑄: Long-run average number of entities in queue
o 𝑊: Long-run average time in system (flow time) per entity
시스템 안 각 entity의 평균 시간
o 𝑊𝑄: Long-run average time in queue per entity