唐韻，劉力維

(南京理工大學理學院，江蘇 南京210094)

1.引言

重試排隊系統(tǒng)在我們的日常生活中無處不在，并且學者對它的研究已經非常廣泛，但大部分都是利用隨機過程或動態(tài)規(guī)劃技術進行系統(tǒng)性能分析，而較少從經濟學角度進行研究.文[1]對已有的重試排隊系統(tǒng)的研究方法和成果進行了總結.文[2]利用嵌入馬爾科夫鏈和母函數的方法研究了一種批到達重試排隊系統(tǒng)，求得了重試軌道中隊長的分布，進而得到各性能指標.文[3]研究了帶有恒定重試率的單服務臺排隊系統(tǒng)的顧客最優(yōu)策略和最大社會收益.文[4]針對不可見情形和可見情形的經典單服務臺重試排隊系統(tǒng)，研究了顧客均衡策略和社會最優(yōu)的止步策略.文[5]針對局域網的應用研究了帶有恒定重試率和延遲休假的M/M/1排隊系統(tǒng)，得到了顧客進入系統(tǒng)的納什均衡策略和社會價格最優(yōu)策略.文[6]研究了帶有恒定重試率和N策略的M/M/1 排隊系統(tǒng)，分析了顧客行為和社會收益最大問題.文[7]在文[6] 的基礎上研究了帶有啟動時間的情形.文[8]研究了帶有恒定重試率和工作假期的單服務臺排隊系統(tǒng)，分析了顧客均衡策略和社會最優(yōu)策略.

因為系統(tǒng)高昂的建設成本和運行成本，現實生活中的很多服務系統(tǒng)會采用某些策略來控制系統(tǒng)的啟動和關閉，其中N策略應用得十分廣泛.文[9]第一次在M/M/1系統(tǒng)中提到了N策略的概念.之后，文[10-12]用了幾種不同的方法研究了這種控制策略.值得注意的是N策略雖然在經典排隊系統(tǒng)中已經被研究，但是從經濟學角度來研究它的文獻還比較少.文[13]針對不可見情形和可見情形，研究了帶有N 策略和假期的排隊系統(tǒng)的顧客均衡策略和社會最優(yōu)策略.文[14]將文[13] 拓展為帶有異類顧客的情形.文[15]針對部分可見情形，研究了假期排隊系統(tǒng)的顧客策略行為和社會最優(yōu)問題.

另外，在許多排隊模型中會假設服務臺完全可靠，但很明顯這種假設是不符合實際的，因為服務臺在服務顧客時可能會發(fā)生損壞且需要立即維修的情況無法被忽視，這就是帶有不可靠服務臺的排隊系統(tǒng).帶有不可靠服務臺的排隊模型可以應用于計算機通信系統(tǒng)和機械生產制造系統(tǒng)中，機器可能因工作時間過長或某些自身原因發(fā)生故障，則不得不停止服務，直至維修結束才能繼續(xù)進行服務.文[16]最早研究服務臺可能發(fā)生故障的排隊系統(tǒng)，并得到了相關數量指標.文[17]研究了M/G/1不可靠服務排隊系統(tǒng)，并首次給出了該系統(tǒng)的可靠性分析.文[18]針對完全可見情形和幾乎可見情形，研究了一個帶有故障和維修期的M/M/1排隊系統(tǒng)并得到顧客的均衡策略.文[19]在文[18]的基礎上得出當隊長信息不可見時顧客遵循混合均衡止步策略.文[20]又將以上結果推廣到離散不可靠服務排隊系統(tǒng)中，給出了顧客的個體最優(yōu)均衡策略.文[21]研究了帶有服務中斷的認知無線電網絡系統(tǒng)，在該系統(tǒng)中主級用戶的出現會導致次級用戶的服務中斷.文[22]針對隊長可見情形和不可見情形，研究了帶有災難到達的M/M/1排隊系統(tǒng)的納什均衡和社會最優(yōu)止步策略.文[23]研究了不可靠Mn/G/1排隊系統(tǒng)的最優(yōu)加入策略，其中顧客的到達率依賴于系統(tǒng)中的顧客數.

