一、隨機(jī)過程（Stochastic Process）：

1.定義：

設(shè)隨機(jī)實(shí)驗(yàn)的樣本空間S={s}，如果對于每個(gè)s，有對應(yīng)屬于參數(shù)集T的參數(shù)t的函數(shù)X(s,t)，那么對于所有的s，得到一組t的函數(shù){X(s,t),t∈T}，這個(gè)t的函數(shù)族稱為隨機(jī)過程，簡記為X(s,t)或X(t)。

族中的每個(gè)函數(shù)稱為該過程的一個(gè)樣本，它是隨機(jī)過程一次試驗(yàn)的物理實(shí)現(xiàn)，是一個(gè)確知的時(shí)間函數(shù)，稱為樣本函數(shù)或樣本曲線。

若固定某個(gè)觀察時(shí)刻t，此時(shí)X(s,t)是一個(gè)取決s的隨機(jī)變量，稱為在t時(shí)刻的狀態(tài)。

?

2.舉例：

給出如下隨機(jī)過程的三個(gè)樣本函數(shù)：

其中A與w0是正常數(shù)，而φ服從在[0,2π]上的均勻分布：

?

二、馬爾科夫過程與生滅過程：

1.馬爾科夫過程（Markov Process）與馬爾科夫鏈：

當(dāng)已知隨機(jī)過程在時(shí)刻ti所處狀態(tài)的條件下，過程在時(shí)刻t（>ti）所處的狀態(tài)與過程在時(shí)刻ti以前的狀態(tài)無關(guān)，而僅與過程在ti所處的狀態(tài)有關(guān)，則稱該過程為馬爾科夫過程。這種特性稱為隨機(jī)過程的“無后效性”或馬爾科夫性。

馬爾科夫過程是隨機(jī)過程的一個(gè)子類，其按狀態(tài)空間G和參數(shù)集T是連續(xù)還是離散，可分為四類，其中有兩種：

T和G都取連續(xù)集時(shí)，稱為馬爾科夫過程；

T和G都取離散集時(shí)，稱為馬爾科夫鏈；

?

2.生滅過程（Birth and death process）：

離散時(shí)間的生滅過程：是每一次狀態(tài)轉(zhuǎn)移都發(fā)生在相鄰狀態(tài)之間的齊次馬氏鏈。其狀態(tài)轉(zhuǎn)移矩陣P是一個(gè)夾層的矩陣，對于|i-j|>1有pij=0。

連續(xù)時(shí)間的生滅過程：一個(gè)連續(xù)時(shí)間，狀態(tài)空間S={0,1,2...}，為可數(shù)集的齊次馬爾科夫過程{X(t),T>=0}，稱為連續(xù)時(shí)間生滅過程。

（可數(shù)集：每個(gè)元素能與自然數(shù)集N的每個(gè)元素之間能建立一一對應(yīng)的集合）

生滅過程是用來處理輸入為最簡單流（即泊松分布），服務(wù)時(shí)間為負(fù)指數(shù)分布這樣一類最簡單排隊(duì)模型的方法。

λn——系統(tǒng)處于瞬時(shí)狀態(tài)N(t)時(shí)單位時(shí)間內(nèi)顧客的平均到達(dá)率

μn——系統(tǒng)處于瞬時(shí)狀態(tài)N(t)時(shí)單位時(shí)間內(nèi)顧客的平均離去率（或服務(wù)率）

以下為一生滅過程的舉例及其推導(dǎo)，其有無限個(gè)狀態(tài)：

?

三、排隊(duì)論簡述

什么是排隊(duì)論：

排隊(duì)論（queueing theory）是專門研究帶有隨機(jī)因素產(chǎn)生擁擠現(xiàn)象的優(yōu)化理論，是有關(guān)于服務(wù)設(shè)施與被服務(wù)者構(gòu)成的排隊(duì)服務(wù)系統(tǒng)的理論。

亦稱隨機(jī)服務(wù)系統(tǒng)理論。因?yàn)楸环?wù)者到達(dá)系統(tǒng)的時(shí)間是不確定的。

排隊(duì)論是計(jì)算機(jī)通信網(wǎng)絡(luò)和計(jì)算機(jī)系統(tǒng)中通信信息量研究的基礎(chǔ)理論，信息系統(tǒng)通信問題的定量研究往往要求借助于排隊(duì)論才能得到解決。

