田龍妹,趙 寧,劉文奇

(昆明理工大學(xué) 理學(xué)院,云南 昆明 650500)

為了提高隨機(jī)服務(wù)系統(tǒng)中顧客的滿意度,本文研究可購(gòu)買優(yōu)先權(quán)的M/G/1排隊(duì)系統(tǒng)的顧客進(jìn)隊(duì)策略,即顧客到達(dá)系統(tǒng)后可以通過(guò)購(gòu)買優(yōu)先權(quán)獲得優(yōu)先服務(wù)的資格。

具有優(yōu)先權(quán)隊(duì)列的排隊(duì)系統(tǒng)在通信、計(jì)算機(jī)網(wǎng)絡(luò)以及各大主題游樂園被廣泛應(yīng)用[1-5],自20世紀(jì)60年代起得到很多學(xué)者關(guān)注。Hassin[6]研究了具有優(yōu)先權(quán)的M/M/1排隊(duì)系統(tǒng),得到在完全可見情形下顧客選擇進(jìn)入優(yōu)先權(quán)隊(duì)列的純閾值策略和混合閾值策略;Lillo[7]研究了具有優(yōu)先權(quán)的M/G/1排隊(duì)系統(tǒng)的優(yōu)化運(yùn)行策略,證明了平穩(wěn)最優(yōu)策略是一個(gè)雙閾值控制策略;黃文業(yè)等[8]研究了非搶占的具有優(yōu)先權(quán)的M/G/1排隊(duì)系統(tǒng),得出系統(tǒng)穩(wěn)定條件下優(yōu)先權(quán)隊(duì)列和普通隊(duì)列的各種指標(biāo)的理論結(jié)果。

具有優(yōu)先權(quán)的重申隊(duì)列排隊(duì)系統(tǒng)是一類特殊的有優(yōu)先權(quán)的排隊(duì)系統(tǒng),顧客到達(dá)系統(tǒng)后如果發(fā)現(xiàn)服務(wù)器繁忙,則進(jìn)入重申隊(duì)列并任意排序,重申隊(duì)列的顧客在經(jīng)歷某個(gè)隨機(jī)時(shí)間后重新訪問(wèn)服務(wù)器。通常首次訪問(wèn)系統(tǒng)的顧客被賦予優(yōu)先權(quán),相對(duì)重申隊(duì)列的顧客優(yōu)先獲得服務(wù)[9]。Choi[9]研究了具有重申隊(duì)列系統(tǒng)以及優(yōu)先權(quán)的M/G/1排隊(duì)系統(tǒng),得到優(yōu)先權(quán)隊(duì)列和重申隊(duì)列中請(qǐng)求的聯(lián)合母函數(shù)。Iravani[4]研究了帶優(yōu)先權(quán)且顧客沒有耐心的排隊(duì)問(wèn)題,得到平穩(wěn)狀態(tài)下系統(tǒng)的性能指標(biāo)。Shan[10]研究了具有搶占優(yōu)先權(quán)和重申隊(duì)列的M/G/1排隊(duì)系統(tǒng),得到優(yōu)先權(quán)隊(duì)列和重申隊(duì)列的平穩(wěn)概率分布和一些性能指標(biāo)。

近年來(lái),排隊(duì)系統(tǒng)在很多領(lǐng)域得到廣泛應(yīng)用。王小農(nóng)等[11]研究了自動(dòng)化立體車庫(kù)中的M/G/N排隊(duì)系統(tǒng),分析了車位分配時(shí)顧客排隊(duì)隊(duì)長(zhǎng)及出入車庫(kù)的效率等問(wèn)題;曹雷等[12]基于排隊(duì)系統(tǒng)相關(guān)理論,研究了導(dǎo)彈防御系統(tǒng)的效能問(wèn)題,得出有效提高導(dǎo)彈防御系統(tǒng)效能的措施。Xu等[13]研究了完全不可見情形下具有搶占優(yōu)先權(quán)的M/G/1排隊(duì)系統(tǒng),得到了納什均衡策略和社會(huì)最優(yōu)策略。

