帶有負顧客和啟動時間的排隊系統最優策略分析

何柳青,田瑞玲

(燕山大學理學院,河北 秦皇島 066004)

1.引言

現實中存在許多系統被干擾的情況,如操作失誤致使生產系統中生產進度受到制約,木馬入侵使得計算機系統崩潰,外部撞擊使得車輛系統故障等.以上舉例中的干擾信息被稱之為負顧客,它的到達不僅可以使得系統故障,還可以在系統忙期時產生抵消的作用.自20世紀90年代Gelenbe[1]首次提出關于負顧客的排隊模型起,關于負顧客的研究不斷涌現.尤其近些年從經濟學角度分析負顧客排隊模型逐漸成為了熱點.在經濟學和博弈論的背景下,顧客有決策權,可根據自身掌握的有關系統的信息做出進隊還是止步的決定,考慮顧客的行為使得研究更有實用性.Lee[2]研究了帶有負顧客的排隊系統在幾乎不可視和完全不可視兩種情形下的顧客止步和最優定價策略.WANG等[3]研究了帶有負顧客的重試排隊系統,討論了完全可視和幾乎不可視兩種情形下的納什均衡策略和社會最優問題.Panda和Goswami[4]考慮了帶有負顧客和工作休假的M/M/1排隊系統,并且討論了四種信息水平下的均衡策略行為.ZHANG和WANG[5]分析了帶有負顧客和N策略的M/M/1排隊系統,并討論了納什均衡策略.

在實際中,許多系統由閑期轉入忙期需要一段準備時間,即啟動時間.比如設備開機過程中要經歷供電和初始化等一系列操作,又比如發動機接受到發動指令時需經過轉動曲軸并使其達到一定的轉速等操作才能完成發動,這些例子中的準備時間都可以抽象為啟動時間.Burnetas和Economou[6]分析了帶有啟動時間的M/M/1排隊系統在完全可視,幾乎可視,幾乎不可視和完全不可視四種信息水平下的均衡止步策略.SUN,GUO和TIAN[7]則進一步考慮了帶有啟動期和關閉期的排隊系統,并分析了顧客的進隊閾值策略.CHEN和ZHOU[8]考慮了帶有啟動時間和故障的排隊系統中顧客的均衡止步策略.在此基礎上,CHANG和WANG[9]將其推廣到重試排隊系統中,分析了具有啟動時間和故障的重試隊列.YUE等[10]研究了具有啟動時間和單重休假的M/M/1排隊系統,分析了完全可視和完全不可視兩種情形下的顧客止步策略.ZHOU等[11]研究了帶有啟動時間和N 策略的重試排隊系統的顧客的均衡止步行為.關于排隊經濟策略的分析還可以參閱文[12-14].

參閱已有的文獻,發現負顧客和啟動時間受到了人們的普遍關注,因此本文展開了對結合負顧客和啟動時間的排隊模型的相關研究.負顧客到達時,會使得服務臺故障,并且抵消正在接受服務的顧客.而啟動時間的引入,使得空閑服務臺及時去休假,不僅能在某種程度上降低服務臺故障的風險,還能起到節能的作用.此模型在計算機系統、通信系統、車輛工程等領域有著普遍的應用.比如在計算機領域中,當按下電源開關時,計算機會經歷供電、BIOS自檢、系統引導等一系列的流程才能完成啟動進行工作.在工作過程中,可能會遭遇木馬入侵,使得系統文件受到損害,正在進行的操作被迫終止.當受損的系統文件完成備份以后,計算機將恢復工作狀態.鑒于其實用性,本文對其做出研究分析.在本文中,我們考慮具有啟動時間和負顧客的排隊系統中的顧客策略行為,更貼近實際問題,也豐富了現有的排隊內容.利用概率母函數法計算系統的重要性能指標,然后基于收益-成本結構討論顧客的均衡策略和社會最優策略.最后通過數值分析考察社會最優進入策略和最優社會福利關于一些參數的敏感性.

2.模型描述