本文主要研究: 帶有N策略和不可靠服務臺且擁有恒定重試率的M/M/1排隊系統(tǒng).現在重試排隊系統(tǒng)在工業(yè)工程和商業(yè)管理上的應用非常廣泛.例如呼叫中心的管理模式: 如果代理商在客戶打進電話時有空，則將立即為來電服務，如果發(fā)現所有服務臺都忙，則客戶必須掛斷電話，并在隨機時間后重試.在現代服務系統(tǒng)中，呼叫中心可以在客戶到達時給他提供一些系統(tǒng)信息，例如，預期的等待時間和服務臺狀態(tài)，客戶可以根據可用的信息及其預期收益來決定是否加入系統(tǒng).我們在此基礎上還考慮了N策略和不可靠服務臺的情況，使得該模型具有更廣的應用領域和現實意義.

2.模型描述

我們考慮一個帶有N策略和不可靠服務臺且擁有恒定重試率的M/M/1排隊系統(tǒng).顧客到達排隊系統(tǒng)為參數為λ的泊松過程.如果到達的顧客發(fā)現服務臺處于空閑狀態(tài)，則他會立即被服務，在服務臺前面沒有等待空間，如果到達的顧客發(fā)現服務臺處于繁忙狀態(tài)，則他可能會加入虛擬的重試軌道，實際上，這些軌道中的顧客可以被看作“等待顧客”，當服務臺處于空閑狀態(tài)時，服務臺會根據FCFS規(guī)則從“等待名單”中選擇顧客進行服務，“等待顧客”的重試時間間隔服從參數為θ的指數分布，但是如果在這個過程中有新的顧客到達系統(tǒng)，則“等待顧客”的重試將會被打斷，服務臺會對新到達的顧客進行服務.我們假設服務時間服從相互獨立且參數為μ的指數分布.服務臺在服務一名顧客時會因為它到達“壽命”極限而損壞，服務臺的“壽命”服從參數為γ的指數分布.如果服務臺發(fā)生損壞，則它會被立即送去維修，且正在被服務的顧客需要等待服務臺被修好，然后完成他的剩余服務，維修時間服從參數為α的指數分布，另外，服務臺在被修好以后和新的一樣，我們假設服務臺在損壞的時候，新到達的顧客不會選擇加入系統(tǒng)(包括重試軌道).當服務臺處于休眠狀態(tài)時，它不會為顧客提供任何服務，直到重試軌道中的顧客數達到給定的閾值N(N ≥1)，服務臺被啟動，其啟動時間可忽略不計.當服務臺被啟動以后，它會為所有的顧客提供窮盡服務，在這之后，排隊系統(tǒng)會變空，服務臺會再次進入休眠狀態(tài).我們假設到達時間間隔、服務時間、重試時間間隔、服務臺“壽命”和維修時間相互獨立.

新顧客到達排隊系統(tǒng)的瞬間會決定加入系統(tǒng)或者止步.每一位顧客在完成服務后會獲得回報R，并且他們在系統(tǒng)中的逗留期間(包括排隊等待和被服務期間)的單位費用為C.假設每位顧客都是風險中立的且想自己的收益最大化，如果服務后得到的回報比逗留期間的費用大，則顧客會選擇加入系統(tǒng)，如果服務后得到的回報等于或小于逗留期間的費用，則顧客會選擇止步.我們假設:

其中最后一項表示不可靠排隊系統(tǒng)的廣義服務時間(見文[17])，這能夠保證到達的顧客發(fā)現服務臺處于空閑狀態(tài)會選擇加入系統(tǒng).我們進一步假設顧客一旦做出進入系統(tǒng)的決定則不能反悔，即不能中途選擇退出; 如果顧客決定止步也不能再次返回系統(tǒng).

