The objective of this study is to present an efficient method, based on decomposition approach, which yields tight throughput upper bounds for the general open and closed queueing networks with finite buffer capacities and under any commonly used blocking mechanism. Also, by using the throughput upper bound, we develop several procedures to effectively solve the design problems of queueing networks.
First, we propose a simple method obtaining the throughput upper bounds for three special networks - tandem, split, and merge configurations - under various blocking mechanisms. Also, a throughput upper bound for a general open network is given by a recursive method. Computational experiments confirm that our method is superior to other existing methods.
Second, we extend the proposed method to multiple server system and two special closed networks, cycle network and central server network.
Third, we show that the existing throughput-bounding methods for twostage tandem queueing networks are improved via the duality results. Besides, we show the invalidity of the method proposed by Onvural and Perros by illustrating two counter-examples.
Fourth, we deal with the following optimal design models of queueing networks: (i) arrangement of station (or server assignment), (ii) allocation of service rates (or workload), (iii) allocation of extra servers, and (iv) allocation of buffers. The computational experience well demonstrates the effectiveness of our approach, so it gives many implications to system designers.
Finally, some future research directions are suggested.
본 논문은 각종 통신, 교통, 생산체계의 설계와 운용에 유용하게 쓰이는 $\ulcorner$유한용량을 갖는 대기행렬망$\lrcorner$에서의 대표적인 성능척도인 $\ulcorner$산출율$\lrcorner$ (throughput, 단위시간당 흐름량)에 대한 분석을 다룬다. 여러가지 $\ulcorner$막힘$\lrcorner$ (blocking) 형태를 갖는 일반적인 망구조하에서, 정확한 산출율을 얻기가 어렵기 때문에, 그 대신에 산출율의 상한을 구할 수 있는 매우 간단한 방법을 제시한다. 또한 그 상한에 대한 결과가 효율적인 자원배분을 필요로하는 대기행렬망의 설계에 이용될 수 있음을 보여준다.
본 논문의 내용을 간략히 요약하면 다음과 같다.
첫째, 각 서비스 시스템이 단일서비스제공자를 갖는 개방대기행렬망 중에서, 직렬구조, 분할구조, 병합구조 등 특수한 세가지 망구조에서의 산출율의 상한을 각각 다양한 막힘 형태하에서 구할 수 있는 방법을 제시한다. 이 방법은 전체 대기행렬망을 독립적인 여러개의 시스템으로 분해하는 기법에 기초를 둔다. 다음으로 일반적인 개방 대기행렬망에 대한 산출율의 상한을 얻을 수 있는 간단한 순환적 방법을 제시한다. 이렇게 구한 산출율의 상한이 다른 기존의 연구에서 제시한 것들보다 매우 우수함을 계산결과를 통하여 입증한다.
둘째, 앞서 제시한 산출율의 상한을 구하는 방법을 확장하여, 다수 서비스제공자를 갖는 시스템 및 폐쇄대기행렬망 등 좀더 일반적인 망구조에 대하여도 적용할 수 있음을 보여준다. 또한 대기행렬망에서의 쌍대이론의 결과를 이용하여 기존의 방법들을 개선시킬 수 있음을 보여준다.
셋째, 대기행렬망의 설계시 발생하는 최적자원할당문제를 해결할 수 있는 가능성을 제시한다. 각 시스템 및 서비스제공자의 순서 결정 문제, 서비스 능력의 할당 문제, 여분의 서비스제공자의 배분 문제, 용량의 배분 문제 등의 설계문제를 다룬다. 설계된 대기행렬망의 성능기준으로 앞서 구한 산출율의 상한을 이용함으로써도 자원배분의 효율성을 극대화할 수 있음을 계산결과에서 발견할 수 있다.