田龍妹,趙 寧,劉文奇

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

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

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

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

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

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

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

1 模型描述

2 完全可見情形

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

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

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

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

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

(1)

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

3 完全不可見情形

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

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

(2)

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

(3)

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

(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排隊系統(tǒng)中,假設(shè)到達顧客的單位時間的逗留成本為C,在不可見情形下該顧客的最優(yōu)進隊策略為:

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

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

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

(7)

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

4 數(shù)值實驗

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

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

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

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

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

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

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

由表1可知:

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

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

(b)當ξ≥32/3時,q=0,顧客進入普通隊列是最優(yōu)策略,也是占優(yōu)策略;

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

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

(b)當ξ≥64/3時,q=0,顧客進入普通隊列是最優(yōu)策略,也是占優(yōu)策略;

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

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

(b)當ξ≥32時,q=0,顧客進入普通隊列是最優(yōu)策略,也是占優(yōu)策略;

5 結(jié)束語

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

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