對于所研究的排隊系統(tǒng)，定義{I(t)，N(t)，t ≥0}表示在時刻t時系統(tǒng)的狀態(tài)，其中I(t)表示服務臺的狀態(tài)(0 : 休眠，1 : 繁忙，2 : 空閑，3 : 損壞)，N(t) 表示表示軌道中的顧客數.很明顯，隨機過程{I(t)，N(t)，t ≥0} 在狀態(tài)空間{(0，i)，0 ≤i ≤N -1;(1，j)，j ≥0;(2，k)，k ≥1，(3，n)，n ≥0} 上為一個連續(xù)時間馬爾科夫鏈.

在這篇文章中，主要研究幾乎不可見的情形，即到達的顧客只知道服務臺的狀態(tài).在這個規(guī)則下顧客到達瞬間選擇加入系統(tǒng)的概率就依賴于服務臺當前的狀態(tài)I(t)，我們假設當顧客在發(fā)現服務臺狀態(tài)為i時均以相同的策略以概率qi(i = 0，1，2，3)加入系統(tǒng)，即有效均衡到達率λi=λqi(i=0，1，2，3)，這說明λi≤λ.

因為假設條件(2.1)的存在，則當顧客到達系統(tǒng)時發(fā)現服務臺處于空閑狀態(tài)，他肯定會選擇加入系統(tǒng)，這意味著λ2=λ，又因為假設服務臺在損壞時，到達的顧客不會加入系統(tǒng)(包括重試軌道)，即λ3=0，所以，在這兩種情況下，顧客的決策行為是確定的，不受其它顧客決策行為所影響的.因此，只需要研究當服務臺狀態(tài)處于I(t)=0，1時(0: 休眠，1: 繁忙)，到達顧客的決策行為.本文中，通過I(t)=0，1時顧客的均衡到達率來研究顧客的決策行為.該排隊系統(tǒng)穩(wěn)態(tài)存在當且僅當(見文[3，24]):

其系統(tǒng)狀態(tài)轉移率如圖2.1所示.

圖2.1 系統(tǒng)狀態(tài)轉移率圖

3.均衡到達率

在這一節(jié)里，我們研究在幾乎不可見的情形下顧客的均衡到達率.令{p(0，i)，0 ≤i ≤N-1;p(1，j)，j ≥0;p(2，k)，k ≥1;p(3，n)，n ≥0}馬爾科夫鏈{I(t)，N(t)，t ≥0}的穩(wěn)態(tài)分布.則相應的母函數定義如下:

其中|z|≤1.我們得到如下初步結果.

引理3.1對于帶有N策略和不可靠服務臺且擁有恒定重試率的M/M/1 排隊系統(tǒng)，若給定到達率(λ0，λ1，λ，0)，則服務臺狀態(tài)i=0，1，2，3 的穩(wěn)態(tài)概率分別如下:

而且我們還可以得到如下等式:

其中:

證穩(wěn)態(tài)分布的平衡方程如下:

由(3.11)可以得到:

所以:

由(3.16)很容易可以得到:

由(3.12)和(3.13)可以得到:

將(3.19)帶入上式可以得到:

由(3.10)、(3.14)、(3.15)和(3.17)可以得到:

再聯(lián)立(3.21)和(3.22)可以得到:

最后，由(3.19)可以得到:

從(3.18)、(3.23)、(3.24)和(3.25)可以看到P0(z)、P1(z)、P2(z)和P3(z)均可以用p(0，0)來表示，再根據歸一性，就可以計算出:

另外，通過對(3.18)、(3.23)、(3.24)和(3.25)分別對z求一階導，然后取z =1，就可以得到(3.5)、(3.6)、(3.7)和(3.8).

設T(0，j)，1 ≤j ≤N -1，T(1，j)，j ≥0，T(2，j)，j ≥1，和T(3，j)，j ≥0分別表示一名標記顧客處于重試軌道中第j個位置，且服務臺狀態(tài)為i=0，1，2，3 的逗留時間.我們可以得到如下引理.

引理3.2對于帶有N策略和不可靠服務臺且擁有恒定重試率的M/M/1排隊系統(tǒng)，若一名標記顧客處于重試軌道中第j個位置，且服務臺狀態(tài)為i = 0，1，2，3，則他的預期逗留時間分別為:

