正、負(fù)顧客依狀態(tài)到達(dá)的M/M/m/(k-m)優(yōu)先權(quán)排隊(duì)系統(tǒng)

王 玉， 呂勝利， 張 雷

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

0 引言

Gelenbe 在20世紀(jì)90年代初首次將負(fù)顧客引入排隊(duì)網(wǎng)絡(luò)[1-2]，排隊(duì)論的研究領(lǐng)域得到了進(jìn)一步的擴(kuò)展.優(yōu)先權(quán)排隊(duì)也是實(shí)際排隊(duì)系統(tǒng)中常見的現(xiàn)象，在通信網(wǎng)絡(luò)、電子對抗系統(tǒng)、計(jì)算機(jī)中斷系統(tǒng)、醫(yī)療救治系統(tǒng)中，優(yōu)先權(quán)排隊(duì)有著廣泛的應(yīng)用[3-4].隨后，出現(xiàn)了把多服務(wù)臺和帶有優(yōu)先權(quán)同時(shí)考慮的排隊(duì)系統(tǒng)[5-6]，也有學(xué)者對帶有優(yōu)先權(quán)和有限空間的排隊(duì)進(jìn)行了嘗試性探究[7].但是對在2類顧客中分別考慮強(qiáng)占優(yōu)先權(quán)和負(fù)顧客的情況研究較少，在有限等待空間的基礎(chǔ)上同時(shí)考慮到多服務(wù)臺和依狀態(tài)到達(dá)的研究則更少. 本文正是基于對通信網(wǎng)絡(luò)系統(tǒng)中語音信號的傳遞和處理較數(shù)據(jù)信號具有優(yōu)先權(quán)、信號傳輸速率和服務(wù)率的變化、外來信號和病毒對數(shù)據(jù)信號的干擾的實(shí)際應(yīng)用背景而建立的排隊(duì)模型，為系統(tǒng)優(yōu)化提供了理論依據(jù).

1 模型描述

系統(tǒng)中有m個(gè)服務(wù)臺，一個(gè)等待區(qū)域，等待空間為(k-m)(k?m).有2類顧客且均無等待時(shí)間限制.第1類顧客較第2類顧客具有強(qiáng)占優(yōu)先權(quán)，只有當(dāng)?shù)?類顧客數(shù)少于服務(wù)臺數(shù)時(shí)第2類顧客才能接受服務(wù)，即使第2類顧客正在接受服務(wù)，這時(shí)若有第1類顧客到達(dá)，則馬上停止對第2類顧客的服務(wù)而對剛到達(dá)的第1類顧客服務(wù)，被搶占的此第2類顧客回到原來等待軌道的隊(duì)首重新等待.服務(wù)規(guī)則是先到先服務(wù).在服務(wù)臺全忙且正在接受服務(wù)的全是第1類顧客的時(shí)候，若等待空間未滿則新到來的第1類顧客自動排到軌道的隊(duì)首等待接受服務(wù).系統(tǒng)中的第2類顧客會受到負(fù)顧客的干擾，負(fù)顧客的到達(dá)只對第2類顧客實(shí)行RCE抵消策略，即使第2類顧客正在接受服務(wù)，負(fù)顧客不接受服務(wù).

其中n表示系統(tǒng)中已有的顧客數(shù)，當(dāng)n=0時(shí)，第2類正顧客以參數(shù)λ2的泊松流到達(dá)，由此可知，隨著系統(tǒng)中顧客數(shù)目的增多，第2類正顧客的到達(dá)率逐漸降低而負(fù)顧客的到達(dá)率逐漸升高.

2 模型分析

2.1 穩(wěn)態(tài)下的平衡方程

1) 由穩(wěn)態(tài)分析可得下列狀態(tài)轉(zhuǎn)移平衡方程：

j=0時(shí)，

mμ1Pk，0=λ1Pk-1,0.

j=k-m+1,…,k-1時(shí)，

2) 把以上的平衡方程化為矩陣形式

當(dāng)j=0時(shí)，

(1)

其中,f0=λ1+λ2,0，ft=λ1+λ2,t+tμ1(t=1,2,…,m)，ft=λ1+λ2,t+mμ1(t=m+1,…,k-1)，fk=mμ1，gt=-tμ1(t=1,2,…,m)，gt=-mμ1(t=m+1,…,k).

