대기행렬이론

3. 구성 요소 및 표기법

대기행렬 시스템은 서버(Server), 대기실(Waiting Room), 고객(Customer)으로 구성된다.^[5]

• '''서버(Server):''' 서비스를 제공하는 주체. ATM, 슈퍼마켓의 계산원 등이 서버의 예시이다.
• '''대기실(Waiting Room):''' 고객이 서비스를 받기 위해 대기하는 장소. 은행 내 대기 공간, 슈퍼마켓 계산대 앞 줄 등이 해당된다.
• '''고객(Customer):''' 서비스를 받기 위해 시스템에 도착하여 대기하는 대상. ATM을 이용하는 고객, 계산대에서 계산을 기다리는 고객 등이 고객에 해당한다.

• A: 고객의 도착 과정 (Arrival process)
• B: 서비스 시간 분포 (Service time distribution)
• C: 서버 수 (Number of servers)
• D: 대기실을 포함한 시스템의 용량 (System capacity, 무한대인 경우는 생략)

• M/M/1 대기열: 단일 서버가 푸아송 과정에 따라 도착하고(도착 간 시간 간격이 지수 분포를 따름) 지수 분포 서비스 시간을 갖는 작업을 처리하는 모델. (M은 마르코프 과정을 나타냄)
• M/G/1: 일반적인 도착 과정을 가지며, 서비스 시간에 대한 임의의 확률 분포를 나타내는(G는 "일반"을 의미) 단일 서버 대기행렬
• G/D/1: 일반적인 도착 과정을 가지며, 일정 분포를 따르는 서비스 시간을 갖는 단일 서버 대기행렬

4. 핵심 개념 및 분석

대기행렬이론은 대기열의 길이, 대기 시간, 서비스 시간 등 시스템의 성능을 분석하는 데 필요한 다양한 지표를 제공한다. 이러한 분석에는 다음과 같은 개념들이 사용된다.

• 출생-사망 과정: 대기열 내 고객 수의 변화를 확률적으로 모델링하는 방법이다. 도착은 고객 수 증가, 출발은 고객 수 감소를 의미하며, 각 상태에 대한 도착률과 출발률을 통해 시스템의 상태 변화를 나타낸다.

• 균형 방정식: 시스템이 안정 상태에 도달했을 때, 각 상태에 있을 확률을 나타내는 방정식이다. 이 방정식을 통해 각 상태에 있을 확률을 계산할 수 있다.
• 리틀의 법칙: 시스템 내 평균 고객 수 (L), 평균 도착률 (λ), 평균 체류 시간 (W) 간의 관계 (L = λW)를 나타내는 법칙이다.

• A: 고객의 도착 과정
• B: 서비스 시간 분포
• C: 서버 수
• D: 시스템 용량 (생략 가능)

4. 1. 단일 대기열 노드 (Single Queueing Node)

• ''λ'': 도착률 (각 고객이 도착하는 시간 간격의 역수, 예: 초당 10명의 고객)
• ''μ'': 평균 서비스 시간의 역수 (동일 시간 단위당 연속적인 서비스 완료의 예상 횟수, 예: 30초당)
• ''n'': 시스템 내 고객 수를 특징짓는 매개변수
• ''Pn'': 정상 상태에서 시스템 내에 ''n''명의 고객이 있을 확률

4. 2. 서비스 방식 (Service Disciplines)

• 선입 선출(FIFO): '선착순'(FCFS)이라고도 불리며, 가장 오래 기다린 고객이 먼저 서비스를 받는 방식이다.^[21][22]

• 후입 선출(LIFO): 가장 짧은 대기 시간을 가진 고객이 먼저 서비스를 받는 방식이다. 스택이라고도 한다.^[22]
• 프로세서 공유: 서비스 용량이 고객 간에 균등하게 공유되는 방식이다.^[22]
• 우선순위: 우선순위가 높은 고객이 먼저 서비스를 받는다.^[22] 우선순위 큐에는 '비선점형'(서비스 중인 작업이 중단될 수 없음)과 '선점형'(서비스 중인 작업이 더 높은 우선순위의 작업에 의해 중단될 수 있음) 두 가지 유형이 있다. 어떤 모델에서도 작업은 손실되지 않는다.^[23]
• 최단 작업 우선: 다음에 서비스할 작업은 크기가 가장 작은 작업이다.^[24]
• 선점형 최단 작업 우선: 다음에 서비스할 작업은 원래 크기가 가장 작은 작업이다.^[25]
• 최단 잔여 처리 시간: 다음에 서비스할 작업은 남은 처리 요구 사항이 가장 작은 작업이다.^[26]

4. 3. 고객 행동 (Customer Behavior)

5. 대기행렬 네트워크 (Queueing Networks)

대기 행렬 네트워크는 여러 대기열이 '고객 라우팅'으로 연결된 시스템이다. 고객이 한 노드에서 서비스를 받으면 다른 노드에 합류하여 서비스를 위해 대기하거나 네트워크를 떠날 수 있다.