證通過分析我們可以得到如下等式:

(3.30)式表示不可靠排隊系統(tǒng)的廣義服務時間(見文[17]).若一名標記顧客處于重試軌道中的第j個位置且服務臺處于1狀態(tài)，則他的預期逗留時間由以下幾部分組成，首先他需要等待一段時間，這段時間表示接下來有新顧客到達并加入系統(tǒng)、正在被服務的顧客完成服務以及服務臺損壞三者中有一個事件先發(fā)生的時間，且它服從參數為λ1+μ+γ的指數分布.若接下來以概率發(fā)生第一個事件，則該標記顧客的預期逗留時間變?yōu)門(1，j); 若接下來以概率發(fā)生第二個事件，則該標記顧客的預期逗留時間變?yōu)門(2，j); 若接下來以概率發(fā)生第三個事件，則該標記顧客的預期逗留時間變?yōu)門(3，j)，通過上述分析，我們得到(3.31).利用相同的分析方法，我們可以得到(3.32)、(3.33)和(3.34).

接下來，將(3.33)和(3.34)帶入(3.31)，可以得到:

再結合(3.30)，可以得到(3.27):

最后利用(3.27)，再經過簡單的計算，我們可以很容易得到(3.26)、(3.28) 和(3.29).

通過引理3.1和引理3.2，可以得到如下定理:

定理3.1對于帶有N策略和不可靠服務臺且擁有恒定重試率的M/M/1排隊系統(tǒng)，若給定到達率(λ0，λ1，λ，0)，則一個標記顧客到達瞬間發(fā)現服務臺處于0狀態(tài)或1狀態(tài)并選擇加入系統(tǒng)的平均預期逗留時間分別為:

證設W0(k)示重試軌道中有k個顧客且服務臺處于0 狀態(tài)，一名顧客選擇加入系統(tǒng)的預期逗留時間.很容易可以看出W0(k)可以用T(0，k+1) 來表示，即:W0(k) = T(0，k+1) =可由(3.26)得到.另設P(k|0)表示服務臺處于0狀態(tài)且重試軌道中有k個顧客的條件概率，即因此，一個標記顧客到達瞬間發(fā)現服務臺處于0狀態(tài)并選擇加入系統(tǒng)的平均預期逗留時間為:

再由引理3.1我們就可以得到(3.36).同樣的一個標記顧客到達瞬間發(fā)現服務臺處于1狀態(tài)且重試軌道中有k個顧客并選擇加入系統(tǒng)的條件概率和平均預期逗留時間分別為:

其中，P1(1)由引理3.1可得，T(1，k+1)由引理3.2可得.因此，一個標記顧客到達瞬間發(fā)現服務臺處于1狀態(tài)并選擇加入系統(tǒng)的平均預期逗留時間為:

再次由引理3.1我們就可以得到(3.37).

從定理3.1很容易可以看出，平均預期逗留時間W0(或W1)是獨立于λ1(或λ0)的，所以我們可以分別得到相應的均衡到達率(唯一均衡或多元均衡).而且，在接下來的定理3.2可以發(fā)現擁擠偏好(FTC)情形和擁擠厭惡(ATC)情形在某些情況下是存在的.

定理3.2對于帶有N策略和不可靠服務臺且擁有恒定重試率的M/M/1排隊系統(tǒng)，當服務臺處于休眠狀態(tài)(i=0)時，顧客均衡到達率如下:

當服務臺處于繁忙狀態(tài)(i=1)時，顧客均衡到達率如下:

其中，

證首先，一名顧客到達時發(fā)現服務臺處于休眠狀態(tài)，止步總是一種均衡策略，因為如果其它所有顧客均選擇止步，則服務臺永遠不會被激活，那么對于標記顧客來說此時止步是最好的選擇.所以，λe=0總是一個均衡到達率且與R無關.

我們現在來考慮當標記顧客到達時發(fā)現服務臺處于休眠狀態(tài)的正的均衡到達率.根據收益函數的結構，標記顧客選擇加入系統(tǒng)的凈收益等于他完成服務獲得的獎勵R與逗留總花費之差，所以根據定理3.1，我們可以得到標記顧客預期凈收益為:

