離散時間SM[K]/PH[K]/1/FCFS排隊系統的年齡過程改進分析

高卓,徐德舉

1.華南農業大學珠江學院,廣東廣州510900

2.首都師范大學數學科學學院,北京100048

離散時間SM[K]/PH[K]/1/FCFS排隊系統的年齡過程改進分析

高卓1,徐德舉2

1.華南農業大學珠江學院,廣東廣州510900

2.首都師范大學數學科學學院,北京100048

基于一個離散時間的排隊系統：顧客有著多種類型，成批到達，到達過程是一個半馬爾可夫過程，按照先來先服務的準則，并且每一個顧客的服務時間服從各自的PH分布。對這個離散時間SM[K]/PH[K]/1/FCFS排隊系統年齡過程進行了詳細分析，引進一些附加變量構造一個關于年齡過程的馬爾可夫鏈，從而計算出年齡過程的轉移矩陣。

排隊系統;年齡過程;馬爾可夫鏈;轉移矩陣

現代通訊網絡需要處理各類數據，這些數據在容量等方面是各不相同的。現代供應鏈的設計也是要滿足顧客的不同需要，這相當于在排隊系統中顧客是有類型的。在現實生活中我們還經常遇到成批到達的現象，例如在生產制造系統中，需要加工的部件成批到達加工車間；再如在庫存系統中，顧客的需求按照復合泊松過程到達系統。以上這些現象都可以描述為成批到達的排隊系統。由于這些隨機系統的設計和功能分析的需要，我們將研究一類有著多種類型顧客的離散時間的排隊模型，其顧客是批到達。

文獻[1]介紹了離散時間SM[K]/PH[K]/1/FCFS排隊系統，該系統有k個類型的顧客（其中k為正整數），所有的顧客都加入一個隊列，遵守“先到先服務”的規則。顧客的到達過程是一個離散的半馬爾可夫過程，每個顧客的服務時間服從離散的PH分布，他們相互獨立且與其到達過程相互獨立[1]。文獻[4]主要討論了離散時間狀態下的批量到達排隊系統，推廣了經典的離散時間排隊模型，考慮單個服務臺的情形，假設顧客到達服從幾何分布、每批到達的顧客數服從一般的離散分布、顧客的服務時間也服從幾何分布，使用嵌入馬爾可夫鏈的方法，分析得到了該隨機排隊系統的隊長、等待隊長、等待時間以及忙期等關鍵指標的母函數[4]。在文獻[3]中到達過程是馬爾可夫過程，這是與我們研究的排隊系統最大的不同之處。我們考慮的是一個離散時間的更普遍的排隊模型，構造廣義的年齡過程，這個過程是沒有水平0這個邊界的。在一個服務臺的情形下我們可以從這個年齡過程的平穩分布得到等待時間和逗留時間的分布。在文獻[2]中引進一個由顧客批的年齡過程構造的GI/M/1型的馬爾可夫鏈，于是，正在服務的顧客批的年齡、系統總的工作量、等待時間、不同批不同類型的顧客的逗留時間等這些變量的穩態分布也可以得到[2]。并且文獻[2]證明出廣義的年齡過程和廣義的總的工作量過程有相同的穩態分布，等待時間和逗留時間的分布為PH分布，并得到這些PH分布的矩陣表示[2]。但分析過程有點差錯，我們將在文獻[2]的思想上進行改進，引進不同的附加變量。

1 廣義的年齡過程的改進分析

在文獻[2]中引進了一些附加變量構造了一個關于年齡過程ag(t)的馬爾可夫鏈，但當ag(t)＜0時附加變量Ia(t)的定義與計算過程是不相符的，在此對這個過程進行改進，引進一些與到達位相和服務過程相關的附加變量。引進附加變量分情況討論如下：

（1）ag(t)＜0時，我們引進三個附加變量Ia(t),J(t),Is(t)。我們由ag(t)＜0可得，此時系統為空，下一個顧客批還需要-ag(t)個時刻才能到達。我們用馬爾可夫鏈{ξn,n≥0}來定義Ia(t)，Ia(t)=ξn，如果第n個顧客批為將要接受服務的顧客批，那么Ia(t)表示將要達到的顧客批到達系統時半馬爾可夫鏈的狀態，J(t),Is(t)則分別表示這個顧客批的類型和其初始服務位相。

（2）ag(t)≥0時，我們仍引進三個附加變量：Ia(t),J(t),Is(t)。因為這個時候系統中有顧客存在，那么Ia(t)=ξn，如果第n個顧客批為正在接受服務的顧客批，那么Ia(t)表示正在接受服務的那個顧客批到達系統時半馬爾可夫鏈的狀態，J(t),Is(t)則分別表示正在接受服務的那個顧客批的類型和在t時刻的服務位相。可以看到，在ag(t)＜0時系統為空，顧客批還需-ag(t)個時刻才能到達，那么其到達時半馬爾可夫鏈的狀態以及它的類型和初始服務位相應該是一個未知數。但是我們可以將這個時間提前，使Ia(t),J(t),Is(t)提前發生變化，這并不對顧客批到達系統后狀態的轉移構成影響。因此，我們這樣構造是可行的，并且我們發現建立的這個過程{ag(t),Ia(t),J(t),Is(t),t≥0}在一個顧客批接受服務期間是具有馬爾可夫性的：這是因為這個顧客批的服務時間是由一個潛在的馬爾可夫鏈（PH分布）決定，Ia(t),J(t)在這期間是不發生變化的，而ag(t)的值增加1。在系統完成一個顧客批的服務時，根據馬爾可夫鏈Ia(t)發生改變，并且決定了到達間隔，ag(t)的值也發生改變。J(t)也由馬爾可夫鏈決定，Is(t)由服務時間的初始分布決定。因此，過程{ag(t),Ia(t),J(t),Is(t),t≥0}在一個顧客批服務完的時刻也是具有馬爾可夫性的。綜合以上，我們能看出我們建立的這個與ag(t)有關的過程是一個馬爾可夫過程[5]。