?

典型排隊(duì)系統(tǒng)模型：

排隊(duì)系統(tǒng)的三個(gè)基本組成：

輸入過程：顧客按照怎樣的規(guī)律到達(dá)；

排隊(duì)規(guī)則：顧客按照什么樣的規(guī)則排隊(duì)等待服務(wù)；

服務(wù)規(guī)則：服務(wù)機(jī)構(gòu)的設(shè)置，服務(wù)臺的數(shù)量，服務(wù)的方式，服務(wù)時(shí)間的分布等。

（1）輸入過程：

顧客到達(dá)的方式通常是一個(gè)給一個(gè)到達(dá)的，也可能是成批的。顧客到達(dá)總是有一定規(guī)律，即到達(dá)的過程或到達(dá)時(shí)間間隔符合一定的分布，稱到達(dá)分布。

顧客到達(dá)或到達(dá)時(shí)間通常假定為相互獨(dú)立的且遵從同一分布的隨機(jī)變量。

• 顧客來源：有限/無限
• 顧客數(shù)量：有限/無限
• 經(jīng)常性的顧客來源：顧客到達(dá)間隔時(shí)間服從某一概率分布
• 顧客的行為假定：在未服務(wù)之前不會離開、當(dāng)看到隊(duì)列很長的時(shí)候離開、從一個(gè)隊(duì)列移到另一個(gè)隊(duì)列

（2）隊(duì)列/排隊(duì)規(guī)則

• 隊(duì)列容量：有限/無限
• 排隊(duì)方式：單隊(duì)列、并聯(lián)式多隊(duì)列、串聯(lián)式多隊(duì)列、雜亂隊(duì)列

（3）服務(wù)規(guī)則

• 服務(wù)臺數(shù)量：單服務(wù)臺、多服務(wù)臺、無限服務(wù)臺
• 服務(wù)協(xié)議：FCFS、LCFS、RSS、PR、PS、IS
• 服務(wù)時(shí)間分布：指數(shù)、常熟、k階愛爾朗分布

服務(wù)協(xié)議：

（a）先來先服務(wù)：FCFS（First-Come-First-Served）

（b）后來后服務(wù)：LCFS（Last-Come-First-Served）隊(duì)列是一種堆棧形式，如果隊(duì)列中有兩個(gè)以上等待的顧客，則把最后到達(dá)的顧客作為下一個(gè)服務(wù)對象。

（c）隨機(jī)服務(wù)系統(tǒng)：RSS（Random Service System）在服務(wù)時(shí)從等待顧客中隨意抽取一個(gè)進(jìn)行服務(wù)。

（d）優(yōu)先服務(wù)和動態(tài)優(yōu)先服務(wù)：PR（Priority Service）預(yù)先規(guī)定優(yōu)先順序位的類別，且給到達(dá)顧客規(guī)定優(yōu)先順序位作為標(biāo)記的優(yōu)先權(quán)。通常按照FCFS服務(wù)，優(yōu)先權(quán)分為三類：排隊(duì)優(yōu)先權(quán)、中斷優(yōu)先權(quán)、動態(tài)優(yōu)先權(quán)。如計(jì)算機(jī)中斷的優(yōu)先級。

（e）處理器共享：PS（Processor Sharing）服務(wù)臺的處理能力被平均分配給隊(duì)列中的所有顧客，沒有排隊(duì)現(xiàn)象出現(xiàn)，當(dāng)顧客的數(shù)量增加時(shí)，只是顧客的服務(wù)時(shí)間邊長。如：網(wǎng)絡(luò)服務(wù)系統(tǒng)。

（f）無限服務(wù)臺：IS（Infinite Server）在這種情況下，隊(duì)列中的每個(gè)顧客接收完全相同的服務(wù)，而且就好像它是唯一的一個(gè)顧客一樣。好像對于每個(gè)顧客都可以“克隆”出一個(gè)心得服務(wù)臺，而且克隆的數(shù)目可以無限。

?

1.排隊(duì)系統(tǒng)的到達(dá)和服務(wù)

到達(dá)規(guī)律的描述

（1）主要描述參數(shù)

