休假機(jī)制超市模型的報(bào)酬過(guò)程

摘要：超市模型已經(jīng)成為解決大型網(wǎng)絡(luò)資源管理問(wèn)題的一個(gè)重要的數(shù)學(xué)工具，它具有操作簡(jiǎn)單、運(yùn)行方便的特點(diǎn)，能對(duì)大型的網(wǎng)絡(luò)資源進(jìn)行實(shí)時(shí)控制。超市模型已經(jīng)應(yīng)用到交通網(wǎng)絡(luò)、信息管理等領(lǐng)域，進(jìn)而成為大型網(wǎng)絡(luò)資源管理領(lǐng)域的一個(gè)重要的課題。文章對(duì)一般的休假機(jī)制超市模型進(jìn)行研究，然后建立了休假機(jī)制超市模型的報(bào)酬函數(shù)，提出了這個(gè)休假機(jī)制超市模型的性能優(yōu)化準(zhǔn)則。文章對(duì)休假機(jī)制超市模型的研究提供了理論依據(jù)。

關(guān)鍵詞：超市模型；實(shí)時(shí)控制；報(bào)酬函數(shù)；性能優(yōu)化

一、引言

由于隨機(jī)負(fù)載平衡策略具有操作簡(jiǎn)單、運(yùn)行方便等優(yōu)點(diǎn)成為解決大型計(jì)算機(jī)網(wǎng)絡(luò)資源管理的一個(gè)有效的研究方法，它已經(jīng)應(yīng)用到交通網(wǎng)絡(luò)、信息管理等領(lǐng)域，并使得這些重要的領(lǐng)域有了性能上的改進(jìn)，降低了資源的閑置時(shí)間，提高了資源的利用率。由于大型網(wǎng)絡(luò)資源管理系統(tǒng)的服務(wù)平臺(tái)之間的相互聯(lián)系、相互依賴(lài)，使得超市模型所對(duì)應(yīng)的大型排隊(duì)網(wǎng)絡(luò)變得更加復(fù)雜。目前，馬爾可夫與排隊(duì)論已經(jīng)用來(lái)研究隨機(jī)負(fù)載平衡策略的相關(guān)問(wèn)題，并引起了國(guó)際學(xué)者的注意，使得隨機(jī)負(fù)載平衡策略成為這個(gè)領(lǐng)域的熱點(diǎn)課題。

其中代表性的研究成果包括：代桂榮等人利用尾巴方程和密度相依跳躍馬爾可夫過(guò)程，建立了系統(tǒng)的無(wú)窮維非線(xiàn)性表示。王瑞鋒提出了一種基于超市模型的網(wǎng)格資源管理分配方法，減少了網(wǎng)格管理開(kāi)銷(xiāo)，高效地分配了稀缺資源。沈薇提出了基于超市模型的文件復(fù)制管理策略，提高了整體系統(tǒng)效率。Li提供了一些重要排隊(duì)過(guò)程的尾部分布的計(jì)算方法。關(guān)于馬爾可夫過(guò)程的研究成果有：李祺對(duì)已分類(lèi)的關(guān)鍵業(yè)務(wù)流量通過(guò)改進(jìn)的基于令牌桶的流量整形算法來(lái)保證其服務(wù)質(zhì)量。葛愿研究了僅存在前向網(wǎng)絡(luò)短時(shí)延的網(wǎng)絡(luò)化控制系統(tǒng)的建模與控制問(wèn)題。Janssen研究了簡(jiǎn)單離散時(shí)間的超市模型的報(bào)酬過(guò)程和決策過(guò)程，并對(duì)馬氏過(guò)程研究的幾個(gè)方法進(jìn)行了比較。

本文的學(xué)術(shù)貢獻(xiàn)有兩個(gè)方面：其一、超市模型是目前國(guó)際上的熱點(diǎn)課題，由于服務(wù)平臺(tái)之間的相互聯(lián)系、相互依賴(lài)使得超市模型的研究變得比較復(fù)雜。休假機(jī)制的超市模型已經(jīng)應(yīng)用于許多類(lèi)的問(wèn)題，包括排隊(duì)系統(tǒng)、生產(chǎn)流程、庫(kù)存控制和傳染病控制等，因此休假機(jī)制的超市模型更接近于實(shí)際系統(tǒng)；其二、針對(duì)休假機(jī)制的超市模型，本文建立了它的馬氏報(bào)酬過(guò)程，研究了報(bào)酬過(guò)程的單調(diào)性，并對(duì)報(bào)酬函數(shù)進(jìn)行了數(shù)值算例。

二、超市模型描述

