帶有負(fù)顧客和啟動時間的排隊系統(tǒng)最優(yōu)策略分析

何柳青,田瑞玲

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

1.引言

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

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

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

2.模型描述

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

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

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

顧客到達(dá)系統(tǒng)時,會根據(jù)其了解的有關(guān)系統(tǒng)狀態(tài)的信息來決定進(jìn)隊的策略.本文考慮了不可視的兩種情形: 1)幾乎不可視: 到達(dá)顧客被告知服務(wù)臺的狀態(tài)信息;2)完全不可視: 到達(dá)顧客對系統(tǒng)的狀態(tài)一無所知.

3.幾乎不可視情形

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

定義pn,i為系統(tǒng)的穩(wěn)態(tài)概率,相應(yīng)的母函數(shù)定義如下

其中|z|≤1.

定理3.1在帶有負(fù)顧客和啟動時間的幾乎不可視M/M/1排隊系統(tǒng)中,假設(shè)<1,服務(wù)臺狀態(tài)i=0,1,2的穩(wěn)態(tài)概率分別如下

證系統(tǒng)的平衡方程如下

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

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

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

觀察式(3.1),(3.2),(3.3)和(3.7),容易得出此排隊系統(tǒng)的穩(wěn)態(tài)條件為<1.

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

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

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

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

由式(3.22),可得

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

定理3.3對于帶有負(fù)顧客和啟動時間的幾乎不可視M/M/1排隊系統(tǒng),一名標(biāo)記顧客到達(dá)時發(fā)現(xiàn)服務(wù)臺狀態(tài)為i(i=1,2)并選擇進(jìn)入系統(tǒng)的平均逗留時間分別如下

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

證根據(jù)線性“收益-成本”結(jié)構(gòu),可得服務(wù)臺處于啟動期時的平均剩余效用

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

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

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

U1(q1,q2)是關(guān)于q2和q1的函數(shù),上面已經(jīng)給出了的結(jié)果,因此它現(xiàn)在只與q1有關(guān),求U1(q1)關(guān)于q1的一階導(dǎo),可得

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

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

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

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

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

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

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

步2 借助適應(yīng)度函數(shù)對每個個體進(jìn)行評價,通過輪盤法選擇優(yōu)秀個體參與遺傳操作,淘汰劣質(zhì)個體;

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

步4 將后代中表現(xiàn)最好的個體作為遺傳算法的結(jié)果.

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

借助遺傳算法尋得最優(yōu)解后,將在文章第5部分進(jìn)一步做最優(yōu)解關(guān)于參數(shù)的敏感性分析.

4.完全不可視情形

本節(jié)研究完全不可視情形下顧客的均衡進(jìn)入概率.在完全不可視情形下,到達(dá)顧客既不知道服務(wù)臺的狀態(tài)信息,也不知道系統(tǒng)的隊長信息,假設(shè)他們都以概率q進(jìn)入,那么實際到達(dá)率為λq.狀態(tài)轉(zhuǎn)移圖如圖4.1所示.

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

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

定理4.2對于帶有負(fù)顧客和啟動時間的完全不可視M/M/1排隊系統(tǒng),一名標(biāo)記顧客到達(dá)并選擇進(jìn)入系統(tǒng)的平均逗留時間為

證根據(jù)PASTA性質(zhì),系統(tǒng)中顧客的有效到達(dá)率為

系統(tǒng)中的平均顧客數(shù)為

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

定理4.3對于帶有負(fù)顧客和啟動時間的完全不可視M/M/1排隊系統(tǒng),均衡進(jìn)入概率qe如下

證根據(jù)線性“收益-成本”結(jié)構(gòu),可得顧客的平均剩余效用U(q),表達(dá)式如下

求式(4.12)關(guān)于q的一階導(dǎo),可得

基于函數(shù)的單調(diào)性,分以下三種情形來討論

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

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

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

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

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

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

5.數(shù)值分析

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

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

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

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

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

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

觀察圖5.1-5.4, 從整體上來看, 不論最優(yōu)進(jìn)入概率關(guān)于參數(shù)的變化是何種走勢, q?大致總是夾在和之間. 也就是說, 在完全不可視的排隊系統(tǒng)中, 到達(dá)顧客進(jìn)入系統(tǒng)的概率介于幾乎不可視排隊系統(tǒng)的兩個進(jìn)入概率之間.

觀察圖5.1-5.4,從整體上來看,不論最優(yōu)進(jìn)入概率關(guān)于參數(shù)的變化是何種走勢,q?大致總是夾在和之間.也就是說,在完全不可視的排隊系統(tǒng)中,到達(dá)顧客進(jìn)入系統(tǒng)的概率介于幾乎不可視排隊系統(tǒng)的兩個進(jìn)入概率之間.

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

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

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

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

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

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