（a）到達(dá)時(shí)間：將某一時(shí)刻設(shè)為t0，顧客一次到達(dá)的時(shí)刻用..<=t-1<=t0<=t1<=t2<=...表示，若果在時(shí)刻tk到達(dá)的顧客為Nk，則到達(dá)的時(shí)點(diǎn)可用（tk，Nk）表示。

（b）平均到達(dá)間隔：一個(gè)顧客到達(dá)時(shí)刻之間的時(shí)寬為到達(dá)間隔。

（c）到達(dá)速率：單位時(shí)間到達(dá)顧客的平均數(shù)。

（2）到達(dá)規(guī)律：顧客到達(dá)的規(guī)律可用概率來描述，當(dāng)前到達(dá)的顧客數(shù)的常見分布是泊松分布。

服務(wù)規(guī)律的描述

（1）主要描述參數(shù)

（a）平均服務(wù)時(shí)間：設(shè)服務(wù)時(shí)間的分布函數(shù)為F（t），則服務(wù)時(shí)間的平均表示為∫F(t)dt。

（b）服務(wù)速率μ：指平均服務(wù)速率，單位時(shí)間內(nèi)被服務(wù)完的顧客數(shù)，即平均服務(wù)時(shí)間的倒數(shù)，μ=1/∫F(t)dt；

?

（2）服務(wù)規(guī)律：即服務(wù)時(shí)間的分布，典型的有指數(shù)分布、愛爾郎分布、一般分布。

?

2.經(jīng)典排隊(duì)模型

其格式為： A/B/n/S/Z

A：顧客到達(dá)的規(guī)律；B：服務(wù)時(shí)間分布；n：服務(wù)臺數(shù)目；S：隊(duì)列容量的大小；Z：服務(wù)規(guī)程

若隊(duì)列容量大小為∞時(shí)，可簡化為A/B/n/Z

若還為先來先服務(wù)時(shí)，可簡化為A/B/n

其中A、B的分布可用以下字母表示：

M（Markov）：若描述到達(dá)（A），則表示泊松到達(dá)；若描述服務(wù)（B），則指具有指數(shù)分布的時(shí)間。

G（General）：一般分布。

Ek（Erlang）：表示到達(dá)間隔或服務(wù)間隔服從k階愛爾朗分布

還有D：定長分布（常數(shù)間隔）、H：超幾何分布、L：H項(xiàng)式分布

典型的Z有：FCFS、LCFS、PR、RSS

?

3.基本排隊(duì)關(guān)系

由利特爾法則（Little's Law），有以下公式：

（1）Lq=λWq

Wq是一個(gè)顧客平均排隊(duì)等待的時(shí)間，λ是顧客平均到達(dá)率，所以在Wq時(shí)間內(nèi)有λWq個(gè)顧客到達(dá)，Lq表示排隊(duì)等待服務(wù)的平均顧客數(shù)量，故Lq=λWq。

（2）L=λW

系統(tǒng)中的平均顧客數(shù)（L）（包括等待的和正在被服務(wù)的顧客）等于顧客的平均到達(dá)率（λ）乘以一個(gè)顧客在系統(tǒng)中花費(fèi)的平均時(shí)間（W）。

（3）W=Wq+1/μ

一個(gè)顧客在系統(tǒng)中花費(fèi)的時(shí)間（W），就是它等待的時(shí)間（Wq）加上被服務(wù)的時(shí)間（1/μ）。

?

4.隊(duì)列分析的任務(wù)

隊(duì)列分析的基本任務(wù)是：

給出如下輸入信息（概率分布）：

到達(dá)速率（λ）、服務(wù)時(shí)間（1/μ）

求出如下輸出信息（均值、標(biāo)準(zhǔn)差）：

等待顧客的數(shù)量（Lq）、等待時(shí)間（Wq）、系統(tǒng)中顧客的數(shù)量（L）、逗留時(shí)間（W）

?

四、幾個(gè)常用的排隊(duì)模型

1.排隊(duì)模型與生滅過程：

※如果用N(t)表示時(shí)刻t系統(tǒng)中的顧客數(shù)，則{N(t),t>=0}就構(gòu)成了一個(gè)隨機(jī)過程。如果用“生”表示顧客的到達(dá)，“滅”表示顧客的離去，則對許多排隊(duì)過程來說，{N(t),t>=0}是一類特殊的隨機(jī)過程——生滅過程。