休假機(jī)制的超市模型進(jìn)行描述是：系統(tǒng)中的N個(gè)服務(wù)臺(tái)都是相同的，并且是獨(dú)立同分布的，每個(gè)服務(wù)平臺(tái)的服務(wù)率都為μ；每個(gè)顧客的到達(dá)過(guò)程都是泊松過(guò)程，到達(dá)率為λ。顧客到達(dá)系統(tǒng)會(huì)隨機(jī)的選擇其中的d個(gè)服務(wù)臺(tái)，然后進(jìn)入這d個(gè)服務(wù)臺(tái)前隊(duì)列最短的一個(gè)隊(duì)伍接受服務(wù)或者排隊(duì)等待，直到接受完服務(wù)才離開(kāi)在每個(gè)服務(wù)臺(tái)采取的服務(wù)機(jī)制都是先來(lái)先服務(wù)（FCFS）；系統(tǒng)由于服務(wù)臺(tái)機(jī)器的損壞、工作人員或者器械的休息等原因使得該服務(wù)臺(tái)不得不停止提供服務(wù)，但是一段時(shí)間之后服務(wù)臺(tái)會(huì)恢復(fù)工作，因此也可稱(chēng)這種休假制度的超市模型為可修復(fù)超市模型，此時(shí)假設(shè)該服務(wù)臺(tái)前的顧客仍在此服務(wù)臺(tái)前排隊(duì)等待，但是到達(dá)的顧客不會(huì)再進(jìn)入此隊(duì)列。這個(gè)超市模型的物理結(jié)構(gòu)見(jiàn)圖1。

三、休假機(jī)制超市模型的報(bào)酬過(guò)程

在這一節(jié)中，將休假機(jī)制的超市模型轉(zhuǎn)變?yōu)橐粋€(gè)馬氏過(guò)程，然后建立它的報(bào)酬函數(shù)。知道一般的超市模型的報(bào)酬函數(shù)為：

V（x）=r（x）+p（x，y）V（y），（1）

其中x=（x1，x2，…，xN）表示系統(tǒng)中每個(gè)服務(wù)臺(tái)前顧客的長(zhǎng)度，并且假設(shè)向量x滿(mǎn)足：

x1≤x2≤…≤xN；（2）

V（x）表示系統(tǒng)處于狀態(tài)x時(shí)的報(bào)酬值；

r（x）是指系統(tǒng)處于狀態(tài)x時(shí)的初始值；

p（x，y）是指從狀態(tài)x轉(zhuǎn)移到y(tǒng)的概率。

為了研究休假超市模型的馬氏報(bào)酬過(guò)程，需要考慮一下三種情況：

1.顧客的到達(dá)

在這個(gè)超市模型中，每個(gè)到達(dá)的顧客都會(huì)從這N個(gè)服務(wù)臺(tái)中隨機(jī)的選擇其中的d個(gè)，然后進(jìn)入這d個(gè)服務(wù)臺(tái)前隊(duì)列最短的一個(gè)隊(duì)伍接受服務(wù)或者排隊(duì)等待，如果有兩個(gè)或者兩個(gè)以上的對(duì)端隊(duì)列，那么這個(gè)顧客就會(huì)隨機(jī)的選擇一個(gè)進(jìn)入。Janssen已經(jīng)給出顧客進(jìn)入一般的超市模型中的第i個(gè)服務(wù)臺(tái)的概率為

假設(shè)在某一時(shí)刻，服務(wù)臺(tái)停止提供服務(wù)的概率為q，那么在這個(gè)休假機(jī)制的超市模型中，顧客進(jìn)入第i個(gè)服務(wù)臺(tái)的概率為

那么顧客進(jìn)入第i個(gè)服務(wù)臺(tái)的到達(dá)率為λK（N，i，d），其中i=1，2，...，N。

2. 顧客的離去

在這個(gè)模型中第i個(gè)服務(wù)臺(tái)中，顧客接受完服務(wù)后離開(kāi)有兩個(gè)前提（1）此服務(wù)臺(tái)正在提供服務(wù)；（2）此服務(wù)臺(tái)前的隊(duì)列長(zhǎng)度不為0，用Π{xi>0}來(lái)表示第i個(gè)服務(wù)臺(tái)前顧客不為0的概率，即

因此得到系統(tǒng)中有顧客離開(kāi)的概率為μ（1-q）Π{xi>0}。

3. 既沒(méi)有顧客的到達(dá)也沒(méi)有顧客的離去

顯然知道即沒(méi)有顧客的到達(dá)也沒(méi)有顧客的離去的概率為