現(xiàn)實(shí)中有的服務(wù)被中斷后能夠比較容易啟動(dòng)后續(xù)的服務(wù),例如清洗汽車的服務(wù),這類服務(wù)系統(tǒng)可以采用搶占優(yōu)先權(quán)的服務(wù)規(guī)則。然而有的服務(wù)中斷成本較高,例如芯片加工過(guò)程涉及很多化學(xué)反應(yīng),如果加工過(guò)程被中斷,可能導(dǎo)致元件性能下降,甚至報(bào)廢,為了避免較大的損失,這類服務(wù)一般采取非搶占的服務(wù)規(guī)則;另外,在大型娛樂公園,例如過(guò)山車、海盜船,如果娛樂過(guò)程中被中斷,會(huì)引起顧客恐懼和不適,這類服務(wù)一般也采取非搶占的服務(wù)規(guī)則。除此之外,在現(xiàn)實(shí)生活存在很多非搶占的服務(wù)。基于此,本文研究非搶占優(yōu)先權(quán)的M/G/1排隊(duì)系統(tǒng),通過(guò)顧客的個(gè)體收益函數(shù)分析這類排隊(duì)系統(tǒng)的進(jìn)隊(duì)策略,提高系統(tǒng)中顧客的滿意度。

本文第1節(jié)介紹可購(gòu)買優(yōu)先權(quán)的M/G/1排隊(duì)系統(tǒng)。第2節(jié)對(duì)完全可見情形進(jìn)行描述,并從個(gè)體平均收益的角度給出優(yōu)先權(quán)隊(duì)列的閾值。第3節(jié)對(duì)完全不可見情形進(jìn)行描述,并給出進(jìn)入優(yōu)先權(quán)隊(duì)列的最優(yōu)概率。第4節(jié)通過(guò)數(shù)值實(shí)驗(yàn)分析了完全可見情形下優(yōu)先權(quán)隊(duì)列的閾值與購(gòu)買優(yōu)先權(quán)價(jià)格的關(guān)系,以及完全不可見情形下進(jìn)入優(yōu)先權(quán)隊(duì)列的策略與購(gòu)買優(yōu)先權(quán)價(jià)格的關(guān)系。第5節(jié)為結(jié)論。

1 模型描述

2 完全可見情形

在完全可見情形下,到達(dá)顧客可以觀察到系統(tǒng)中優(yōu)先權(quán)隊(duì)列和普通隊(duì)列的顧客數(shù),以及服務(wù)器中的客戶類型。當(dāng)服務(wù)器空閑時(shí),到達(dá)顧客最優(yōu)選擇進(jìn)入普通隊(duì)列;當(dāng)系統(tǒng)忙碌并且普通隊(duì)列非空時(shí),到達(dá)顧客根據(jù)系統(tǒng)中顧客的隊(duì)長(zhǎng)選擇是否進(jìn)入優(yōu)先權(quán)隊(duì)列。進(jìn)入優(yōu)先權(quán)隊(duì)列需要額外支付ξ的費(fèi)用。

定理1在完全可見的具有非搶占優(yōu)先權(quán)的M/G/1排隊(duì)系統(tǒng)中,假設(shè)某顧客到達(dá)系統(tǒng)時(shí)觀察到系統(tǒng)的狀態(tài)為(n1,n2,1),該顧客在系統(tǒng)中單位時(shí)間的逗留成本為C,則存在閾值

(1)若n1≤K*,則顧客進(jìn)入優(yōu)先權(quán)隊(duì)列的平均收益非負(fù);

(2)若n1>K*,則顧客進(jìn)入優(yōu)先權(quán)隊(duì)列的平均收益小于零。