''m''개의 노드로 구성된 네트워크의 경우, 시스템의 상태는 각 노드에 있는 고객의 수를 나타내는 ''m''차원 벡터 (''x''₁, ''x''₂, ..., ''x''_''m'')로 설명할 수 있다.

가장 간단한 비자명 대기열 네트워크는 직렬 대기열이라고 한다.^[28] 이 분야의 첫 번째 중요한 결과는 효율적인 곱 형태 정상 분포가 존재하고 평균값 분석^[31] (처리량 및 체류 시간과 같은 평균 지표를 허용)을 계산할 수 있는 잭슨 네트워크이다.^[29][30][32] 네트워크의 총 고객 수가 일정하게 유지되는 경우 해당 네트워크를 ''폐쇄 네트워크''라고 하며, 고든-뉴웰 정리에 의해 곱 형태의 정상 분포를 갖는 것으로 나타났다.^[33] 이 결과는 BCMP 네트워크로 확장되었으며,^[34] 여기서 매우 일반적인 서비스 시간, 방식 및 고객 라우팅을 가진 네트워크가 곱 형태의 정상 분포를 나타내는 것으로 나타났다. 정규화 상수는 1973년에 제안된 부젠 알고리즘으로 계산할 수 있다.^[35]

켈리 네트워크와 같이 서로 다른 고객 클래스가 서로 다른 서비스 노드에서 서로 다른 우선 순위 수준을 경험하는 고객 네트워크도 조사되었다.^[36] 또 다른 유형의 네트워크는 1993년 에롤 젤렌베가 처음 제안한 G-네트워크이다.^[37] 이러한 네트워크는 고전적인 잭슨 네트워크와 같이 지수 시간 분포를 가정하지 않는다.

어떤 시점에도 활성화될 수 있는 서비스 노드에 제약이 있는 이산 시간 네트워크에서, 최대 가중치 스케줄링 알고리즘은 각 작업이 단일 서비스 노드만 방문하는 경우 최적 처리량을 제공하는 서비스 정책을 선택한다.^[21] 작업이 여러 노드를 방문할 수 있는 보다 일반적인 경우에는 백프레셔 라우팅이 최적 처리량을 제공한다. 네트워크 스케줄러는 더 큰 네트워크의 특성에 영향을 미치는 대기열 알고리즘을 선택해야 한다.^[38]

6. 응용 분야

대기행렬이론은 다양한 분야에서 시스템 성능 분석 및 최적화에 활용된다.^[5] 생산 활동에서 노동자, 자재, 기계 등이 다음 작업을 기다리는 시간을 최소화하고 유휴 시간을 줄이기 위해 개발되었다. 예를 들어, 공장 내 기계 설비 수, 정비공 수, 트럭 수, 항구의 독 수 등을 결정하는 데 활용된다.

대기행렬이론은 경영과학의 주요 연구 분야 중 하나로, 기업이 여러 문제를 해결하는 데 사용된다. 대기행렬 분석은 확률적 분석을 통해 시스템의 운영 특성을 계산하고, 이를 통해 개선 방안을 찾는다.^[5] 주요 대기행렬 모델에는 단일 서버 대기열 시스템과 다중 서버 대기열 시스템이 있으며, 서비스 시간, 대기열 길이, 호출 모집단 등에 따라 더 세분화될 수 있다.^[5]

컴퓨터 과학과 정보 기술 분야에서도 널리 응용된다. 네트워킹에서 라우터와 스위치의 패킷 전송, 시스템 최적화, 응답 성능 및 자원 활용 효율성을 높이는 데 사용된다.

또한, 일상생활에서도 대기행렬이론은 슈퍼마켓 줄서기, 대중교통 기다리기 등 다양한 상황에 적용되어 사용자 만족도를 높이는 데 활용된다.

응용 수학과 컴퓨터 과학에 기반을 둔 대기행렬이론은 대기열 시스템의 효율성을 이해하고 최적화하는 데 중요한 역할을 한다. 교통 시스템, 컴퓨터 네트워크, 통신, 서비스 운영 등 다양한 분야에서 필수적이다.

대기행렬이론은 도착 과정과 서비스 과정과 같은 핵심 개념을 통해 시스템 효율성을 측정한다. 평균 대기열 길이, 평균 대기 시간, 시스템 처리량 등의 지표를 사용하여 성능을 개선하고 대기 시간을 줄이는 의사 결정을 지원한다.

켄달의 표기법은 D. G. 켄달이 1953년에 대기행렬 모델을 통일하기 위해 도입한 표기법이다. A/B/C/D 형태로 모델의 특징을 나타내며, 현재에도 널리 사용된다.

대기행렬은 자원 이용 요구를 추상화한 수리 모델이다. 은행의 ATM을 예로 들 수 있으며, ATM을 서버, 대기 공간을 대기실, 이용 고객을 고객으로 간주한다. 콜센터, 전화 교환기, 전화망, 인터넷, 서버나 라우터 등의 버퍼 설계, 지능형 교통 시스템, 생산 시스템, 공항, 병원 시설 설계 등 다양한 분야에 응용된다.

7. 추가 내용

