Finite queueing network is a useful tool in evaluating the performance of real-life systems which have finite capacity resources. The complexity associated with the blocking phenomena inherent to such systems with finite capacities, in general, makes the analysis difficult. The approximation methods, which are the only means available for large systems, are generally based on decomposition. In most of the decomposition approaches, each subsystem is a single queueing system. However, the configurational complexity of the system and/or the dependencies between subsystems seriously degrades the accuracy and the efficiency of the decomposition.
This thesis presents an efficient method which yields the steady-state probabilities for the general two-node tandem queueing network and some of its variants which have the similar transition structures. Also, we propose a decomposition scheme for the finite-buffered fork/join queueing network, in which the simple fork or join networks can be the subsystems. By using the equivalence relations, such subsystems are evaluated by the algorithm for the two-node tandem queueing networks.
First, focusing on repetitive-service(RS) blocking, we propose an aggregation scheme for the two-node tandem queueing network. Together with the recursive relations between the states, derived then is a reduced system of linear equations. Also, we propose an equivalence relation between the cyclic network and the tandem network with population size constraints, which makes it possible that three-node cyclic networks can be analyzed using the same line of approach.
Second, we show that the proposed principle, the aggregation and the recursion, can be applied to some tandem networks with more general assumptions such as the ones with any commonly used blocking mechanism, with feedback, with multiple servers, and with more than two nodes. Also, we deal with the finite-buffered cutoff priority queue with reneging as an illustration that any queueing system, provided it has two-dimensional state space and the same transition patterns except for some boundary states, can be analyzed by the proposed approach.
Finally, for the approximate analysis of the finite fork/join queueing network (FJQN), we propose a decomposition method which can sustain the fork/join primitives within subsystems. The decomposition scheme is first developed for the case with two siblings and is extended to the case with more than two siblings. Subsystems of two-sibling FJQN can be the simple fork or join network with three servers. Using the structurally equivalent relations, subsystems are evaluated by the algorithm for the two-node tandem network. Computational tests show that the proposed decomposition scheme gives fairly accurate results on the throughputs and the average buffer levels.
유한 용량의 대기행렬(queueing networks with finite buffers)은 제한된 자원을 가진 실제 시스템의 성능을 평가하는 유용한 기법이다. 그러나, 유한한 용량이 유발하는 블로킹 현상(blocking phenomena)이 시스템의 분석을 어렵게 하기 때문에 여러가지의 근사 해법이 제시되어 왔으며, 분할 기법(decomposition)은 그 중에서도 많이 사용되는 방법이다. 대개의 분할 기법은 시스템을 단일 대기행렬(single queueing system)로 분할하게 되는데, 이 방법은 분석이 용이하지만, 시스템의 규모가 커지고 대기행렬들 간의 관계가 복잡해질수록 결과의 정확도와 분석의 효율이 떨어지게 된다.
본 연구는 유한 용량의 대기행렬의 분석을 다루고 있으며, 안정 상태의 확률 분포(steady-state probabilities)를 구하는 방법을 중심으로 하고 있다. 시스템의 상태가 2차원으로 표시될 수 있는 대기행렬에 대한 정확한 해(exact solution)를 구하는 방법과, 보다 복잡한 시스템에 대한 분할 기법에 있어서 이 방법을 소규모 시스템(subsystem)의 해법으로 이용하는 방법을 소개한다.
먼저, 반복 서비스 블로킹(repetitive-service blocking)하에서 2개의 노드(node)로 구성된 직렬망(tandem network)에 대하여 종합화 (aggregation)와 순환적 관계(recursive relations)를 이용하여 안정 상태의 확률 분포를 구할 수 있는 선형 방정식들을 유도한다. 이때, 방정식의 수는 균형 방정식(balance equations)에 비하여 크게 줄어들게 된다. 또한, 폐쇄형 회전망(closed cyclic network)과 고객의 수(customer)가 제한되는 개방형 직렬망(open tandem network)이 동일(equivalency)하다는 것을 보임으로써, 폐쇄형 회전망을 같은 방법으로 분석할 수 있음을 보였다.
다음으로, 다양한 가정하에서 직렬망에 대한 분석 역시 종합화와 순환적 관계라는 접근 방법(approach)으로 분석될 수 있음을 보였다. 다양한 가정들이란 여러가지 종류의 블로킹, 피이드백, 다수의 서버 (server) 등을 말한다. 또한 시스템의 상태가 2차원으로 표시될 수 있고 상태간의 전이율(transition)이 일정한 규칙을 갖는 여러가지 대기행렬에 이러한 접근 방법이 적용될 수 있음을 보이기 위하여, 우선순위에 의한 차단을 고려한 대기행렬(cutoff priority queue)을 분석하였다.
마지막으로, 분기/접합 형태를 지닌 대기행렬망(fork/join queueing network)을 분할 기법(decomposition)을 이용하여 분석하였다. 본 연구에서는 대부분의 분할 기법들이 단일 대기 행렬로 분할하는 것과는 달리, 하나의 소규모 시스템(subsystem)이 분기 또는 접합 현상을 포함하도록 고안되었다. 이때의 소규모 시스템들은 단순 접합(또는 분기)구조의 망이 되는데, 이들 시스템이 2개의 노드로 구성된 직렬망과 동일하다는 성질을 이용하여 앞에서 제시한 해법이 소규모 시스템을 평가하는데 사용되었다. 이러한 분할 기법은 분기 및 접합 현상을 소규모 시스템 자체내에 포함하게 되어, 여러번의 계산을 수행한 결과 상당히 정확하게 산출률(throughput)과 대기 장소의 평균 고객수를 추정함을 알 수 있었다.