經分析，構造的這個關于年齡過程的馬爾可夫鏈{ag(t),Ia(t),J(t),Is(t),t≥0}的轉移概率矩陣為：

2 關于年齡過程的轉移概率矩陣的求解

（1）當ag(t)=x,x≤-1時，此時系統中為空，下一批顧客還要經過-x個時刻才能到達，在t+1時刻，顧客批要么還沒有到達，要么剛到達系統開始接受服務，但至少能肯定這個顧客批沒有服務完離開系統。那么應該有ag(t)隨時間應該增加1，而Ia(t),Ia(t+1)都是指將要到達的這個顧客批到達系統時半馬爾可夫鏈的狀態，J(t),J(t+1)都是表示這個顧客批的類型，Is(t),Is(t+1)也都表示其初始服務位相。于是，當ag(t)=x,x≤-1時，于是，由狀態按字典排序以及只有當y=x+1,j=j’,J=J’,i=i’時概率為1，則B=I(ma·mtot)×(ma·mtot)，而從ag(t)=x轉到其他年齡的概率都為零。

（2）當ag(t)=x,x≥0時，此時系統中至少有一個顧客批在接受服務，在t+1時刻，這個顧客批可能繼續接受服務，也可能服務完畢離開系統。

如果t時刻接受服務的顧客批在t+1時刻繼續接受服務，此時轉移矩陣塊為A0，那么應該有：ag(t+1)=x+1，而Ia(t)，Ia(t+1)都是指這個顧客批到達系統時半馬爾可夫鏈的狀態，J(t),J(t+1)都是表示這個顧客批的類型，但是Is(t)表示t時刻的服務位相，Is(t+1)表示t+1時刻的服務位相，這兩者的變化由服務位相的轉移矩陣決定。于是，

為了求出A0，我們根據狀態按字典排序將A0這個(ma·mtot)×(ma·mtot)的矩陣塊寫成ma·ma個mtot·mtot的矩陣子塊：

如果t時刻接受服務的顧客批在t+1時刻服務完畢離開系統，此時轉移矩陣塊為As,s≥1那么這時ag(t+1)與下一個顧客批有關，應有ag(t+1)=ag(t)+1-τn(t+1)+1。而Ia(t+1)是指下一個顧客批到達系統時半馬爾可夫鏈的狀態，J(t+1),Is(t+1)表示其類型和初始服務位相，于是，

同樣為了求出As，我們同樣根據狀態按字典排序將As這個(ma·mtot)×(ma·mtot)的矩陣塊寫成ma·ma個mtot·mtot的矩陣子塊：

綜合以上得到了轉移矩陣Pg。

定理1SM[K]/PH[K]/1/FCFS的關于年齡的馬爾可夫鏈的轉移矩陣Pg為隨機矩陣。

證明：

因此，轉移矩陣是一個隨機矩陣。

這與文獻[2]中年齡過程的轉移矩陣結果一樣。我們也能從馬爾科夫鏈{ag(t),Ia(t),J(t),Is(t),t≥0}得到很多關于年齡、系統閑期、逗留時間和等待時間的很多信息。并且，我們也可以和文獻[2]一樣從年齡過程的穩態分布得到它們的穩態分布。在這我們不再重復解決這個問題，有興趣的讀者可以參考文獻[2]。

[1]高卓.離散時間SM[K]/PH[K]/1/FCFS排隊系統的研究[J].科技信息,2014,5:7,32

[2]He Qi-ming.Age process,Workload Process,Sojourn Times,and Waiting Times in a Discrete Time SM[K]/PH[K]/1/FCFS Queue[J].Queuing Systems,2005,49(1):363-403

[3]Van Houdt B,Blondia C.The waiting time distribution of a type k customer in a discrete time MMAP[K]/PH[K]/c(c=1,2)queue using QBDs[J].Stochastic models,2004,20(1):55-69

[4]劉次華,何少鋒.批量到達的離散時間排隊系統[J].華中科技大學學報:自然科學版,2005,33(10):106-108

[5]Janssen AJEM,Van Leeuwaarden JSH.Analytic computation schemes for the discrete-time bulk service queue[J]. Queueing Systems,2005,50(2-3):141-163

[6]Marcel F Neuts.Matrix-geometric solutions in stochastic models[M].Baltimore and London:The Johns Hopkins University Press,1981

Analysis and Improvement of the Age Process in a Queuing System of Discrete TimeSM[K]/PH[K]/1/FCFS

GAO Zhuo1,XU De-ju2
1.Zhujiang College of South China Agricultural University,Guangzhou510900,China
2.School of Mathematical Sciences/Capital Normal University,Beijing100048,China

We studied a discrete time queuing system with multiple types of customers and a first-come-first-served(FCFS) service discipline.Customers arrive according to a semi-Markov arrival process and the service times of individual customers have PH-distributions.We studiedSM[K]/PH[K]/1/FCFSqueue and analyzed its generalized age process particularly.We introduced some auxiliary variables to construct a Markov chain associated withag(t)and obtained the transition probability matrix of this Markov chain.

Queuing systems;age process;Markov chain;the transition probability matrix

O226

:A

:1000-2324(2016)01-0923-04

2014-04-15

:2014-04-25

廣東高校優秀青年創新人才培養計劃項目(自然科學)(2013LYM_0117)

高卓(1981-),男,講師,碩士研究生,主要研究方向:隨機運籌學.E-mail:77275491@qq.com