考慮一個帶有負顧客和啟動時間的M/M/1排隊系統.到達系統的顧客有兩種,正顧客和負顧客,分別服從參數為λ和α的泊松流.正顧客的到達是為了尋求服務,而當負顧客到達時,不僅會抵消正在接受服務的正顧客,還會使得服務臺故障.發生故障的服務臺即刻被送去維修,維修時間服從參數為β的指數分布.故障時顧客不會進入系統.當系統為空時,服務臺會立即關閉.若有新顧客到達,服務臺會立即啟動.啟動時間服從參數為θ的指數分布.服務時間服從參數為μ的指數分布,服務順序是先到先服務.假設顧客到達的間隔時間,負顧客到達的間隔時間,服務時間,維修時間,啟動時間是相互獨立的.

定義(N(t),I(t))為時刻t系統的狀態,其中N(t)表示系統中顧客的數量,I(t)表示服務臺狀態(0:故障;1:繁忙;2: 啟動).過程{(N(t),I(t)),t ≥0}是狀態空間?={(n,i),n ≥0,i=0,1,2}的連續時間馬爾科夫鏈.

本文感興趣的是顧客到達系統時的策略行為,為了量化此過程,引入線性“收益-成本”結構,每個顧客在服務完成后,會獲得回報R,同時也要支付成本,每單位時間的逗留成本是C.假設顧客是風險中立的,期望最大化自己的收益,并且一旦做出決定不得后悔.

顧客到達系統時,會根據其了解的有關系統狀態的信息來決定進隊的策略.本文考慮了不可視的兩種情形: 1)幾乎不可視: 到達顧客被告知服務臺的狀態信息;2)完全不可視: 到達顧客對系統的狀態一無所知.

3.幾乎不可視情形

本節研究幾乎不可視情形下顧客的均衡進入概率.在幾乎不可視情形下,到達的顧客掌握了服務臺的狀態信息,因此假設顧客遵循混合進隊策略(q1,q2),q1和q2分別代表服務臺狀態為1和2的顧客進入概率,實際到達率為λqi.狀態轉移圖如圖3.1所示.

定義pn,i為系統的穩態概率,相應的母函數定義如下

其中|z|≤1.

定理3.1在帶有負顧客和啟動時間的幾乎不可視M/M/1排隊系統中,假設<1,服務臺狀態i=0,1,2的穩態概率分別如下

證系統的平衡方程如下

將式(3.15)和(3.8)代入(3.16)可得

將式(3.14)代入(3.17)可得

將式(3.18)代入(3.15)可得

觀察式(3.1),(3.2),(3.3)和(3.7),容易得出此排隊系統的穩態條件為<1.

接下來,計算顧客在不同狀態下進入系統的平均逗留時間.當標記顧客進入系統發現自己位于系統中第j個位置,且服務臺狀態為i時,其平均逗留時間為T(j,i),可以得到如下定理.

定理3.2對于帶有負顧客和啟動時間的幾乎不可視M/M/1排隊系統,標記顧客到達時發現自己處于系統中第j個位置,且服務臺狀態為i(i=1,2)的平均逗留時間分別如下

證通過分析,可以得到如下等式

將式(3.25)代入式(3.23),可得

由式(3.22),可得

利用式(3.24),可得式(3.21).

定理3.3對于帶有負顧客和啟動時間的幾乎不可視M/M/1排隊系統,一名標記顧客到達時發現服務臺狀態為i(i=1,2)并選擇進入系統的平均逗留時間分別如下

定理3.4對于帶有負顧客和啟動時間的幾乎不可視M/M/1排隊系統,服務臺處在啟動期和忙期(i=1,2)時,顧客均衡進入概率有以下三種情況

證根據線性“收益-成本”結構,可得服務臺處于啟動期時的平均剩余效用

求式(3.31)對q2的一階導,可得

容易看出U′2(q2)<0,U2(q2)是關于q2∈[0,1]的減函數.分以下三種情形討論

服務臺處于忙期時的平均剩余效用為U1(q1,q2),其函數表達式如下

U1(q1,q2)是關于q2和q1的函數,上面已經給出了的結果,因此它現在只與q1有關,求U1(q1)關于q1的一階導,可得

容易看出U′1(q1)<0,因此U1(q1)是關于q1∈[0,1]的減函數,分以下幾種情形討論

前面討論了顧客的均衡進隊策略,每個客戶都希望獲得最大的平均剩余效用.但從整體來看,這些行為決策不一定是最優的.因此,進一步考慮社會福利,把所有顧客視為一個整體來討論.Sau(q1,q2)表示幾乎不可視情形下的社會福利,表達式如下

