In queueing systems, customers may leave the system without service or the server may be subject to deterioration and failures. This dissertation considers the concept of "negative customer", "disaster", and "random shock" to model queues with reneging customers and server failures.
First, we extend the queueing theory on negative customers to GI/M/1 queues. When a negative customer arrives at the system, it immediately removes a customer. A negative customer is a kind of work cancellation. We consider FIFO and preemptive LIFO service discipline. The system size distribution and the sojourn time distribution are derived.
Second, we analyze M/G/1 queues with disasters. In these systems, an external arrival of a disaster removes all workload in the system. We can think of the disaster as a machine breakdown that causes all the jobs in the system to be lost. We present the system size distribution and the sojourn time distribution.
Finally, we propose a random review replacement policy of single server queues with random shocks that cause deterioration and breakdowns of a server. Shocks deteriorate the effectiveness of a server. A repairman monitors the system randomly and replaces the server instantaneously if the cumulative magnitude of shocks exceeds a maintenance level. We analyze the system size distribution and the sojourn time distribution. An efficient algorithm for computing the sojourn time distribution function is derived. A cost analysis is performed to investigate the optimal maintenance level.
일반적으로, 대기행렬 모형에서는 시스템에 입장한 고객은 반드시 서비스를 받고 시스템을 떠나며 서버는 고장나지 않는다고 가정한다. 그러나 현실적으로 그렇지 않은 경우가 많다. 예를 들어, 인출을 위해 은행에서 대기중인 고객에게 다음과 같은 상황이 발생할 수 있다.
(1) 급한 일이 생겨 인출을 포기하고 은행을 떠난다.
(2) 은행 업무가 너무 지체돼 인출을 포기하고 은행을 떠난다.
(3) 중대한 전산시스템의 마비로 모든 인출 업무가 중단된다. 고객들은 인출을 포기하고 은행을 떠난다.
(4) 사소한 전산시스템의 마비로 (또는 직원이 잠시 자리를 비워서) 인출 업무가 잠시 중단된다. 고객은 은행에서 기다린다.
(1)은 외적 요인에 의해 작업이 취소되는 경우이다. 예를 들어, 생산 시스템에서는 생산계획이 변경되면 진행중이거나 대기중인 작업이 취소된다. 최근 대기모형에서는 이와 같은 상황을 "Negative customer" 모형으로 분석한다. 이 모형에서는 작업취소 신호가 발생하면 대기중이거나 서비스 받는 고객중 한 명 또는 일부가 시스템을 이탈한다.
(2)는 내적 요인에 의해 작업이 취소되는 경우이다. 가령, 음성과 같이 실시간 전송을 요하는 통신망에서는, 제한시간 내에 전달되지 않은 음성 패킷은 파기된다. 대기모형에서는 이와 같은 상황을 "Impatient customer" 모형으로 분석한다. 대기시간이 일정 제한시간 보다 크면 고객은 서비스를 포기하고 시스템을 떠난다.
(3)은 치명적인 시스템 고장으로 인해 고객들도 모두 시스템을 떠나는 경우이다. 갑작스러운 외부환경에 따라 통신망 전체 또는 일부의 서비스가 불가능하고 취소되는 경우가 이에 해당한다. 이 경우 망을 복구할 때까지 그 망을 이용하는 서비스가 모두 취소된다. 대기행렬 모형에서는 이와 같은 상황을 "Disaster" 모형으로 분석한다. 외부 신호에 의해 고객의 이탈이 발생하기 때문에 Disaster는 Negative customer의 일종으로 분류할 수도 있다.
(4)는 생산/제조 시스템에서 자주 발생한다. 생산라인에서 장비가 고장나면 수리기간 동안 생산라인은 멈추고 제품들은 그동안 생산라인에 남아있게 된다. 대기모형에서는 이와 같은 상황을 "Server failure" 모형으로 분석한다. (3)과 달리 고객들은 시스템에 머물러 있는다.
(1), (2), 그리고 (3)과 같이 고객이 서비스를 받지 못하고 시스템을 이탈하는 상황을 "Reneging"이라 부른다. 본 논문에서는 위와 같이 작업이 취소되거나 서버가 고장하는 시스템을 수리적으로 모형화하고 분석하였다. 구체적인 내용은 다음과 같다.
2장에서는 negative customer와 disaster가 동시에 존재하는 GI/M/1 대기행렬 모형을 다루었다. Negative customer를 고려한 대기모형은 그간 M/M/1 모형과 M/G/1 모형에 대해 부분적으로만 연구되었고 GI/M/1 모형은 아직 연구되지 않았다. 본 연구에서는 가장 중요한 시스템 성능 척도인 고객수 분포와 체류시간 분포를 분석하였다. 각종 평균치와 고객들이 서비스를 받지 못하고 시스템을 떠날 확률(blocking probability)을 유도하였다. 또한, 축출형 후입선출방식(preemptive LIFO) 서비스 정책도 다루었다.
3장과 4장에서는 일반 수리시간을 갖는 M/G/1 Disaster 모형을 분석하였다. 3장에서는 수리중 고객이 시스템에 입장하지 못한다고 가정하였다. 반면, 4장에서는 수리중 고객이 시스템에 입장할 수 있다고 가정하였다. 고객수 분포와 체류시간의 분포, 고객들이 서비스를 받지 못하고 시스템을 떠날 확률 및 시스템 가용성(availability)을 분석하였다. 아울러, 후입선출방식 (LIFO) 서비스 정책을 다루었다.
생산/제조 시스템에서 기기들은 성능이 떨어지다가 고장난다. 기기 고장은 생산계획의 차질 및 품질 저하의 원인이 되기 때문에 시스템의 유지 및 관리가 중요하다. 서버가 고장나는 대기모형은 그간 상당히 연구되어 왔으나, 기존 연구의 주된 관심사는 고객수 분포와 체류시간 같은 성능치들이었고 대기모형의 시스템의 유지/보수에 대한 연구는 그리 많지 않다. 한편, "Shock" 모형은, 고장이 발생하는 시스템의 수명을 연구하기 위한 모형으로 그간 많이 연구되었다. Shock 모형에서는 시스템에 발생한 쇽의 누적량이 일정치 이상이면 시스템이 고장난 것으로 간주한다.
5장에서는 충격(shock)에 의해 서버의 성능이 저하되다가 고장나는 대기행렬 모형을 제안하고 분석하였다. 본 연구는 대기행렬 모형과 shock 모형을 통합한 모형이다. 즉, 본 연구에서는 대기행렬 모형의 서버를 shock 모형의 시스템으로 간주하였다. 5장에서는 행렬기하 (matrix-geometric) 방법을 이용하여 고객수와 체류시간을 분석하였다. 아울러, 비용분석을 통해 시스템 비용을 최소화하는 사전예방 정책에 대해서도 다루었다.