我們可以看出，S0(λ0)是關于λ0∈[0，λ] 嚴格單調遞增的，所以，我們可以得到如下幾個結論:

同樣的，根據定理3.1，如果一名到達顧客發(fā)現服務臺處于繁忙狀態(tài)且決定加入系統(tǒng)，他的預期凈收益為:

另外，(3.39)的證明過程同上述(3.38)的證明過程.

注3.1因為S1(λ1)是關于λ1∈[0，λ]的減函數，一方面，當顧客到達率為λ1且λ1＞時，若標記顧客到達并選擇加入系統(tǒng)，則他的預期凈收益為負值，因此，此時標記顧客的唯一最優(yōu)決策是止步(λ1=0)，另一方面，當顧客到達率為λ1且λ1＜時，若標記顧客到達并選擇加入系統(tǒng)，則他的預期凈收益為正值，因此，此時標記顧客的唯一最優(yōu)決策是加入(λ1=λ).上述分析表明了: 標記顧客的最優(yōu)決策是關于其它顧客所采用決策的減函數，即: 其它顧客的到達率越高，則標記顧客的最優(yōu)到達率越低，這是擁擠厭惡(ATC)情形，所以至少存在一個均衡到達率.另外要注意唯一均衡到達率λ′1是穩(wěn)定的，因為W1是關于λ1∈[0，λ]的增函數，所以顧客到達率λ1的增加會使得平均預期逗留時間的增加，這樣就會導致選擇加入系統(tǒng)的顧客變少，所以顧客到達率λ1的增加就會得到遏制，因此唯一均衡到達率就會逐漸趨于一個穩(wěn)定的值.同樣的，我們很容易可以看出來S0(λ0)是關于λ0∈[0，λ]的增函數，應用上述相同的分析方法，可以得到它對應的是擁擠偏好(FTC)情形，所以多元均衡到達率可能存在且均衡到達率是不穩(wěn)定的.

4.社會收益

社會收益等于所有顧客預期凈收益之和，所以要求社會最優(yōu)到達率，需要將所有顧客看作一個整體并且使得社會收益最大化.首先，我們給出社會收益函數S(λ0，λ1) 的表達式，然后尋找使它最大化的參數(服務臺處于0狀態(tài)時的社會最優(yōu)到達率)和(服務臺處于1狀態(tài)時的社會最優(yōu)到達率).

定理4.1社會收益函數表達式如下:

其中，P0(1)、P1(1)和P2(1)由引理3.1可得，W0和W1由定理3.1可得.

證如果λ0= 0，則服務臺永遠處于休眠狀態(tài)，不會被激活，所以此時社會收益為0，得到(4.1)第一部分; 如果λ00，根據社會收益的定義，社會收益函數等于所有顧客的預期凈收益之和，即:

得到(4.1)的第二部分.

注4.1通過計算，可以得到這說明當服務臺處于休眠狀態(tài)且顧客到達時間間隔趨于無窮大的時候，社會收益會為負值.這種現象可以從管理者的角度理解，當顧客到達率為無窮小的時候，管理者關閉系統(tǒng)是最好的選擇.

注4.2當θ →∞時，即重試時間趨于0，這個時候我們所研究的系統(tǒng)可以看作是一個帶有N策略和不可靠服務臺的M/M/1排隊系統(tǒng).

因為求得S(λ0，λ1)的表達式非常復雜，通過傳統(tǒng)的計算很難得到相應的結果，所以，在后一節(jié)中我們采用粒子群優(yōu)化算法(PSO)得到和的值.

PSO算法最先由Kennedy和Eberhart在1995年提出，它有精度高、收斂速度快等特點，使用它我們不需要對目標函數做太多的分析，可以很容易找到全局最優(yōu)解，這些特性剛好是我們所需要的，下面就簡單介紹一下PSO 算法的要點.