其中,P1(1)和P2(1)由定理3.1可得,W1(q1,q2)和W2(q2)由定理3.2可得.

從圖3.2中可以看出, Sau(q1,q2)隨著q1和q2的增大呈現先增大后減小的趨勢. 這是因為當q1和q2較小時, 系統中的顧客也較少, 此時顧客需要支付的等待成本就小, 社會福利增大. 隨著q1和q2的增大, 進入系統的顧客越來越多, 系統變得擁擠, 需要支付的等待成本增大, 社會福利減小. 從圖中還可以得知, 使Sau(q1,q2)取得最大值的解為然而根據定理3.4可以得到此時的均衡解為很明顯最優解和均衡解是不一致的, 這印證了個體均衡和社會最優的差異性. 個體均衡的決策背離了社會最優的決策, 這是由于每個個體為了追求自身效用的最大化導致系統擁擠或否, 使得整體的社會福利減少. 社會管理者可以通過征收入場費或者給予補貼來消除二者之間的差距.

圖3.2 Sau(q1,q2)關于q1和q2的變化(λ=1,μ=2.5,θ=2,α=0.2,β=1,R=5,C=4)

本文接下來將討論社會福利, 引入遺傳算法求得最優解并給出一些數值結果. 借助遺傳算法去求最優的社會福利Sau(,)以及最優進隊概率和. 下面介紹遺傳算法的步驟.

步1 首先通過隨機方式產生若干由確定長度編碼的初始群體;

步2 借助適應度函數對每個個體進行評價,通過輪盤法選擇優秀個體參與遺傳操作,淘汰劣質個體;

步3 經遺傳操作(復制,交叉,變異)的個體集合形成新一代種群,重復步驟2,直到滿足停止準則;

步4 將后代中表現最好的個體作為遺傳算法的結果.

在遺傳算法中,需要明確種群中個體數目(pop),編碼方式,交叉概率(pc),變異概率(pm),選擇個體的方法,終止運行的條件.在本文中,我們設置pop=200,pc=0.9,pm=0.1,采用十進制編碼方式,輪盤法選擇個體,通過每個個體與總體的適應度占比來衡量其優劣,比值越大越不容易被淘汰.當滿足迭代次數時停止運行,即iter≥500.

借助遺傳算法尋得最優解后,將在文章第5部分進一步做最優解關于參數的敏感性分析.

4.完全不可視情形

本節研究完全不可視情形下顧客的均衡進入概率.在完全不可視情形下,到達顧客既不知道服務臺的狀態信息,也不知道系統的隊長信息,假設他們都以概率q進入,那么實際到達率為λq.狀態轉移圖如圖4.1所示.

完全不可視情形相當于幾乎不可視情形的一種特殊情形,上一節已經給出了幾乎不可視情形下的一些結果,對完全不可視排隊系統有著重要的參照意義.令式(3.1)-(3.7)中的q1=q2=q,可以得到以下的結果.

定理4.1對于帶有負顧客和啟動時間的完全不可視M/M/1排隊系統,假設<1,服務臺狀態i(i=0,1,2)的穩態概率分別如下

定理4.2對于帶有負顧客和啟動時間的完全不可視M/M/1排隊系統,一名標記顧客到達并選擇進入系統的平均逗留時間為

證根據PASTA性質,系統中顧客的有效到達率為

系統中的平均顧客數為

由Little公式得到顧客的平均逗留時間

定理4.3對于帶有負顧客和啟動時間的完全不可視M/M/1排隊系統,均衡進入概率qe如下

證根據線性“收益-成本”結構,可得顧客的平均剩余效用U(q),表達式如下

求式(4.12)關于q的一階導,可得

基于函數的單調性,分以下三種情形來討論

U(q)是關于q的減函數,這表明當q越大時,即其他顧客的進入概率越大時,被標記顧客進入系統并接受服務后獲得的平均剩余效用越少,那么被標記顧客進入系統的意愿越低,這種行為被稱為擁擠厭惡,由Hassin和Haviv[15]首先提出并命名.此外,還可得知均衡進入概率是穩定的.因為T(q)隨著q的增加而增加,平均逗留時間的增加會使得進入系統的顧客減少,因此q的增加會得到遏制,最終趨于平穩.

Sfu(q)表示完全不可視情形下的社會福利,表達式如下

其中,λeff和E(N)由定理4.2可得.