證明假設(shè)顧客到達(dá)時(shí)發(fā)現(xiàn)系統(tǒng)狀態(tài)為(n1,n2,1)時(shí),該顧客選擇進(jìn)入優(yōu)先權(quán)隊(duì)列的平均收益函數(shù)為

(1)

令G(n1,n2,1)≥0,得

3 完全不可見情形

在完全不可見情形下,顧客到達(dá)系統(tǒng)后不能觀察到系統(tǒng)中優(yōu)先權(quán)隊(duì)列和普通隊(duì)列中的顧客數(shù),也觀察不到服務(wù)器服務(wù)的顧客類型。假設(shè)到達(dá)顧客隨機(jī)選擇進(jìn)入優(yōu)先權(quán)隊(duì)列和普通隊(duì)列,其概率分別為q和1-q。該系統(tǒng)的繁忙程度為ρ=λb1,假定系統(tǒng)處于穩(wěn)定狀態(tài),即ρ<1。令系統(tǒng)中第i類顧客數(shù)為Ni,平均隊(duì)長(zhǎng)為E(Ni),平均等待時(shí)間為E(Wi),i=1,2。

引理1[14]具有非搶占優(yōu)先權(quán)的M/G/1排隊(duì)系統(tǒng)中,在不可見情形下的優(yōu)先權(quán)顧客和普通顧客的平均等待時(shí)間分別為

(2)

由Little法則知E(N1)=λqE(W1),代入式(2)得具有優(yōu)先權(quán)顧客的平均等待時(shí)間為

(3)

令N=N1+N2,由均值法得系統(tǒng)中任意顧客的平均等待時(shí)間為

(4)

同理,由Little法則得E(N)=λE(W),代入式(4)得

(5)

由于

E(W)=qE(W1)+(1-q)E(W2)

(6)

將式(3)、(5)代入式(6)得

定理2具有非搶占優(yōu)先權(quán)的M/G/1排隊(duì)系統(tǒng)中,假設(shè)到達(dá)顧客的單位時(shí)間的逗留成本為C,在不可見情形下該顧客的最優(yōu)進(jìn)隊(duì)策略為:

證明在不可見情形下,若顧客選擇進(jìn)入優(yōu)先權(quán)隊(duì)列的平均等待時(shí)間花費(fèi)為J1=CE(W1),顧客選擇進(jìn)入普通隊(duì)列的平均等待時(shí)間花費(fèi)為J2=CE(W2)。

如果選擇進(jìn)入優(yōu)先權(quán)隊(duì)列,則該顧客在系統(tǒng)中的平均等待的費(fèi)用減少量為

f(q)=J2-J1=C(E(W2)-E(W1))=

(7)

由于函數(shù)f(q)關(guān)于q單調(diào)遞增(q∈[0,1]),所以顧客具有擁擠偏好的情形:

4 數(shù)值實(shí)驗(yàn)

第2節(jié)和第3節(jié)從理論上分析了具有非搶占優(yōu)先權(quán)的M/G/1排隊(duì)系統(tǒng)在完全可見和完全不可見情形下顧客的進(jìn)隊(duì)策略,本節(jié)分別假設(shè)服務(wù)時(shí)間服從指數(shù)分布、伽馬分布及常數(shù),對(duì)理論結(jié)果進(jìn)行數(shù)值驗(yàn)證。

4.1 完全可見情形的數(shù)值計(jì)算

考慮完全可見情形下的M/G/1排隊(duì)系統(tǒng),分別假設(shè)服務(wù)時(shí)間服從指數(shù)分布X～Exp(3/4)、伽馬分布X～Gamma(1/2,3/8)及常數(shù)X=4/3。3種服務(wù)時(shí)間分布下,優(yōu)先權(quán)隊(duì)列的閾值K*與購(gòu)買優(yōu)先權(quán)價(jià)格ξ的關(guān)系如圖1所示。

4.2 完全不可見情形的數(shù)值計(jì)算

