帶有反饋和不耐煩的雙端排隊系統

單凈璇，朱翼雋，濮華盛

（江蘇大學理學院 數學系，江蘇 鎮江 212013）

帶有反饋和不耐煩的雙端排隊系統

單凈璇，朱翼雋，濮華盛

（江蘇大學理學院 數學系，江蘇 鎮江 212013）

文章以需求/供應系統為背景，研究了帶有反饋和不耐煩的雙端排隊模型。假定供應方d到達系統服從泊松分布，需求方到達系統的時間間隔服從一般分布，利用補充變量法構造馬爾可夫過程，通過狀態轉移分析列出微分方程，借助概率母函數求出該系統的一些性能指標。

雙端；補充變量法；概率母函數；L變換

0 引言

雙端排隊模型最早是由Kendall[1]提出的，他初步設想了乘客與出租車都以possion流到達車站時的問題，其中乘客與出租車數量均無限。之后被許多不同的作者研究過。Dobbi[2]在kendall基礎上引入了時間函數的概念，Jain[3]進一步討論了當出租車等待空間是有限（不多于n）的情形，而Kashyap[4-6]系統研究了出租車與乘客等待空間均有限的雙端排隊模型并討論了出租車分布是k階Erlang分布的特殊情形。近年來國際上B.W.Conolly[7]討論了雙端排隊在通訊網絡以及編程語言上的應用。國內尹小玲，蘇健[8]考慮了引入負顧客的等待空間有限的雙端排隊系統。

與此同時，雙端排隊模型在需求/供應系統中有著廣泛的應用背景，其中庫存生產模型可以理解為雙端排隊模型的擴展。庫存問題的研究最早可追溯到1915年Harris所首先建立的著名的經濟批量公式 (Economic Order Quantity，EOQ)。研究庫存系統需要解決的問題通常是，確定系統的最優控制變量，以使費用目標函數達到最小。Berman，Kaplan及shimask[9]研究了需求率是常數，訂貨瞬時到達的庫存系統。Berman和Kim研究了需求服從指數分布，所訂貨物的到達有一個延遲的庫存系統，He Q M[10]等人利用排隊論的矩陣幾何解的理論，給出了庫存系統中的每件產品的平均費用函數的2個算法，侯玉梅[11]等人在此基礎上進行了簡單生產-庫存系統的優化控制。

帶反饋的排隊系統與經典排隊系統不同，其服務機制有所變化，顧客到達系統后并不一定依次服務就離開系統，而是有可能經過多次，這個服務次數是由反饋機制所決定的[12-14]，其中主要的Bernoulli反饋已被廣泛應用于計算機分時操作和無線電通訊網絡系統中，通過對它一些指標的研究，可安排最合理的運行管理方案[15]。

在很多實際服務系統中會有不耐煩顧客出現，產生不耐煩顧客一般有兩種情況：一是顧客剛剛到達時，因其不能被馬上服務而立刻離開系統，稱之為阻滯；二是顧客到達并進行排隊，排隊一段時間以后失去耐心，未等到服務即離開系統，稱之為中途離開。

綜上所述，本文討論一個帶有反饋和不耐煩的雙端排隊系統，比如對于庫存系統這個由倉庫和顧客共同構成的雙端排隊系統中，到達的顧客隨時有可能會因為不耐煩而離開系統。同時，顧客方并不是依次進行服務后立刻離開系統，而是有可能需求得到滿足后發現貨物質量有問題需要調換等問題而要求再次服務，這就要由反饋機制決定。

1 模型的描述

