M/G/1/K與G/M/1/K排隊含啟動時間的F方策與N方策之相互關係

Abstract

此篇論文是在研究F方策M/G/1/K和G/M/1/K排隊含起動時間的問題，進而深入探討F方策和N方策的相互關係。在排隊問題中，F方策主要是研究控制到達的問題。N方策排隊問題主要是研究控制服務的問題。首先，我們探討對於在F方策M/G/1/K和G/M/1/K排隊含起動時間的問題。而F方策的定義如下：當顧客數目到達系統可承載數(例如系統容量)，系統不再允許任何到達顧客進入，直到有一定數目(足夠)的顧客已被服務，也就是顧客數目會降到一個門檻值F (0<=F<K-1)。同時，啟動系統開始讓顧客進入系統，其啟動時間的分配為指數分配，參數為 。因此，系統會正常運作直到系統裡的顧客數目到達系統可承載的數目，所有的程序會再重新依序發生。我們分別針對在F方策M/G/1/K和G/M/1/K排隊中提出遞迴的方法與輔助變數技巧來推導。其方式如下，使用輔助變數代替剩餘服務時間(到達時間)再利用遞迴方法來計算在穩態下的機率。為了分析說明遞迴方法，此篇論文提出三種不同服務時間(到達時間)分配來解釋在F方策M/G/1/K和G/M/1/K排隊系統含指數分配的起動時間，其服務時間(到達時間)分配包括指數分配、3階段Erlang和deterministic分配等。同時，針對最佳化的問題，建立其成本模型來決定最佳F值，使得成本最小。我們也使用Maple電腦程式來計算出最佳F值與系統參數的關係，並作敏感度的分析。為了進一步探討F方策和N方策的關係，我們同樣使用遞迴方法和輔助變數技巧來求取含啟動時間之N方策M/G/1/K 排隊系統中穩態機率的演算法。而N方策的定義如下：當顧客數目增加到一個門檻值N (N>=1)時，啟動系統開始服務，其啟動時間的分配為指數分配，參數為 。且直到系統內沒有顧客後關閉服務。透過一系列的演算法的比對與計算，驗證出F方策和N方策之間的互補關係：可由F(或N)方策排隊系統所得到的演算法去計算另一個方策的排隊問題的解。最後，我們提供兩個範例，分別為3階段Erlang與指數分配來作說明F方策和N方策之間的互補關係。

This dissertation deals with the interrelationship between F policy and N policy. The F policy queuing problem investigates the most common issue of controlling arrival to a queuing system. The N policy queuing problem investigates the most common issue of controlling service. The optimal control arrival in M/G/1/K and G/M/1/K queues operating under the F policy and startup time is investigated in this dissertation. The definition of F policy is described as following: When the number of customers in the system reaches its capacity K (i.e. the system becomes full), no further arriving customers are allowed to enter the system until there are enough customers who have been served in the system. Consequently, the number of customers in the system decreases to a threshold value F (0<=F<K-1). At that time, the server requires to take an exponential startup time with parameter β to start allowing customers in the system. Thus, the system operates normally until the number of customers in the system reaches its capacity at which time the above process is repeated all over again. A recursive method, using the supplementary variable technique and treating the supplementary variable as the remaining service (or inter-arrival) time, is provided to develop the steady-state probability distributions of the number of customers in two finite queues. To illustrate analytically the two recursive methods, examples of different service (or interarrival) time distributions, such as exponential, 3-stage Erlang and deterministic distributions, in the F policy M/G/1/K queuing system and in the F policy G/M/1/K queuing system with exponential startup time distribution is present. In both queueing systems, a cost model is established to determine the optimal management F policy at minimum cost. An efficient Maple computer program is used to determine the optimal operating F policy and some system performance measures. Sensitivity analysis is also studied. To find the interrelationship between F policy and N policy, we have solved the solution algorithm of the N policy M/G/1/K queue with startup time. A recursive method and supplementary variable technique to obtain the solution algorithm is provided. The definition of N policy is described as following: The server needs a startup time when the number of customers in the system reaches the threshold N(N>=1) for the first time until there are no customers present in the system. At that time, the server needs to take an exponential startup time with parameter γ to start servicing customers in the system. Through a series of the algorithm, the complementary interrelationship between the F policy and N policy queues is obtained. Therefore, the problem of F policy (N policy) queuing system with startup time gives the solution algorithm to the other problem. The two simple examples of 3-stage Erlang and exponential distribution to illustrate the interrelationship are provided.