從圖4.2中可以看出,隨著進入概率的增大,單位時間內系統中的顧客數增大導致社會福利增大,然而過多的顧客逗留在系統中,導致顧客支付的等待成本增大,社會福利減小.同時可以知道,此時使得社會福利最大的解為q?=0.65.然而根據定理4.1可以得到此時的均衡解為qe=1,最優解和均衡解是存在差異的,個體最優并不能達到社會整體最優,因此社會管理者可以通過征收入場費來遏制顧客的個體決策行為,使二者達成一致.

圖4.2 Sfu(q)關于q的變化(λ=1,μ=2.5,θ=2,α=0.2,β=1,R=5,C=4)

下文將借助遺傳算法去尋找最優的社會福利Sfu(q?)和最優的進隊概率q?,并進行數值分析.

5.數值分析

本節給出了一些數值例子.數值分析能夠直觀地展示一些現象,形象地刻畫排隊模型的實用性.首先,在幾乎不可視和完全不可視的情形下,本節分析了系統參數對社會最優進入概率的影響.然后進一步比較兩種情形下的最優社會福利,并討論披露更多的系統信息是否能帶來更多的社會福利.

本節給出了一些數值例子. 數值分析能夠直觀地展示一些現象, 形象地刻畫排隊模型的實用性. 首先, 在幾乎不可視和完全不可視的情形下, 本節分析了系統參數對社會最優進入概率的影響. 然后進一步比較兩種情形下的最優社會福利, 并討論披露更多的系統信息是否能帶來更多的社會福利.

圖5.1 最優進入概率(,)和q?關于μ的變化(λ=1,θ=2,α=0.2,β=1,R=5,C=3)

圖5.2 最優進入概率(,)和q?關于θ的變化(λ=1,μ=2.5,α=0.2,β=1,R=5,C=3)

圖5.3 最優進入概率(,)和q?關于α的變化(λ=1,μ=2.5,θ=2,β=1,R=5,C=3)

圖5.4 最優進入概率(,)和q?關于β的變化(λ=1,μ=2.5,θ=2,α=0.2,R=5,C=3)

觀察圖5.1-5.4, 從整體上來看, 不論最優進入概率關于參數的變化是何種走勢, q?大致總是夾在和之間. 也就是說, 在完全不可視的排隊系統中, 到達顧客進入系統的概率介于幾乎不可視排隊系統的兩個進入概率之間.

觀察圖5.1-5.4,從整體上來看,不論最優進入概率關于參數的變化是何種走勢,q?大致總是夾在和之間.也就是說,在完全不可視的排隊系統中,到達顧客進入系統的概率介于幾乎不可視排隊系統的兩個進入概率之間.

圖5.5-5.8展示了兩種信息水平下的最優社會福利. 其中, 從圖5.5, 圖5.6和圖5.8中可以看出,和Sfu(q?)分別隨著參數μ,θ,β 的增加而增加, 這是因為隨著服務時間, 啟動時間和維修時間的減少, 顧客被服務完成后獲得的回報會相應增加, 因此顧客更愿意進入系統, 社會福利隨之增加. 從圖5.7中可以看出,和Sfu(q?)隨著參數α的增加而減少, 這是因為隨著負顧客越來越多的到達, 服務臺故障的頻率增加, 顧客在系統中等待的成本增加, 因此顧客進入系統的意愿降低, 社會福利減少.

圖5.5 最優社會福利Sau(,)和Sfu(q?)關于μ的變化(λ=1,θ=2,α=0.2,β=1,R=5,C=3)

圖5.6 最優社會福利Sau(,)和Sfu(q?)關于θ的變化(λ=1,μ=2.5,α=0.2,β=1,R=5,C=3)

圖5.7 最優社會福利Sau(,)和Sfu(q?)關于α的變化(λ=1,μ=2.5,θ=2,β=1,R=5,C=3)

圖5.8 最優社會福利Sau(,)和Sfu(q?)關于β的變化(λ=1,μ=2.5,θ=2,α=0.2,R=5,C=3)

從圖5.5-5.8的整體上來看, 不管最優社會福利隨著參數如何變化,總是高于Sfu(q?), 這說明披露服務臺狀態的信息對社會管理者而言是有益的, 可以獲得更高的社會福利. 但是隨著參數的增加,和Sfu(q?)之間的差距越來越小, 逐漸趨于一致.