由一個倉庫和顧客共同構成的雙端排隊系統中，需求與供應之間的關系體現在倉庫庫存的增加與減少。此時需求方相當于顧客，而供應方相對于需求方可以看做是提供服務的服務員，其服務率為供應方的到達率，服務規則是先到先服務。供應方（服務端）以參數為λ的泊松分布到達系統，需求方（顧客端）到達系統的時間間隔服從一般分布函數A(x)，對應密度函數為a(x)，L-S變換為A*(x)，一階矩、二階矩為v1.v2。μ(x)表示相應的風險率函數，即有，若顧客到達發現系統中沒有顧客則立刻接受服務，否則會有顧客因為等待不耐煩而離開（即中途離開情形）。離開前等待的時間η是一個隨機變量，我們假設它服從參數為b的負指數分布。服務完成后以概率1-q反饋到隊尾尋求再次服務或者以概率q離開。設庫存量的等待空間為M，即第M+1個顧客到達則自動離開系統，同理顧客數的等待空間為N。若倉庫中沒有儲備貨物而有顧客到達時,系統將該需求記錄為一個單位的缺貨。為了保證生產持續進行及減少缺貨事件的發生,倉庫要向供應系統訂貨,以補充生產消耗。

我們進一步記系統中顧客數與庫存數分別為U(t)和V(t)，則系統中的隊長為 N(t)=U(t)-V(t)=n(n=-M，-M+1，…，-1，0，1，2，…，N)，當 n>0 時，表示時刻 t系統中有 n 個顧客在等待服務，當n<0時，表示時刻t系統中的庫存量為|n|，n=0表示t時刻系統為空。顯然{N(t),t≥0}不是馬爾可夫過程，引入補充變量ξ(t)為時刻t與t前最后一個顧客到達時刻的時間間隔。于是過程{N(t),ξ(t),t≥0}形成一個馬爾可夫過程。

2 模型求解

我們定義

通過狀態轉移分析，可以得到下列微分方程：

邊界條件：

對上述方程作L變換可得：

邊界條件：

3 若干性能指標

通過以上的結果和算法過程，我們可以得到關于系統的以下幾個性能指標：

（1）系統中有顧客的概率的L變換為：

[1]DG Kendall.Some Problems in the Theory of Queues[J].J.R.Statis.Soc.B,1951,13.

[2]JM Dobbie.A Double-ended Queueing Problem of Kendall[J].Ops Res,1961,9.

[3]HC Jain.A Double-ended QueueingProblem[J].Def.Sci.J,1962,12.

[4]BRK Kashyap.The Random Walk with Partially Reflecting Barriers with Application to Queueing Theory[J].Proc.Nat.Inst.Sci.India,A,1965,31.

[5]BRK Kashyap.A Double-ended Queueing System with Limited Waiting Space[J].Proc.Nat.Inst.Sci.India,1965,31A.

[6]BRK Kashyap.Further Results for the Double Ended Queue[J].Metrika,1967,11.

[7]BW Conolly,P R Parthasarathy,N Selvaraju.Double-ended Queues with Impatience[J].Computers and Operations Research,2002,29.

[8]尹小玲，蘇健.帶有負顧客的雙端排隊系統[J].中山大學學報（自然科學版）,2004,43.

[9]Berman O,Kapla E H,Shimask D G.Deterninistic Approximations for Inventory Management at Service Facilities[J].I I E Transactions,1993,25.

[10]He Q M,Jewkes E M.Performance Measures of a Make-to-order Inventory-production System[J].Commun Statist-stochastic Model,2000,16.

[11]侯玉梅.簡單生產—庫存系統的優化控制[J].系統工程理論與實踐，2003，（4）.

[12]孫榮恒.排隊論基礎[M].北京：科學出版社，2002.

[13]余玅妙，唐應輝.反饋次數服從幾何分布的M/G/1排隊系統的隊長分布[J].電子學報,2007,35.

[14]陳佩樹，朱翼雋，王曉春.有反饋，強占型的M/G/1重試排隊系統[J].統計與決策，2006，（9）.

[15]B K Kumar,S P Madheswari.The M/G/1 Retrial Queue with Feedback and Starting Failures[J].Applied Mathematical Modelling,2002,26.

（責任編輯/亦 民）

O226

A

1002-6487（2011）03-0077-05

江蘇大學研究生創新計劃項目（CX10B-003X）