具隨機假期策略之M[x]/G/1排隊系統分析

Analysis of the M[x]/G/1 Queueing System with Randomized Vacation Policy

黃凱斌(Huang, Kai Bin)

指導教授 ： 彭文理

國立交通大學/管理學院/工業工程與管理系所/博士(2009年)

https://doi.org/10.6842/NCTU.2009.01171

摘要

本論文研究探討具隨機假期策略之M[x]/G/1排隊系統。當系統中沒有顧客時，服務者會立刻休假。而當服務者休假回來且發現系統中至少有一位顧客在等待服務時，服務者會馬上對顧客進行服務。另外，當服務者休假回來且發現系統中沒有顧客正在等候服務時，則服務者會有p的機率閒置在系統中等候顧客進入系統以進行服務，但會有（1-p）的機率繼續下一個假期。這種模式(pattern)會一直持續到服務者休假次數達到J次為止。如果服務者結束第J個假期回到系統中且發現系統中沒有顧客在等候服務，此時服務者會永遠閒置在系統中等候顧客進入系統以進行服務。在此論文中，我們將考慮以下三種排隊系統：(1) 服務者為可靠的，(2) 服務者會故障且可立即修理及 (3) 服務者會故障且可能會延遲修理等三種不同的排隊系統。對於論文中所有考慮的系統，我們利用輔助變數技巧推導出系統中顧客數的機率分配及其它重要的系統特徵，例如忙碌期間開始時的系統中顧客數分配、在離開時點時的等候區顧客數分配以及閒置週期及忙碌週期之分配等。另外，對於服務者會故障的情形我們也探討其可靠度分析，並提出主要的可靠度指標。利用更新報酬定理，我們提出一個成本模型以決定最佳化隨機假期策略。而基於所提出的成本模型，我們也提出一個啟發式方法用來搜尋使得成本為最小時的p及J。最後並以數值分析來說明此論文所提出的最佳化隨機假期策略。此論文推廣了現存的假期策略排隊模型，並且對真實世界中發生的問題提供了有用的績效評估。

關鍵字

批次到達排隊系統 ； 延遲修理 ； 可靠度 ； 故障 ； 輔助變數技巧 ； 假期策略

並列摘要

This dissertation examines an M[x]/G/1 queueing system with a randomized vacation policy and at most J vacations. Whenever the system is empty, the server immediately takes a vacation. If there is at least one customer found waiting in the queue upon returning from a vacation, the server will be immediately activated for service. Otherwise, if no customers are waiting for service at the end of a vacation, the server either remains idle with probability p or leaves for another vacation with probability 1-p. This pattern continues until the number of vacations taken reaches J. If the system is empty by the end of the Jth vacation, the server becomes idle in the system until at least one customer waiting in the queue. In this dissertation, we investigate the following three queueing systems: Reliable server queueing system, un-reliable server queueing system and un-reliable server with a delayed repair queueing system. For the three systems considered in our dissertation, using the supplementary technique, we develop the system size distribution as well as other important system characteristics, such as the system size distribution at busy period initiation epoch, the queue size distribution at a departure epoch, and the distributions of busy period and idle period, etc. Further, for the un-reliable server we also develop main reliability indices of the presented model. Using the renewal reward theorem, a cost model is constructed to determine the optimal randomized vacation policy. Based on the cost model, a heuristic approach is provided to search the joint optimum values of p and J. Some numerical results are presented for illustrative purpose. Our study presents an extension of the existing vacation queueing model and the analysis of the proposed model will provide a useful performance evaluation tool for more general situations arising in real word.

並列關鍵字

Batch arrival queue ； Delayed repair ； Reliability ； Server Breakdown ； Supplementary variable technique ； Vacation polic

參考文獻

1. Avi-ltzhak, B. and Naor, P. (1963) ”Some queueing problems with the service station

subject to breakdowns,” Operations Research 11(3), 303-320.

2. Baba, Y. (1986) ”On the M/G/1 queue with vacation time,” Operations Research Letters

4. Burke, P. J. (1975) ”Delay in single server queues with batch input,” Operations Research

5. Choudhury, G. (2002) ”A batch arrival queue with a vacation time under single vacation