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

高卓,徐德舉

1.華南農(nóng)業(yè)大學(xué)珠江學(xué)院,廣東廣州510900

2.首都師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院,北京100048

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

高卓1,徐德舉2

1.華南農(nóng)業(yè)大學(xué)珠江學(xué)院,廣東廣州510900

2.首都師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院,北京100048

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

排隊系統(tǒng);年齡過程;馬爾可夫鏈;轉(zhuǎn)移矩陣

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

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

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

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

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

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

經(jīng)分析，構(gòu)造的這個關(guān)于年齡過程的馬爾可夫鏈{ag(t),Ia(t),J(t),Is(t),t≥0}的轉(zhuǎn)移概率矩陣為：

2 關(guān)于年齡過程的轉(zhuǎn)移概率矩陣的求解

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

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

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

為了求出A0，我們根據(jù)狀態(tài)按字典排序?qū)0這個(ma·mtot)×(ma·mtot)的矩陣塊寫成ma·ma個mtot·mtot的矩陣子塊：

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

同樣為了求出As，我們同樣根據(jù)狀態(tài)按字典排序?qū)s這個(ma·mtot)×(ma·mtot)的矩陣塊寫成ma·ma個mtot·mtot的矩陣子塊：

綜合以上得到了轉(zhuǎn)移矩陣Pg。

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

證明：

因此，轉(zhuǎn)移矩陣是一個隨機矩陣。

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

[1]高卓.離散時間SM[K]/PH[K]/1/FCFS排隊系統(tǒng)的研究[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]劉次華,何少鋒.批量到達的離散時間排隊系統(tǒng)[J].華中科技大學(xué)學(xué)報:自然科學(xué)版,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

廣東高校優(yōu)秀青年創(chuàng)新人才培養(yǎng)計劃項目(自然科學(xué))(2013LYM_0117)

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