為了使系統(tǒng)服務(wù)臺(tái)上的負(fù)荷比較均勻，應(yīng)該盡量的使最長(zhǎng)隊(duì)列的長(zhǎng)度最小化，因此假設(shè)定義r（x）=xM。當(dāng)?shù)趇個(gè)服務(wù)臺(tái)有顧客進(jìn)入時(shí)，用x+ei來(lái)表示，其中ei是指第i個(gè)元素為1，其它都為0的列向量；當(dāng)?shù)趇個(gè)服務(wù)臺(tái)有顧客離開(kāi)時(shí)，用x-ei來(lái)表示。由于有顧客進(jìn)入或者離開(kāi)時(shí)，可能會(huì)使得新的狀態(tài)x+ei或者x-ei不再滿(mǎn)足條件（2），因此引進(jìn)一個(gè)升序函數(shù)σ（x），升序函數(shù)對(duì)新的狀態(tài)x+ei或者x-ei進(jìn)行重新排列，以滿(mǎn)足條件（2）。因此根據(jù)報(bào)酬函數(shù)（1）得到這個(gè)休假機(jī)制超市模型的報(bào)酬函數(shù)為

V（x）=xM+λK（N，i，d）V（σ（x+ei））+μ（1-q）Π{xi>0}V（σ（x-ei））+{1-[λK（N，i，d]+μ（1-q）Π

{xi>0}]}V（x）（7）

四、數(shù)值算例

本節(jié)將對(duì)休假機(jī)制超市模型的報(bào)酬函數(shù)進(jìn)行數(shù)值算例，進(jìn)而研究此模型的報(bào)酬函數(shù)性質(zhì)。此時(shí)將取其中的一組數(shù)據(jù)，假設(shè)此系統(tǒng)要求總?cè)藬?shù)不超過(guò)10個(gè)人。通過(guò)Matlab得出不同狀態(tài)下系統(tǒng)中顧客總數(shù)圖1與圖2對(duì)應(yīng)的報(bào)酬函數(shù)圖。

通過(guò)對(duì)上面兩個(gè)圖的比較，很容易看出：1. 顧客總數(shù)和報(bào)酬函數(shù)都呈現(xiàn)出周期性的遞增性質(zhì)；2. 報(bào)酬函數(shù)值會(huì)隨著系統(tǒng)中顧客總數(shù)的增加而增加。因此可知，休假機(jī)制超市模型報(bào)酬函數(shù)是x的單調(diào)遞增函數(shù)。

五、結(jié)語(yǔ)

超市模型已經(jīng)應(yīng)用到交通網(wǎng)絡(luò)、信息管理、供應(yīng)鏈管理等重要領(lǐng)域，由于超市模型的操作簡(jiǎn)單、運(yùn)行方便等優(yōu)點(diǎn)，并且能夠?qū)Υ笮偷木W(wǎng)絡(luò)資源進(jìn)行實(shí)時(shí)控制，因此超市模型已經(jīng)引起了國(guó)際學(xué)者的關(guān)注，成為了大型網(wǎng)絡(luò)資源管理領(lǐng)域的一個(gè)重要的課題。本文是對(duì)具有休假機(jī)制的超市模型進(jìn)行研究，這個(gè)休假可能是由于機(jī)器的損壞、工作人員的離開(kāi)等原因造成的，這使得休假機(jī)制的超市模型更加接近實(shí)際情況，也就使得研究變得更加有意義。本文給出了休假機(jī)制超市模型的報(bào)酬函數(shù)，并進(jìn)行了一些數(shù)值算例，發(fā)現(xiàn)報(bào)酬函數(shù)值是隨著系統(tǒng)中顧客總數(shù)的增加而變大，并給出了兩個(gè)直觀圖。

參考文獻(xiàn)：

[1]代桂蓉.大型超市模型的動(dòng)態(tài)策略及其在物流系統(tǒng)中的應(yīng)用研究[D].燕山大學(xué)，2013.

[2]王瑞鋒，劉方愛(ài).基于超市模型的網(wǎng)格資源分配方法研究[J].計(jì)算機(jī)應(yīng)用研究，2007（10）.

[3]沈薇，周宇，劉方愛(ài).基于超市模型的文件復(fù)制策略[J].計(jì)算機(jī)應(yīng)用研究，2008 （04）.

[4]李泉林，杜曄，王盟，代桂蓉.超市模型的實(shí)時(shí)動(dòng)態(tài)控制及其數(shù)值分析[J].應(yīng)用概率統(tǒng)計(jì)，2014（30）.

[5]李祺，基于隱馬爾可夫模型的網(wǎng)絡(luò)流量分類(lèi)和控制技術(shù)研究[D].重慶大學(xué)，2012.

[6]葛愿，基于隱馬爾可夫模型的網(wǎng)絡(luò)化控制系統(tǒng)建模與控制[D].中國(guó)科學(xué)技術(shù)大學(xué)，2011.

（作者單位：丁園園、黃亞靜，燕山大學(xué)經(jīng)濟(jì)管理學(xué)院；張偉，西北大學(xué)）