帶有反饋和不耐煩的雙端排隊(duì)系統(tǒng)

單凈璇，朱翼雋，濮華盛

（江蘇大學(xué)理學(xué)院 數(shù)學(xué)系，江蘇 鎮(zhèn)江 212013）

帶有反饋和不耐煩的雙端排隊(duì)系統(tǒng)

單凈璇，朱翼雋，濮華盛

（江蘇大學(xué)理學(xué)院 數(shù)學(xué)系，江蘇 鎮(zhèn)江 212013）

文章以需求/供應(yīng)系統(tǒng)為背景，研究了帶有反饋和不耐煩的雙端排隊(duì)模型。假定供應(yīng)方d到達(dá)系統(tǒng)服從泊松分布，需求方到達(dá)系統(tǒng)的時(shí)間間隔服從一般分布，利用補(bǔ)充變量法構(gòu)造馬爾可夫過(guò)程，通過(guò)狀態(tài)轉(zhuǎn)移分析列出微分方程，借助概率母函數(shù)求出該系統(tǒng)的一些性能指標(biāo)。

雙端；補(bǔ)充變量法；概率母函數(shù)；L變換

0 引言

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

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

帶反饋的排隊(duì)系統(tǒng)與經(jīng)典排隊(duì)系統(tǒng)不同，其服務(wù)機(jī)制有所變化，顧客到達(dá)系統(tǒng)后并不一定依次服務(wù)就離開(kāi)系統(tǒng)，而是有可能經(jīng)過(guò)多次，這個(gè)服務(wù)次數(shù)是由反饋機(jī)制所決定的[12-14]，其中主要的Bernoulli反饋已被廣泛應(yīng)用于計(jì)算機(jī)分時(shí)操作和無(wú)線電通訊網(wǎng)絡(luò)系統(tǒng)中，通過(guò)對(duì)它一些指標(biāo)的研究，可安排最合理的運(yùn)行管理方案[15]。

在很多實(shí)際服務(wù)系統(tǒng)中會(huì)有不耐煩顧客出現(xiàn)，產(chǎn)生不耐煩顧客一般有兩種情況：一是顧客剛剛到達(dá)時(shí)，因其不能被馬上服務(wù)而立刻離開(kāi)系統(tǒng)，稱之為阻滯；二是顧客到達(dá)并進(jìn)行排隊(duì)，排隊(duì)一段時(shí)間以后失去耐心，未等到服務(wù)即離開(kāi)系統(tǒng)，稱之為中途離開(kāi)。

綜上所述，本文討論一個(gè)帶有反饋和不耐煩的雙端排隊(duì)系統(tǒng)，比如對(duì)于庫(kù)存系統(tǒng)這個(gè)由倉(cāng)庫(kù)和顧客共同構(gòu)成的雙端排隊(duì)系統(tǒng)中，到達(dá)的顧客隨時(shí)有可能會(huì)因?yàn)椴荒蜔┒x開(kāi)系統(tǒng)。同時(shí)，顧客方并不是依次進(jìn)行服務(wù)后立刻離開(kāi)系統(tǒng)，而是有可能需求得到滿足后發(fā)現(xiàn)貨物質(zhì)量有問(wèn)題需要調(diào)換等問(wèn)題而要求再次服務(wù)，這就要由反饋機(jī)制決定。

1 模型的描述

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

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

2 模型求解

我們定義

通過(guò)狀態(tài)轉(zhuǎn)移分析，可以得到下列微分方程：

邊界條件：

對(duì)上述方程作L變換可得：

邊界條件：

3 若干性能指標(biāo)

通過(guò)以上的結(jié)果和算法過(guò)程，我們可以得到關(guān)于系統(tǒng)的以下幾個(gè)性能指標(biāo)：

（1）系統(tǒng)中有顧客的概率的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]尹小玲，蘇健.帶有負(fù)顧客的雙端排隊(duì)系統(tǒng)[J].中山大學(xué)學(xué)報(bào)（自然科學(xué)版）,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]侯玉梅.簡(jiǎn)單生產(chǎn)—庫(kù)存系統(tǒng)的優(yōu)化控制[J].系統(tǒng)工程理論與實(shí)踐，2003，（4）.

[12]孫榮恒.排隊(duì)論基礎(chǔ)[M].北京：科學(xué)出版社，2002.

[13]余玅妙，唐應(yīng)輝.反饋次數(shù)服從幾何分布的M/G/1排隊(duì)系統(tǒng)的隊(duì)長(zhǎng)分布[J].電子學(xué)報(bào),2007,35.

[14]陳佩樹(shù)，朱翼雋，王曉春.有反饋，強(qiáng)占型的M/G/1重試排隊(duì)系統(tǒng)[J].統(tǒng)計(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.

（責(zé)任編輯/亦 民）

O226

A

1002-6487（2011）03-0077-05

江蘇大學(xué)研究生創(chuàng)新計(jì)劃項(xiàng)目（CX10B-003X）