학술 연구 분야에서는 "queuing" 대신 "queueing" 철자를 일반적으로 사용한다.^[39] 실제로 이 분야의 대표적인 저널 중 하나는 ''대기 시스템''(Queueing Systems)이다.

평균장 모델은 큐의 수 ''m''이 무한대로 접근함에 따라 경험적 측도(다양한 상태에 있는 큐의 비율)의 극한 거동을 고려한다. 네트워크 내의 주어진 큐에 대한 다른 큐의 영향은 미분 방정식을 사용하여 근사화된다. 결정론적 모델은 원래 모델과 동일한 정상 분포로 수렴한다.^[39]

높은 점유율(1에 가까운 활용률)을 가진 시스템에서 대기열 길이 과정을 반사 브라운 운동,^[40] 오른스타인-울렌벡 과정, 또는 더 일반적인 확산 과정으로 근사하기 위해 heavy traffic 근사를 사용할 수 있다.^[41] 브라운 운동의 차원은 대기열 노드의 수와 같으며, 확산은 음이 아닌 orthant로 제한된다.

유체 모형은 시간과 공간에서 과정을 확장하여 얻은 대기 행렬 네트워크의 연속적인 결정론적 유사체로, 이기종 객체를 허용한다. 이 확장된 궤적은 시스템의 안정성을 증명할 수 있는 결정론적 방정식으로 수렴한다. 대기 행렬 네트워크가 안정적이지만 불안정한 유체 극한을 가질 수 있다는 것이 알려져 있다.^[42]

참조

_[1] 서적 Probability, Statistics and Queueing Theory PHI Learning
_[2] 웹사이트 Performance by Design: Computer Capacity Planning by Example http://www.cs.gmu.ed[...] 2009-07-08
_[3] 뉴스 Hershey Medical Center to open redesigned emergency room http://www.pennlive.[...] 2009-03-02
_[4] 서적 Using queuing theory to analyse completion times in accident and emergency departments in the light of the Government 4-hour target https://openaccess.c[...] Cass Business School 2006-12
_[5] 서적 Introduction to management science Pearson 2019
_[6] 문서 Algorithmic Analysis of Queues Wiley
_[7] 간행물 Stochastic Processes Occurring in the Theory of Queues and their Analysis by the Method of the Imbedded Markov Chain
_[8] 간행물 An application of queuing theory to SIS and SEIS epidemic models 2010
_[9] 웹사이트 Agner Krarup Erlang (1878-1929) | plus.maths.org http://pass.maths.or[...] Pass.maths.org.uk 1997-04-30
_[10] 간행물 Editorial introduction
_[11] 간행물 The theory of probabilities and telephone conversations http://oldwww.com.dt[...]
_[12] 간행물 The first Erlang century—and the next
_[13] 문서 Ueber eine Aufgabe der Wahrscheinlichkeitstheorie
_[14] 간행물 Applied Probability in Great Britain
_[15] 문서 Stochastic processes occurring in the theory of queues and their analysis by the method of the imbedded Markov chain
_[16] 문서 Problèmes Stochastiques posés par le phénomène de formation d'une queue
_[17] 간행물 The single server queue in heavy traffic 1961-10
_[18] 간행물 A stable recursion for the steady state vector in markov chains of m/g/1 type
_[19] 서적 Proceedings of 14th European Workshop
_[20] 간행물 Simulation and queueing network modeling of single-product production campaigns https://www.scienced[...] 1992
_[21] 서적 Business Process Modeling, Simulation and Design https://books.google[...] Pearson Education India 2011
_[22] 문서 Queueing Systems
_[23] 서적 Performance Modeling and Design of Computer Systems
_[24] 서적 Modern Operating Systems https://books.google[...] Pearson
_[25] 서적 Performance Modeling and Design of Computer Systems
_[26] 서적 Performance Modeling and Design of Computer Systems
_[27] 간행물 A Multiclass Retrial System With Coupled Orbits And Service Interruptions: Verification of Stability Conditions
_[28] 웹사이트 Archived copy http://www.stats.ox.[...] 2018-08-02
_[29] 간행물 Networks of Waiting Lines
_[30] 간행물 Jobshop-like Queueing Systems 1963-10
_[31] 간행물 Mean-Value Analysis of Closed Multichain Queuing Networks
_[32] 간행물 On the arrival theorem for communication networks https://research.vu.[...]
_[33] 간행물 Closed Queuing Systems with Exponential Servers
_[34] 간행물 Open, closed and mixed networks of queues with different classes of customers
_[35] 간행물 Computational algorithms for closed queueing networks with exponential servers http://www-unix.ecs.[...]
_[36] 논문 Networks of Queues with Customers of Different Types
_[37] 논문 G-Networks with Triggered Customer Movement 1993-09
_[38] 논문 Applications of Queueing Theory https://doi.org/10.1[...] 1982
_[39] 서적 2008 Fifth International Conference on Quantitative Evaluation of Systems
_[40] 논문 Diffusion approximations for open queueing networks with service interruptions
_[41] 논문 Diffusion Approximation for Open State-Dependent Queueing Networks in the Heavy Traffic Situation
_[42] 논문 A stable queueing network with unstable fluid model