首先，需要設置如下幾個參數: 最大迭代次數、目標函數的自變量個數和粒子的最大速度，其中每個粒子只具有兩種屬性: 速度和位置，速度代表粒子移動的快慢，位置代表粒子移動的方向.開始時位置信息會設置為整個搜索空間，并且會在速度區(qū)間和搜索空間上隨機初始化粒子的速度和位置，然后不斷迭代更新粒子的速度和位置，同時得到每個粒子的最優(yōu)解(個體極值)，再從這些個體極值中找到一個最優(yōu)解稱為本次全局最優(yōu)解，將它再與歷史最優(yōu)進行比較，不斷更新，最后，就能得到我們所需要的全局最優(yōu).

速度和位置更新公式如下:

其中，ω稱為慣性因子，較大時，算法全局尋優(yōu)能力強，局部尋優(yōu)能力弱，較小時，算法全局尋優(yōu)能力弱，局部尋優(yōu)能力強，所以，通過調整ω的大小，可以對算法全局尋優(yōu)能力和局部尋優(yōu)能力進行調節(jié).c1和c2稱為加速常數，前者稱為每個粒子的個體學習因子，后者稱為每個粒子的社會學習因子.pid表示第i個變量的個體極值的第d維，pgd表示全局最優(yōu)解的第d維.

本文中，我們設置ω =0.9，c1=c2=2，粒子數S =100，最大迭代次數M =2000.盡管迭代次數不夠大，但重復了6次發(fā)現結果幾乎一樣.

5.數值結果

本節(jié)中，我們主要基于PSO算法研究不同參數(N，R，θ，μ，α，γ)對社會收益函數S(λ0，λ1)的影響，導出了的數值最優(yōu)解進而得到然后再對系統(tǒng)性能指標的敏感性進行分析.

圖5.1 社會最優(yōu)到達率()和社會收益S()關于N的變化(λ=1，μ=θ =3，α=γ =1，R=8，C =2)

綜上所述: 如果社會管理者想得到一個較高的社會收益，他就必須設置N為一個相對較小的值.我們在圖5.1(b)中可以看到，當N = 1 時，社會收益達到最大值，也就是說，當一名顧客到達時發(fā)現服務臺處于休眠狀態(tài)并選擇加入系統(tǒng)，系統(tǒng)就會被立即激活，這種情況下系統(tǒng)的社會收益達到最大值.

圖5.2 社會最優(yōu)到達率()和社會收益S()關于R的變化(λ=1，μ=θ =3，α=γ =1，N =4，C =2)

圖5.2(b)顯示: 當R = 1，2，3，4，5，6時，S() = 0，當R ＞6時，S變?yōu)檎登抑饾u變大.

綜上所述: 后到顧客帶來的正收益將彌補早到顧客的損失，所以從整體來看，所有顧客的社會收益都是正值，因此，如果社會管理者想要獲得一個較高的社會收益，他需要設定一個相對較大的R，鼓勵更多的顧客選擇加入系統(tǒng).

圖5.3 社會最優(yōu)到達率和社會收益關于θ的變化(λ=1，μ=3，α=γ =1，N =4，R=8，C =2)

綜上所述: 社會管理者如果想獲得一個較大的社會收益，則他需要設定相對較大的θ.

圖5.4 社會最優(yōu)到達率()和社會收益S()關于μ的變化(λ=1，θ =3，α=γ =1，N =4，R=8，C =2)

綜上所述: 若社會管理者希望系統(tǒng)被激活以后有更多的顧客選擇加入系統(tǒng)，以獲得較高的社會收益，他需要設置μ＞2.4.

圖5.5 社會最優(yōu)到達率(，)和社會收益S(，)關于α的變化(λ=1，μ=θ =3，γ =1，N =4，R=8，C =2)

綜上所述: 若社會管理者希望獲得較高的社會收益，他需要設置α ＞0.6.

圖5.6 社會最優(yōu)到達率(，)和社會收益S(，)關于γ 的變化(λ=1，μ=θ =3，α=1，N =4，R=8，C =2)

綜上所述: 若社會管理者希望獲得較高的社會收益，則他必須保證服務臺的“質量”，使服務臺“壽命”盡可能的長.