※服務(wù)臺忙的時(shí)間比率（服務(wù)強(qiáng)度）：顧客到達(dá)速率/服務(wù)速率，即ρ=λ/μ.

?

2.M/M/1模型

（1）生滅過程模型：

為 "二、2.生滅過程”中的模型。

?

根據(jù)連續(xù)生滅過程穩(wěn)定的條件，要求ρ<1。有如下推導(dǎo)：

Pk表示在系統(tǒng)穩(wěn)定狀態(tài)下，有k個(gè)顧客的概率。

其為服從參數(shù)為(1-ρ)的改進(jìn)型幾何分布，根據(jù)幾何型分布可得其數(shù)字特征，即顧客數(shù)量的均值與方差：

均值L=E=ρ/(1-ρ)，方差D=ρ/(1-ρ)2

根據(jù)little定理，顧客平均花費(fèi)時(shí)間W=L/λ=1/(μ(1-ρ))

因?yàn)閃=Wq+1/μ，Wq=W-1/μ=ρ/(μ(1-ρ))

由little定理，Lq=λWq=ρ2/(1-ρ)

?

（2）M/M/1系統(tǒng)運(yùn)行指標(biāo)：

?

※系統(tǒng)中平均顧客數(shù)：L=ρ/(1-ρ)

※顧客在系統(tǒng)中平均等待時(shí)間：W=1/(μ(1-ρ))

※隊(duì)列中平均顧客數(shù)：Lq=ρ2/(1-ρ)

※顧客在隊(duì)列中平均等待時(shí)間：Wq=ρ/(μ(1-ρ))

（3）例題（均為M/M/1系統(tǒng)）：

①一條通信線路的帶寬是2000bps，該線路用來傳一個(gè)字符（8位bit），來自應(yīng)用的要求是12000字符/分

求：等待被傳輸?shù)钠骄址麛?shù)Lq與每個(gè)字符平均傳輸時(shí)間W。

解：設(shè)單位時(shí)間為秒，則μ=2000/8=250，λ=12000/60=200，則ρ=0.8

Lq=0.64/0.2=3.2，W=0.8/(250*0.2)=16ms

②一個(gè)書店平均每分鐘有3個(gè)顧客到達(dá)，正常情況有48個(gè)顧客在書店中，求每一個(gè)顧客在商店花費(fèi)的平均時(shí)間。

解：設(shè)單位時(shí)間為分鐘，易知λ=3；因?yàn)長=48，得ρ=48/49，所以μ=49/16,；所以Wq=(48/49)/((49/16)*(1/49))≈15.6分

?

3.M/M/c 隊(duì)列模型：

該隊(duì)列系統(tǒng)的顧客到達(dá)為泊松流，到達(dá)速率為λ，有并列的c個(gè)服務(wù)臺，每個(gè)服務(wù)臺的服務(wù)速率為μ，服務(wù)規(guī)則FCFS。所有服務(wù)臺共享一個(gè)公用的隊(duì)列。

由于每個(gè)服務(wù)臺工作是相互獨(dú)立的（無協(xié)作）且平均服務(wù)率相同，于是整服務(wù)系統(tǒng)的平均服務(wù)率為cμ(n>=c)或nμ(n<c)。

（1）生滅過程模型：

平衡條件：ρ=λ/cμ<1

有如下推導(dǎo)：

（2）運(yùn)行指標(biāo)

（3）例題（服從M/M/c）M/M/1與M/M/c的比較：

某銀行有3個(gè)出納員，每人平均每小時(shí)可服務(wù)12人，顧客的到達(dá)服從泊松分布，平均每小時(shí)到達(dá)30個(gè)人。求：

①三名出納員都忙的概率及該銀行的主要運(yùn)行指標(biāo)；

②若所有的顧客排成3隊(duì)，平均分?jǐn)偟竭_(dá)人數(shù)（每隊(duì)每小時(shí)到達(dá)10人），計(jì)算主要運(yùn)行指標(biāo)；

③對比①②，得出什么結(jié)論？

解：

?

?

?

總結(jié)

以上是生活随笔為你收集整理的排队论简介的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。