由定理2知,在完全不可見情形下顧客的最優(yōu)進(jìn)隊(duì)策略與f(0)、f(1)有關(guān)。分別假設(shè)服務(wù)時(shí)間服從指數(shù)分布X～Exp(3/4)、伽馬分布X～Gamma(1/2,3/8)及常數(shù)X=4/3,令C=1。3種服務(wù)時(shí)間分布下,f(0)、f(1)與系統(tǒng)繁忙程度ρ的關(guān)系分別如圖2所示。

下面通過(guò)數(shù)值計(jì)算說(shuō)明3種服務(wù)時(shí)間分布下的最優(yōu)進(jìn)隊(duì)策略,表1比較了ρ=0.8時(shí)顧客的平均剩余服務(wù)時(shí)間、平均等待時(shí)間的費(fèi)用減少量f(0)、f(1)的值。

表1 ρ=0.8時(shí)3種服務(wù)時(shí)間分布下進(jìn)隊(duì)策略的數(shù)值分析

由表1可知:

(1)若X=4/3,則有:

(a)當(dāng)0≤ξ≤32/15時(shí),q=1,顧客進(jìn)入優(yōu)先權(quán)隊(duì)列是最優(yōu)策略,也是占優(yōu)策略;

(b)當(dāng)ξ≥32/3時(shí),q=0,顧客進(jìn)入普通隊(duì)列是最優(yōu)策略,也是占優(yōu)策略;

(2)若X～Exp(3/4),則有:

(a)當(dāng)0≤ξ≤64/15時(shí),q=1,顧客進(jìn)入優(yōu)先權(quán)隊(duì)列是最優(yōu)策略,也是占優(yōu)策略;

(b)當(dāng)ξ≥64/3時(shí),q=0,顧客進(jìn)入普通隊(duì)列是最優(yōu)策略,也是占優(yōu)策略;

(3)若X～Gamma(1/2,3/8),則有:

(a)當(dāng)0≤ξ≤32/5時(shí),q=1,顧客進(jìn)入優(yōu)先權(quán)隊(duì)列是最優(yōu)策略,也是占優(yōu)策略;

(b)當(dāng)ξ≥32時(shí),q=0,顧客進(jìn)入普通隊(duì)列是最優(yōu)策略,也是占優(yōu)策略;

5 結(jié)束語(yǔ)

本文針對(duì)具有非搶占優(yōu)先權(quán)的M/G/1排隊(duì)系統(tǒng),分析了完全可見和完全不可見兩種情形下顧客購(gòu)買優(yōu)先權(quán)的策略,得出完全可見情形下顧客進(jìn)入優(yōu)先權(quán)隊(duì)列的閾值,完全不可見情形下進(jìn)入優(yōu)先權(quán)隊(duì)列的最優(yōu)進(jìn)隊(duì)策略,并通過(guò)計(jì)算服務(wù)時(shí)間服從指數(shù)分布、伽馬分布和常數(shù)3種情況下顧客的最優(yōu)進(jìn)隊(duì)策略,驗(yàn)證了完全可見情形下優(yōu)先權(quán)隊(duì)列的閾值與購(gòu)買優(yōu)先權(quán)價(jià)格呈現(xiàn)線性遞減的關(guān)系,以及在不可見情形下購(gòu)買優(yōu)先權(quán)的價(jià)格與進(jìn)入優(yōu)先權(quán)隊(duì)列的關(guān)系。在具有非搶占優(yōu)先權(quán)的隨機(jī)服務(wù)系統(tǒng)中,顧客基于上述討論的進(jìn)隊(duì)策略進(jìn)隊(duì)可以有效提高自身獲益。

關(guān)于具有優(yōu)先權(quán)的M/G/1排隊(duì)系統(tǒng)的博弈問(wèn)題,還可推廣到多服務(wù)器以及節(jié)能系統(tǒng),以及幾乎可見和幾乎不可見情形下的博弈問(wèn)題,未來(lái)可以對(duì)這些問(wèn)題進(jìn)行研究。