In this dissertation, a unified approach to continuous-time queueing models with exogenous priorities and server vacations is proposed. The concept of generalized exogenous priority discipline is introduced, and is shown to cover most exogenous priority queueing models in the literature. It is demonstrated that the stationary numbers of customers of each class in these priority queueing models decompose into a sum of three independent terms, each of which can be calculated from several simple terms. The arguments made to prove this stochastic decomposition are based on extensions of the delay cycle analysis and of the intuitive arguments employed by S. W. Fuhrmann and R. B. Cooper regarding the stochastic decomposition in single-class M/G/1 vacation models. The proposed stochastic decomposition leads to simplification and unification of the analysis of the queue-length distributions in continuous-time priority queueing models.
To illustrate that the proposed unified approach can be extended to discrete-time priority queueing models, a discrete-time queueing model with two-class discretionary priorities is analyzed. As the preemption mode of the discretionary priority discipline, all of the preemptive resume, preemptive repeat different, and preemptive repeat identical modes are considered. The Probability Generating Functions (PGFs) and first moments of queue lengths of each class are derived for all the three preemption modes in a unified manner. The obtained results include all the previous works on discrete-time priority queueing models with general service times and structured inputs as their special cases.
The proposed unified approach is also shown to be extended to the analysis of joint queue-length distributions in priority queueing models in some limited conditions.
연구배경
`우선순위 규칙(Priority disciplines)`이란, 통신, 컴퓨터 시스템 등 고객(서비스 요청)별로 차별화된 `서비스 품질(QoS; Quality of Service)`을 제공해야 하는 시스템에서 이용하는 유용한 스케쥴링 방법이다. `우선순위 (규칙을 가지는) 대기행렬 모델`은 이러한 상황에 놓인 시스템의 성능 분석을 위한 유용한 도구이며, 통신, 컴퓨터, 제조공학 등에 다양한 응용분야를 가지고 있어 관련 연구가 활발히 수행되어 왔다. 특히, 최근 서비스 품질 차별화의 중요성이 대두되면서 그 중요성이 더해지고 있다.
대기행렬 모델에서 우선순위 규칙은 시스템의 내부 상태에 의해 서비스의 우선순위가 결정되는 `내인성 우선순위 규칙(Endogenous priority disciplines)`과 고객 클래스에 의해서만 우선순위가 결정되는 `외인성 우선순위 규칙(Exogenous priority disciplines)`으로 대별된다. 외인성 우선순위 규칙은 다시 상위 클래스의 고객이 하위 클래스 고객의 진행 중인 서비스를 중단(선점)할 수 없는가, 있는가에 따라 `비선점우선순위(Non-preemptive)`와 `선점우선순위 규칙(Preemptive priority disciplines)`으로 나뉘며, 두 우선순위 규칙에 대해서는 많은 연구와 응용이 이루어져 왔다.
그러나 선점, 비선점 우선순위 규칙은 실제 적용시 고유의 약점을 가지고 있다. 선점 우선순위 규칙의 경우 하위 클래스 고객의 서비스 품질에 큰 저하를 야기할 수 있으며, 비선점 우선순위 규칙의 경우 상위 클래스 고객의 서비스 품질에 큰 저하를 야기할 수 있다. 따라서 이러한 문제점을 해결하기 위해 선점과 비선점 우선순위 규칙의 혼합형 우선순위 규칙에 대한 연구가 필요하나 이러한 연구는 몇몇 시도로 제한되고 있다.
그 이유로는, 지금까지의 외인성 우선순위 규칙을 가지는 대기행렬 모델은 특정 우선규칙에 대해 개별적으로 연구가 진행됨에 따라 통합된 시각이 부족하였으며, 개별 우선순위 정책을 가지는 대기행렬 모델의 분석의 복잡성으로 인해 새로운 규칙의 제안 및 분석이 한계를 가지고 있었기 때문으로 판단된다. 따라서, 개별적으로 다루어지던 외인성 우선순위 규칙을 가지는 대기행렬 모델에 대한 통합적 분석 방법이 필요하다고 할 수 있다.
이러한 통합된 분석 방법의 첫번째 장점은 분석의 단순화이다. 어떤 응용 시스템의 문제를 해결하기 위해 특정한 우선순위 규칙이 제시되었을 때, 관련 대기행렬의 분석은 공통적으로 성립하는 결과를 이용하여 특정 우선순위 규칙에 의해 달라지는 요소에 대한 분석으로 단순화될 수 있다. 두번째 장점은, 통합된 시각의 획득이다. 개별적 연구에서는 확인하기 어려운 선점, 비선점 및 혼합형 우선순위 규칙 등 다양한 외인성 우선순위 규칙에 따른 시스템 성능의 변화에 대한 분석을 통합적으로 조망할 수 있다.
연구 주요 내용
본 연구에서는 다음과 같은 주제를 다룬다.
첫째, 지금까지 독립적으로 연구되던 비선점, 선점, 혼합형 우선순위 규칙의 공통된 특성을 밝혀내고 이를 통해 `일반 외인성 우선순위 규칙(Generalized exogenous priority disciplines)`이라는 범주로 개념화함으로써 관련 대기행렬 모델을 통합적으로 분석할 수 있는 개념틀을 제시한다.
둘째, `일반 외인성 우선순위 규칙`을 가지는 대기행렬 모델에 대한 통합적 분석을 위해 고객수 분포에 기반한 지체사이클 분석 (Delay Cycle Analysis) 절차를 제시한다.
- 지금까지의 우선순위 대기행렬에 대한 분석은 대기시간에 대한 분석이 주종을 이루었다. 특히, 지체사이클 분석과 레벨횡단법을 이용한 대기시간의 분석은 나름의 통합된 분석체계를 제시해 왔다.
- 그러나, 위의 방법은 분포 형태의 Little 법칙이 만족되지 않는 경우는 적용에 한계를 가지고 있어 다양한 우선순위 대기행렬 모형을 통합적으로 분석하는 데 한계를 가지고 있다.
- 본 연구에서는 고객수 분포에 기반하여 우선순위 대기행렬의 지체사이클 분석 기법을 제시하고, 이를 통해 상위 클래스에 대해 완전서비스를 하는 `일반 외인성 우선순위 규칙` 및 완전 서비스 휴가 정책을 갖는 우선순위 대기행렬 대한 고객수 분포의 통합적 형태를 제시한다.
셋째, `일반 외인성 우선순위 규칙` 및 `일반 휴가 정책`을 가지는 우선순위 대기행렬에서 항상 성립하는 고객수 분포(Queue-length distributions)의 확률적 분해 (Stochastic decomposition) 속성을 탐구하고, 이를 통해 고객수 분포의 통합적 분석 방법을 제시한다.
- 확률적 분해 속성이란 어떤 확률 분포가 여러 개의 독립된 확률 분포의 Convolution 형태로 표현되는 것을 의미한다.
- 확률적 분해 속성의 대표적인 예가 `일반 휴가 M/G/1 대기행렬 모델`의 고객수 분포가 휴가가 없는 M/G/1 대기행렬 모델의 고객수 분포와 휴가 중일 때의 고객수 분포로 분해되는 성질이다. 따라서 `일반 휴가 정책`의 성질을 따르는 모든 대기행렬 모델의 분석은 휴가 중일 때의 고객수 분포에 대한 분석으로 단순화 된다.
- 본 연구에서는 `일반 외인성 우선순위 규칙`을 따르며, `일반 휴가 정책`을 따르는 대기행렬에서 고객수 분포의 확률적 분해 속성을 연구함으로써, 관련 대기행렬의 분석이 단순화할 수 있는 통합적 방법을 제시한다.
- 통합적 분석 방법의 유용성을 보이기 위해 간단한 3가지 우선순위 대기행렬 모델에 대한 분석을 수행하여 기존 연구 결과와 비교한다.
넷째, 연속시간 우선순위 대기행렬의 고객수에 대한 통합적 분석 방법이 이산시간 우선순위 대기행렬 모델의 분석으로 확장될 수 있음을 예시한다.
- 일반 서비스 시간을 가지고 시간 Slot 당 도착한 고객수가 독립적이고 동일한 분포를 따르는 고객 클래스가 2개인 이산 시간 우선순위 대기행렬 모델을 분석한다.
- 우선순위 규칙으로는 `일반 외인성 우선순위 규칙` 중 하나인 Discretionary priority 규칙을 가정한다.
- 고객수 분포에 대하여 통합적 분석 방법을 통하여 세가지 서로 다른 Discretionary priority 이산시간 대기행렬을 통합적으로 분석한다. 이를 통해 획득된 결과가 기존 일반 서비스 시간을 갖는 이산시간 대기행렬 모델의 연구를 특수 예로 가지는 매우 일반적 결과임을 보인다.
- 수치 예제를 통해 Discretionary priority 우선순위 규칙을 이용하면 고전적 우선순위 규칙을 사용하는 경우보다 시스템 성능을 보다 미세하게 조정할 수 있음을 보인다.
마지막으로, 본 연구는 각 클래스별 고객수의 주변 분포에 대한 통합적 분석 방법이 결합 고객수 분포의 분석으로 확장될 수 있음을 예시한다.
