In this dissertation, we consider a discrete-time single-server queueing system having finite buffer capacity and a Bernoulli arrival process. The system has a finite number M of waiting places and a batch service random capacity Y. A service period is initialized when a service-starting threshold 'α' of waiting customers is reached. The system is denoted accordingly by $Geo/G^{\alpha,Y}/1/M$. This queueing system is motivated by manufacturing environments with batch service workstations, e.g., in machines for computer components and chip productions. We first derive departure-epoch probabilities using the embedded Markov chain technique. Next, we establish two relationships for the steady-state probabilities of the queue lengths at two epochs: departure and random.
These relationships for the steady-state probabilities at two different epochs can be implemented for numerical computations and useful performance measures such as the loss probability can be obtained. As this queueing system can be potentially useful in various other field such as production, transportation, traffic processes and various related systems, the results in this thesis would be useful not only to queueing researchers but also to practitioners who wish to evaluate the performance of their real systems. Further, many of the analytical and computational results of batch service queueing systems can now be recast in this framework. Moreover, the approach used in this thesis seems to be applicable to a much wider range of queueing systems with more general batch arrival and batch service.
This dissertation also presents an exact analysis of the steady-state queue-length distribution of the Geo/G/1 queue with disasters which remove all workloads from the system whenever they occur. We first present the steady-state queue-length distribution of the Geo/G/1 queue with disasters. Then, by using this result, we analyze the Geo/G/1 queue with multiple working vacations in which the server works at a different rate rather than completely stops during the vacation period. For such a queue, we present the steady-state queue-length distribution of the Geo/G/1 queue with multiple working vacations.
1. 연구 배경
대기행렬시스템이란 고객들이 도착하여 기다렸다가 서비스를 받고 떠나는 시스템을 말한다. 이러한 대기행렬시스템을 분석하는 이론이 “대기행렬이론” 이며 이는 시스템의 분석 및 설계를 위한 중요한 수학적 도구로 최근 생산, 통신 및 각종 서비스 시스템 등을 대상으로 광범위하게 활용되고 있다. 대기행렬시스템은 크게 “연속시간 대기행렬(Continuous-time queueing system)”과 “이산시간 대기행렬시스템(Discrete-time queueing system”의 두 범주로 분류할 수 있다. 기본적으로 연속시간 대기행렬시스템에서는 고객의 도착과 이탈이 시간 축 상의 임의의 시점에서 발생한다고 가정하는데 반해, 이산시간 대기행렬시스템에서는 시간 축을 슬롯(slot)이라 불리는 기본단위의 등 간격으로 나누고, 고객의 도착과 이탈이 항상 슬롯경계(slot boundary)에서 발생한다고 가정한다. 최근 대기행렬시스템분야에서는 멀티미디어 서비스를 제공하는 통신시스템에서의 광범위한 응용가능성으로 인해 이산시간 대기행렬시스템에 대한 연구가 증대되고 있다.
1.1. 집단서비스 대기행렬시스템 (Batch Service Queueing Systems)
일반적으로, 대기행렬시스템을 효율적으로 제어하기 위해서 시스템의 운용상황에 여러 제어정책(control policy)을 반영하게 된다. 집단서비스(batch service) 정책은 생산, 수송, 트래픽 등의 관련 시스템에 적용되는 대표적 제어정책의 예로서, 한 서비스가 끝났을 때, 서버는 여러 명의 고객을 한꺼번에 불러들여 서비스할 수 있다. 집단서비스 정책을 갖는 시스템들 중에서도 다양한 세부정책을 갖는 시스템들이 존재한다. 그 중에서 대표적인 세부정책은 다음과 같다. 첫째, 한 서비스가 끝났을 때 서버는 최대 B명까지 불러들여 서비스할 수 있다. 만약 B명 미만의 고객이 있으면 고객 전부를 불러들여 서비스하기 시작한다(만약 서비스 도중 나중에 도착하는 고객들은 서비스 진행도중에라도 여분의 자리를 채울 수 있다). 둘째, 여분의 자리가 있더라도 나중에 도착하는 고객들은 진행중인 서비스에 가담을 할 수 없는 경우가 있는데, 이때는 대기고객수가 일정한 수 a(≤B)가 되어야만 서비스를 시작한다. 셋째, 반드시 B명씩만 서비스를 하는 고정수 서비스시스템(fixed service-size system)이 있는데 이는 기다리는 고객수가 B미만이면 B가 될 때까지 기다렸다가 서비스를 시작하는 등 다양한 형태의 시스템들이 존재한다.
1.2. Disaster 대기행렬시스템 (Queueing Systems with Disasters)
대기행렬시스템에서는 시스템에 입장한 고객은 반드시 서비스를 받고 시스템을 떠나며 서버는 고장 나지 않는다고 가정한다. 그러나 현실적으로 그렇지 않은 경우가 많다. 예를 들어, 인출을 위해 은행에서 대기중인 고객에게 다음과 같은 상황이 발생할 수 있다. 중대한 전산시스템의 마비로 모든 인출 업무가 중단되고 고객들은 인출을 포기한 채 은행을 떠날 수 있다. 이때는 치명적인 시스템 고장으로 인해 고객들도 모두 시스템을 떠나는 경우이다. 갑작스러운 외부환경에 따라 통신망 전체 또는 일부의 서비스가 불가능하고 취소되는 경우가 이에 해당된다. 이 경우 망을 복구할 때까지 그 망을 이용하는 서비스가 모두 취소된다. 그리고 컴퓨터 시스템에서 바이러스의 발생으로 현재 작업과 대기중인 작업을 동시에 취소하는 경우나 갑작스런 또는 인위적인 재부팅 등의 결과로 모든 작업이 취소가 되는 경우가 발생하게 된다. 대기행렬시스템에서는 이와 같은 상황을 “Disaster 대기행렬시스템”으로 분석한다.
1.3. Working Vacation 대기행렬시스템 (Working Vacation Queueing Systems)
여러 정해진 제어정책을 따라서 서비스를 제공하지 않고 반복적으로 휴가를 떠나는 대기행렬시스템을 “복수휴가형 대기행렬시스템(multiple vacation queueing systems)”이라고 한다. 즉, 휴가에서 돌아 왔을 때 한 명 이상의 고객이 있으면 서비스를 시작하고 고객이 없으면 즉시 휴가를 또 떠나는 시스템을 말한다. 그러나 휴가중일 때는 서비스를 제공하지 않는 기존의 휴가형 대기행렬시스템과는 달리 휴가중이더라도 서비스를 제공하는 시스템을 “Working vacation 대기행렬시스템”이라고 한다. 이 시스템은 서비스를 제공할 고객이 없어서 휴가를 떠난 동안에 고객이 한 명 이상 도착하면 휴가가 끝날 때까지 서비스를 제공하지 않는 것이 아니라 휴가중에 도착한 고객이라도 기존의 서비스율보다 낮은 서비스율로 서비스를 제공하는 시스템이다.
2. 연구 목적 및 의의
본 연구는 최근 들어 컴퓨터 시스템 또는 통신 시스템 등을 분석하는데 있어서 많은 응용성을 갖고 있으며, 현재 활발히 연구가 진행중인 이산시간 대기행렬시스템 중에서 집단서비스 정책을 갖는 $Geo/G^{\alpha,Y}/1/M$이산시간 대기행렬시스템(M개의 유한용량 대기장소), Disaster가 발생하는 Geo/G/1/M 이산시간 대기행렬시스템과 Working Vacation 정책을 갖는 Geo/G/1/M이산시간 대기행렬시스템을 분석한다. 특히, $Geo/G^{\alpha,Y}/1/M$ 대기행렬시스템은 기존의 집단서비스 정책을 갖는 대기행렬시스템을 통합하는 가장 일반적인 형태로 표현되는 시스템이므로 본 연구에서 얻어진 결과인 고객수 분포뿐만 아니라 주요 성능척도인 손실 확률(loss probability)을 바탕으로 다양한 집단서비스를 갖는 시스템 분석에 효과적으로 이용될 수 있을 것이며 Disaster가 발생하는 대기행렬시스템과 Working vacation 정책을 갖는 대기행렬시스템에 대한 분석 결과는 서버시스템으로 운용되고 있는 모든 메인 컴퓨터시스템과 그외 다양한 통신 서비스를 제공하는 시스템 등을 분석하는데 이론적/실용적 토대로써 많은 활용이 기대된다.
2장에서는 집단서비스 정책을 갖는 이산시간 대기행렬시스템의 임의시점 고객수 분포를 구하는데 있어서 우선 내재점 마코브 체인(embedded Markov chain)을 이용하여 이탈시점(departure-epoch)에서의 시스템내의 고객수 분포의 확률을 구하였다. 이탈시점에서의 시스템내의 고객수 분포를 가지고 준마코브과정(semi-Markov process)을 이용하여 임의시점(random-epoch)에서의 시스템내의 고객수 분포를 명시적으로 유도하였다. 그리고 추가적으로 임의시점에서의 시스템내의 고객수 분포의 결과를 이용하여 서비스시간이 각각 Deterministic, Negative binomial, Geometric 분포를 따르는 시스템의 손실 확률을 비교/제시하였다.
3장에서는 부가변수법(supplementary variable technique)을 이용하여 시스템 방정식을 구하고 시스템 방정식에 포함된 미지수는 사이클 분석(cycle analysis)을 이용하여 Disaster가 발생하는 이산시간 대기행렬시스템의 임의시점에서의 시스템내의 고객수 분포를 제시하였다.
4장에서는 Working vacation 정책을 갖는 이산시간 대기행렬시스템의 고객수 분포를 구하는데 있어서 이 시스템의 사이클을 기존의 서비스율을 제공하는 기간과 낮은 서비스율을 제공하는 휴가기간으로 나누어서 각각의 고객수 분포를 구한 뒤 전체 시스템의 고객수 분포를 제시하였다.
