正、負顧客依狀態到達的M/M/m/(k-m)優先權排隊系統

王 玉， 呂勝利， 張 雷

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

0 引言

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

1 模型描述

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

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

2 模型分析

2.1 穩態下的平衡方程

1) 由穩態分析可得下列狀態轉移平衡方程：

j=0時，

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

j=k-m+1,…,k-1時，

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

當j=0時，

(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).

當j=1,2,…,k-1時，

(2)

當j=1,2,…,k-m時，

當j=k-m+1,…,k-1時，

2.2 平衡方程組求解

由系統中2類顧客的穩態分布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)可求得系統中第2類顧客的穩態分布,

(7)

系統中第2類顧客的平均隊長為

(8)

第2類顧客的溢出概率為

(9)

由于第1類顧客較第2類顧客具有強占優先權，且不受負顧客影響，故第1類顧客的穩態分布與只有一類顧客的經典的M/M/m/(k-m)排隊相同[8]. 第1類顧客的穩態分布為

(10)

(11)

第1類顧客的平均隊長

(12)

第1類顧客的溢出率

(13)

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

3 一個數值例子

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

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

表1 系統中第2類顧客的穩態分布Tab.1 Stationary distribution of class 2 in the system

4 結束語

利用優先權排隊可以為2類顧客提供不同的服務質量，考慮到現代通信中干擾信號的存在以及不同信號傳輸速率的變化，研究了依狀態到達的正、負顧客對排隊系統的影響.通過對系統中2類顧客平均隊長的分析，可以估計2類顧客在系統中的延誤時間；利用溢出概率可以改進服務臺的服務率和等待軌道的容量，從而使系統得到優化，滿足不同的需求，這對通信網絡的發展能起到很大的推進作用.

參考文獻：

[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] 陳佩叔，朱翼雋，耿響.具有強占優先權的不耐煩顧客的排隊模型[J].系統工程與電子技術，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] 孫榮恒，李建平.排隊論基礎[M].北京：科學出版社，2002：44-54.