當(dāng)j=1,2,…,k-1時(shí)，

(2)

當(dāng)j=1,2,…,k-m時(shí)，

當(dāng)j=k-m+1,…,k-1時(shí)，

2.2 平衡方程組求解

由系統(tǒng)中2類顧客的穩(wěn)態(tài)分布P·j的存在性及唯一性，由式(1)、(2)和克拉默法則可知，矩陣Aj(j=0,1,…,k-1)必為非奇異的.

(3)

(4)

易知P·k=P0，k，令E0=1，由式(3)、(4)遞推得

P·j=Ek-jP0，k.

(5)

(6)

將式(6)代入式(5)可求得系統(tǒng)中第2類顧客的穩(wěn)態(tài)分布,

(7)

系統(tǒng)中第2類顧客的平均隊(duì)長為

(8)

第2類顧客的溢出概率為

(9)

由于第1類顧客較第2類顧客具有強(qiáng)占優(yōu)先權(quán)，且不受負(fù)顧客影響，故第1類顧客的穩(wěn)態(tài)分布與只有一類顧客的經(jīng)典的M/M/m/(k-m)排隊(duì)相同[8]. 第1類顧客的穩(wěn)態(tài)分布為

(10)

(11)

第1類顧客的平均隊(duì)長

(12)

第1類顧客的溢出率

(13)

式(13)中P0由式(11)給出.

3 一個(gè)數(shù)值例子

利用參數(shù)m,k,λ1,λ2,μ1,μ2和式(3)～(13)用matlab編程.取m=3，k=8，λ1=λ2=0.7,μ1=μ2=0.3,可得系統(tǒng)中第2類顧客的穩(wěn)態(tài)分布如表1所示.

由式(8)和(9)得穩(wěn)態(tài)下第2類顧客的平均隊(duì)長和溢出率分別為E(L2)=3.795 9，r2=0.253 3.

表1 系統(tǒng)中第2類顧客的穩(wěn)態(tài)分布Tab.1 Stationary distribution of class 2 in the system

4 結(jié)束語

利用優(yōu)先權(quán)排隊(duì)可以為2類顧客提供不同的服務(wù)質(zhì)量，考慮到現(xiàn)代通信中干擾信號的存在以及不同信號傳輸速率的變化，研究了依狀態(tài)到達(dá)的正、負(fù)顧客對排隊(duì)系統(tǒng)的影響.通過對系統(tǒng)中2類顧客平均隊(duì)長的分析，可以估計(jì)2類顧客在系統(tǒng)中的延誤時(shí)間；利用溢出概率可以改進(jìn)服務(wù)臺的服務(wù)率和等待軌道的容量，從而使系統(tǒng)得到優(yōu)化，滿足不同的需求，這對通信網(wǎng)絡(luò)的發(fā)展能起到很大的推進(jìn)作用.

參考文獻(xiàn)：

[1] Gelenbe E，Glynn P，Sigman K.Queues with negative arrivals[J].J Appl Prob，1991，28(3)：245-250．

[2] Harrison P G，Pitel E.Sojourn times in single-server queues with negative customers[J].J Appl Prob，1993，30(4)：943-963.

[3] Miller D R.Computation of steady-state probabilities for priority queues[J].Operations Research，1981，29(6)：945-958.

[4] Steve D. An Eigen value approach to analyzing a finite source priority queuing model[J].Annals of Operations Research，2002，112(2)：139-152.

[5] 陳佩叔，朱翼雋，耿響.具有強(qiáng)占優(yōu)先權(quán)的不耐煩顧客的排隊(duì)模型[J].系統(tǒng)工程與電子技術(shù)，2008，30(6)：1069-1073.

[6] Demetres K，Nasredine T. An ME-based approximation for multi-server queues with preemptive priority[J]. European Journal of Operational Research，1994，77(3)：496-515.

[7] Indranil B，Raktim P.Average waiting time of customers in a priorityM/D/kqueue with finite buffers[J].Computers and operations research，2002，29(4)：327-339.

[8] 孫榮恒，李建平.排隊(duì)論基礎(chǔ)[M].北京：科學(xué)出版社，2002：44-54.