In this dissertation, we consider the stationary queue length of the general multi-server GI/G/c queue with finitely many r waiting places, which has applications in various areas such as computer, communications and industrial manufacturing systems. As a result, using the sample-path approach combined with some fundamental results such as the one-step rate-balance equation, the elementary renewal theorem, the renewal reward theorem, and the stochastic mean value theorem, we first obtain the exact transform-free expressions for the stationary queue-length distribution of the GI/G/c/c+r queue in product form. Making use of these results, we then also present a simple two-moment approximation for the queue-length distribution. From this, approximations for some important performance measures, such as the loss probability, the mean queue length, and the mean waiting time, are also obtained. In addition, we propose an approximation for the minimal buffer size that keeps the loss probability below an acceptable level. Extensive numerical experiments show that our approximation is extremely simple yet fairly good in its performance.
The results presented in this dissertation would be valuable not only to queueing theorist but also to practitioners who prefer simple and quick practical answers to their finite-capacity multi-server queueing systems.
1. 서론
서비스를 제공하는 서버와 서비스를 요구하는 고객으로 구성된 대기행렬은 우리의 일상생활에서 흔히 볼 수가 있다. 대기행렬모형 (queueing model)은 시스템에 내재된 불확실성 (고객의 서비스 요구 시점 및 서비스 요구량 등이 확률과정에 의해 발생)에 의해 발생하는 대기행렬현상(waiting-line phenomena)을 묘사하고 형상화한 수학적 모형이다 (아래 그림 참고). 그리고 대기행렬이론 (queueing theory)은 이와 같은 대기행렬 모형을 확률적으로 분석하여, 시스템 운용 및 설계에 관한 최적화 연구를 수행하는 운용과학(Operations Research)의 한 분야라고 말할 수 있고, 최근 생산, 제조, 통신 및 각종 서비스 시스템 등을 대상으로 광범위하게 활용되고 있다.
◁그림 삽입▷(원문을 참조하세요)
대기행렬모형을 분석하는 다양한 방법이 알려져 있지만, 예를 들어 부가변수법 (supplementary variable technique), 레벨횡단법 (level-crossing technique), 행렬기하법 (matrix-geometric method), 본 논문에서는 샘플경로에 근거한 분석방법에 주목한다. 샘플경로는 확률과정의 실현(實現)으로 가시적인 분석 및 해석이 가능하므로, 확률과정을 분석함에 있어 이론적/실용적인 면에서 매우 유용하고 이해하기 쉬운 장점이 있다.
다음에서는 샘플경로와 본 논문의 연구대상인 유한용량 복수서버 GI/G/c 대기행렬모형 에 대해 알아본다.
1.1. 샘플 경로 (Sample Path)
샘플경로는 시간에 따른 확률과정(stochastic process)의 상태 변화에 대한 하나의 실현(實現)이다. 대표적인 예로, 대기행렬시스템의 고객수 과정 (즉, 시간에 따른 고객의 도착 및 이탈의 추이)을 생각해 볼 수 있으며, 이는 다음의 그림과 같다.
◁그림 삽입▷(원문을 참조하세요)
샘플경로에 근거한 분석법은 다음과 같은 특징을 갖는다.
ㆍ확률과정의 실현을 분석한다. 즉, 위의 그림에서와 같이 이미 기록된 시간 축 위의 상태 변화 추이를 분석하는 것이므로, 확률적인 가정이 필요하지 않다.
ㆍ그림을 통한 가시적인 설명이 가능하므로, 좀더 직관적이고 쉽게 시스템을 이해할 수 있다.
1.2. 유한용량 복수서버 대기행렬시스템 (Finite-capacity multi-server queueing system)
대기행렬시스템을 수리적으로 모형화 한 것 중, 가장 일반적인 모형중의 하나가 유한용량 복수서버 GI/G/c 대기행렬모형이다. 유한용량 GI/G/c 모형에서는, 고객들의 도착간 간격과 서비스시간이 i.i.d.(independent and identically distributed) 일반분포를 따르며, c명의 서버가 고객들을 서비스한다. GI/G/c 모형은 이미 많은 학자들에 의해 난공불락(難攻不落)의 모형이라 일컬어질 만큼 분석이 매우 어렵다는 것이 알려져 있다. GI/G/c 모형의 특수한 경우인 단수서버 GI/G/1 모형 및 포아송 도착과정을 갖는 복수서버 M/G/c 모형의 경우 조차도 분석이 매우 어려우며, 고객수 분포는 물론이고 심지어는 기대치에 대해서도 M/G/1이나 GI/M/c와 같은 특수한 경우를 제외하고는 실용적인 결과가 거의 알려진 바가 없다. 이와 같이 GI/G/c 모형의 고객수 분포 및 기대치를 완벽하게 해결하는 것은 매우 어려운 문제이다.
이러한 분석의 어려움을 해결하고자 기존에는 근사적인 접근을 통한 분석이 주류를 이루었다. 하지만, 기존의 근사 결과들이 대부분 복잡한 방정식 및 축차식 형태이거나 변환형태로 주어져 있기 때문에 쉽게 계산해서 사용하기에는 무리가 있다.
본 논문에서는 유한용량 복수서버 GI/G/c 모형의 안정상태 고객수 분포를 해결하기 위한 방법으로 샘플경로를 활용한다.
2. 본론: 샘플경로를 이용한 고객수 분포의 분석 (3장)
유한용량 복수서버 GI/G/c 대기행렬모형의 고객수 과정 샘플경로를 토대로, 샘플경로 버전의 재생보상정리 (Y=λX)를 활용하면 안정상태 고객수 분포에 관해 세가지 형태의 관계식을 얻을 수 있다 (식 (3.1), (3.2),(3.3) 참고). 그리고, 이를 연립하여 정리하면 두가지 형태로 고객수 분포를 표현할 수 있다 (식 (3.4), (3.5) 참고). 각각의 결과는 변환이 아닌(transform-free) 명시적 형태로 주어지지만, 결과 표현식에는 일반적으로 쉽게 구하기 힘든 미지항들을 포함하고 있다. 그럼에도 불구하고 고객수분포의 결과 표현식은 다음과 같이 유용하게 활용될 수 있다.
첫째로, GI/G/c 틀의 다양한 대기행렬모형의 안정상태 고객수 분포를 일관성 있게 구할 수 있다.
둘째로, 고객수 관련 성능척도 (loss probability, 평균대기고객수)에 관한 부등식 및 상/하한 개발에 활용할 수 있다.
셋째로, 안정상태 고객수 분포들간의 관계, 예를 들어 ASTA 성립조건, 비례관계(proportionality), 쌍대관계 (duality), 규명에 활용할 수 있다.
마지막으로 고객수 분포 결과식 내의 미지항들을 적절히 근사하면 도착 간격과 서비스시간의 평균과 분산만을 가지고도 안정상태 고객수분포를 잘 근사할 수 있는 실용적인 근사식을 제안할 수 있다 (4장).
3. 본론: 2차 적률 근사 (4, 5장)
3장에서 유도한 고객수 분포 표현식을 활용하여 고객수 분포 및 주요 성능척도, 손실 확률 (loss probability), 평균대기고객수 및 평균대기시간에 대한 2차 적률 (Two-Moment) 근사식을 제안한다 (4장). 그리고 추가적으로 실제 다양한 서비스 시스템들을 설계할 때 가장 중요한 이슈 중의 하나로 고려되는 최적의 버퍼크기, 즉 QoS 수준의 시스템 성능 (고객의 손실률)을 만족시키는 최소의 버퍼크기, 에 관한 2차 적률 근사식을 제안한다 (5장). 본 논문에서 제안한 근사식은 기존의 근사식에 비해 상대적으로 간단하고 계산하기 쉬움에도 불구하고 거의 비슷한 성능을 보인다. 특히 도착간격/서비스시간의 변동계수가 1에 가깝거나, 교통밀도 (traffic intensity)가 높은 경우에 매우 안정된 성능을 보인다 (Table 4.1~4.7 & 5.1~5.2).
본 논문에서 제안한 근사식들은 도착간 간격 및 서비스 시간의 평균과 분산만으로 이루어진 식으로 실제 대기행렬시스템의 도착 및 서비스 과정의 분포를 추정하기 어려울 때, 쉽고 빠른 근사식을 원하는 현장의 실무자들이 각자의 시스템을 최적으로 설계하고 효율적으로 운용하는데 유용하게 활용될 수 있을 것이다. 또한 간단한 계산 만으로도 참값에 근접하는 근사값을 제공하므로 시스템을 설계하는 초기 시점에 “Rule of thumb” 추정치로써 효과적으로 사용될 수 있으며, 시간적 비용적 효율성 면에서 시뮬레이션과 상호보완적으로 이용될 수 있을 것이다.
3. 결론
본 논문에서는 샘플경로에 근거한 가시적이고 간단한 방법을 활용하여 유한용량 복수서버 GI/G/c 대기행렬모형의 고객수 분포를 분석하였다. 이를 토대로 다양한 성능척도 (loss probability, 평균대기시간, 최적버퍼크기 결정식)에 관한 2차 적률 근사식을 제안하였다. 본 논문에서 제안하는 샘플경로 접근법은 GI/G/c 대기행렬모형뿐만 아니라 다양한 확률과정의 분석에 유용하게 활용될 수 있을 것이다. 또한 변환이 아닌 형태의 안정상태 고객수 분포 표현식은 각종 GI/G/c 틀의 확률시스템 분석에 이론적/근사적 토대가 될 수 있을 것이며, 이로부터 얻어진 근사식은 실제 대기행렬시스템을 최적으로 설계하고 그 운용의 효율성을 도모하는 데에 유용하게 활용될 수 있을 것이다.
