In this dissertation, general input queues with single working vacation are analysed. General queues encompass the continuous time GI/M/1 queue and the discrete time GI/Geo/1 queue. The working vacation is a newly devised vacation scheme. This scheme is different from the classical vacation schemes in that a server serves customers even when the server is on a vacation, but service rate is assumed to be different (in most cases, lower) from the nominal one.
Using embedded Markov chain, the queue length distribution at arrival epochs of the discrete time GI/Geo/1/SWV queue is obtained. Then using this queue length distribution, the sojourn time in the system is presented. Lastly, using semi-Markov process, the queue-length distribution at arbitrary epochs is derived. Then a similar analysis is applied to the continuous time GI/M/1/SWV queue, same performance indices are presented. After all these steps, the GI/Geo/1/SWV queue and the GI/M/1/SWV queue is contrasted by taking the limit that makes a slot size of the GI/Geo/1/SWV queue goes to zero. We can obtain the result of GI/M/1/SWV queue from the GI/Geo/1/SWV queue.
We also present analyses of a busy period of three general input queues with vacations: the n-policy GI/M/c queue, the GI/M/1/MWV queue, and the GI/Geo/1/MWV queue. A busy period is defined as time duration from when the system size becomes one to the instant when the system size becomes zero. For the n-policy GI/M/c queue, the length of a busy period, the number of customers served during the busy period, and the consecutive idle period are given in terms of the joint transform. For the queue with MWV, the length of a period when a service rate is normal, the length of a period with a lower service rate, the number of customers served in each period, and the length of consecutive idle period are given in terms of the joint transform. By utilizing this joint transform, we can derive various results related to moments, i.e., higher moments and correlated moments. Using the result of the GI/M/1/MWV queue, we represent stochastic decomposition of the queue length.
1. 연구 배경
(a)휴가형 대기행렬과 워킹형 휴가 (queues with vacations and working vacations)
생산, 통신 및 각종 서비스 시스템을 효율적으로 제어하기 위해서는 시스템의 동작 특성을 반영한 운용 정책 (control policy)를 고안, 적용하게 된다. 대표적인 제어 정책의 예로 휴가 정책, 그 중에서 $n$ 정책을 들 수 있다. 시스템 내 고객수가 $n$명이 (단, $n$ 은 1이상의 정수) 되어야 비로소 서비스를 시작하는 정책이다. 이외에도 많은 휴가정책들이 존재하고 이와 같이 휴가정책을 갖는 대기행렬을 ``휴가형 대기행렬''이라고 부른다. 휴가형 대기행렬은 상당히 오래 전에 제안되었으며 따라서 광범위한 연구들이 이루어져왔다.
워킹형 휴가는 2000년대 처음 제안된 새로운 개념이다. 이전의 휴가에서는 휴가 기간동안에는 서비스를 하지 않는데 반해 워킹형 휴가에서는 휴가기간에는 휴가 중이 아닐 때와 다른 서비스율로, 통상 낮은 서비스율을 가정, 서비스를 제공하는 개념이다. 이 새로운 휴가 개념은 제안된 이래 이론적으로도 많은 연구가 발표되고 있다.
(b) 이산시간 대기행렬 (discrete time queues)
연속시간 대기행렬에서는 고객들의 도착과 이탈이 임의의 곳에서 가능하다. 그러나 이산시간 대기행렬에서는 시간축이 등간격의 슬롯이라는 단위로 구분되고, 고객들의 도착은 이 슬롯의 경계에서만 발생한다고 가정한다. 한 슬롯 내에서 도착과 이탈이 동시에 발생한다면 순서를 어떻게 정하는지에 따라 이산시간 대기행렬은 크게 두 가지 모형으로 다시 구분된다. 이산시간 대기행렬은 디지털 통신시스템 등을 묘사하기에 적합한 것으로 알려져 있다. 이산시간 대기행렬에 대한 연구는 최근 활발히 진행되고 있다. 그러나 연속시간 가정에 비해 상대적으로 연구결과가 적은 편이고 연속시간 가정에 익숙한 연구자들이 아직 분석에서 혼란을 겪는 것을 볼 수 있다.
(c)일반도착 대기행렬 (general input queues)
대기행렬 이론에서는 크게 시스템에 들어오는 도착과정과 서버의 서비스 과정을 정의하는 것으로 시스템을 묘사할 수 있다. 기존에는 도착과정이 포아송 과정 (Poisson process, 또는 도착간격이 지수 (exponential)분포)을 따르고 서비스 시간은 일반 (general)분포를 따른다는 대기행렬들이 주로 분석되었다. 따라서 도착과정은 일반 분포를 따르고 서비스 시간은 지수분포를 따른다고 가정하는 GI/M/1 대기행렬 모형에 대해서는 연구결과가 상대적으로 적은 편이고 연구의 여지가 많이 남아 있다. 특히, 위에서 소개된 이산시간 가정을 갖는 휴가형 이산시간 대기행렬에 대한 연구는 찾아보기 매우 힘들다.
(d)일반도착 대기행렬의 바쁜기간 (busy period of general input queues)
바쁜 기간은 흔히 서버가 작동을 시작하는 순간부터 (바빠지는 순간) 처음으로 유휴하게 될 때까지로 정의된다. 보통 바쁜 기간을 분석하면 바쁜 기간의 길이와 그동안 서비스 받는 고객수 (또는 생산되는 제품수)를 얻을 수 있다. 생필품 등을 대량으로 생산하여 재고로 쌓아두는 생산 시스템에서는 한 런 (run)의 생산이 언제쯤 끝날 지, 또 그동안 몇 명이 서비스 받는지를 파악하는 것은 매우 중요하다고 할 수 있다. 이런 것들을 파악하기 위해서는 바쁜 기간의 분석이 필수적이다. 그러나 일반도착을 갖는 대기행렬의 바쁜 기간 분석은 찾아 보기 매우 힘들다고 할 수 있으며 오래된 책에서 찾더라도 분석 방법이 상당히 수학적이어서 이해하기에 쉽지 않다. 본 연구에서는 보다 직관적인 방법으로 워킹형 휴가를 갖는 일반도착 대기행렬의 바쁜기간을 분석한다.
2. 연구의 목적과 의의
(a)단수의 워킹형 휴가를 갖는 GI/Geo/1 대기행렬과 GI/M/1 대기행렬의 분석 및 비교
먼저 단수의 워킹형 휴가를 갖는 GI/Geo/1 대기행렬을 내재점 마코프 체인 방법으로 분석하여 도착시점의 고객수 분포, 그리고 대기시간을 얻는다. 도착시점의 고객수 분포 결과와 준 마코프 과정 (semi-Markov process)을 이용하면 임의시점 고객수 분포를 도출할 수 있다. 그리고 연속시간 단수 워킹휴가형 GI/M/1 대기행렬에 대해서도 비슷한 방법으로 세 가지 성능 척도를 얻는다. 여기서 이산시간 대기행렬의 슬롯의 크기를 무한소로 만드는 극한을 취하여 연속시간 대기행렬의 결과와 비교한다. 이는 연속시간 대기행렬, 이산시간 대기행렬을 따로따로 풀지 않고 이산시간 대기행렬 하나만 풀면 연속시간 대기행렬의 결과도 얻을 수 있음을 보이려는 시도이다. 이 부분에 대해서는 좀 더 수학적으로 엄밀하게 보이려는 노력이 더 필요하다. 수학적으로 일반적으로 성립한다는 것은 보이지 않았으나 기존 연구들에서는 이러한 시도를 찾아보기 쉽지 않다는 점에서 의의를 찾을 수 있다.
앞서 언급했듯, 일반도착을 갖는 이산시간 대기행렬에 대한 연구는 도착간격이 기하분포를 따르는 대기행렬에 비해 상대적으로 부족한 편이다. 이에 휴가 정책을 덧붙인 연구는 더욱더 찾아보기 힘들다. 또한 일반적으로, 한 번의 (단수) 휴가를 갖는 휴가정책은 복수의 휴가정책에 비해 분석이 어렵다고 알려져있다. 이들을 모두 종합해 볼 때 단수 휴가를 갖는 일반도착 이산시간 대기행렬 모형을 분석하는 것은 이론적인 큰 의미가 있다고 할 수 있다.
(b) 휴가형 일반도착 대기행렬들의 바쁜기간 분석
이 논문에서는 세 가지 휴가형 대기행렬 모형들의 바쁜 기간을 다룬다. 세 가지는, $n$- 정책을 갖는 GI/M/c 대기행렬, GI/M/1/MWV 대기행렬, 그리고 GI/Geo/1/MWV 대기행렬이다. 이들은 같은 분석방법을 사용하여 분석될 수 있다. 다만 식을 세울 때 가능한 경우들을 잘 따져야 한다. 먼저 $n$-정책을 갖는 GI/M/c 대기행렬을 분석하여 바쁜 기간의 길이, 그 동안 서비스 받고 이탈하는 고객수와 이어지는 유휴기간의 길이를 결합변환 (joint transform) 형태로 제시한다. GI/M/1/MWV과 GI/Geo/1/MWV의 바쁜기간 분석에서는 결과로 빠른 속도로 서비스하는 기간의 길이와 그 동안 서비스 받고 이탈하는 고객수, 느린 속도로 서비스하는 기간의 길이와 그 동안 서비스받고 이탈하는 고객수, 그리고 유휴기간의 길이를 라플라스 변환 (Laplace transform)과 확률 생성함수 (probability generating function)의 결합 변환 형태로 제시한다. 바쁜 기간을 분석하기 위해 먼저, 휴가 중이고 시스템 내 고객수가 $n$명이 되는 순간 시작하여 언젠가 시스템 내 고객수가 0명이 되는 바쁜 기간을 정의한다. 그리고 이후 다음 고객이 도착할 때까지의 간격, 즉 도착간격, 동안에 발생할 수 있는 사건들을 따져보고 이에 조건을 거는 것으로 (conditioning) 위 다섯가지의 결합변환을 표현할 수 있다. 이를 이용하여 휴가 중 일때 서버가 작동을 시작하는 순간부터 언젠가 처음으로 유휴하게 될 때 까지, 그 기간동안 위 다섯가지의 정보를 얻을 수 있다. 또한 GI/M/1/SWV의 경우, 대기행렬의 확률적 분해속성을 따져보았다. 이를 얻는데 GI/M/1/MWV 대기행렬의 바쁜기간 분석결과가 이용되었다. 일반도착 대기행렬의 경우 확률적 분해속성이 잘 알려져 있지 않은 편이다.
앞서 여러 번 언급되었듯, 일반도착을 갖는 대기행렬의 바쁜 기간 분석은 그 결과가 매우 드물다는 점에서 본 연구의 의의를 찾을 수 있다. 또한 본 연구의 결과는 결합 변환 형태로 제시되어 다양한 모멘트 결과들을 얻을 수 있다.
