排隊(duì)理論(講義)課件

排隊(duì)論

QueueingTheory排隊(duì)理論(講義)CONTENTSPREPARATION:概率論與隨機(jī)過程

UNIT1排隊(duì)模型

UNIT2排隊(duì)網(wǎng)絡(luò)模型

UNIT3應(yīng)用之：QUICKPASS系統(tǒng)結(jié)束語(yǔ)2排隊(duì)理論(講義)PREPARATION

概率論和隨機(jī)過程Part1．概率論基礎(chǔ)1。

概率的定義

概率關(guān)系著對(duì)時(shí)間的數(shù)量分配。一個(gè)事件A的概率P(A)是對(duì)應(yīng)事件A要發(fā)生可能性的數(shù)量分配。概率有很多不同的定義，常用的有三種：(1)古典定義：P(A)=NA/N其中N是可能結(jié)果的總個(gè)數(shù)，NA是事件A在其中發(fā)生的結(jié)果的個(gè)數(shù)。例1.

求拋兩個(gè)骰子并且決定和為7的概率p?？偣灿?6種可能的結(jié)果，所以N=36有6種結(jié)果(1,6),(2,5),(3,4),(4,3),(5,2)和(6,1)為所求。所以NA=6，從而p=6/36=1/6。3排隊(duì)理論(講義)(2)相對(duì)頻率定義：

P(A)=lim

nA/n

n→∞

其中n是實(shí)驗(yàn)的次數(shù)，nA是A發(fā)生的次數(shù)

例2

投硬幣在大數(shù)量投擲后，硬幣的正面在上的可能性在0.5左右，上下兩面在上面具有相同的概率。(3)公理化定義：從一定數(shù)量的定義概率度量的公理出發(fā)，經(jīng)過推導(dǎo)規(guī)則達(dá)到概率的有效計(jì)算。這些公理包括：（a）

對(duì)于每一個(gè)事件A，有0≤P（A）≤1（b）

P（Ω）=1（c）

如果A和B是互斥的，則P（AUB）=P（A）+P（B）4排隊(duì)理論(講義)

2條件概率和獨(dú)立性

條件概率：假定事件B已經(jīng)發(fā)生時(shí)，事件A發(fā)生的條件概率P(A|B)可以定義如下：

P（A|B）=P（AB）/P（B）獨(dú)立性：如果P(AB)=P(A)P(B)，事件A和B叫做相互獨(dú)立的事件獨(dú)立性的概念可以推廣到三個(gè)或多個(gè)事件。

5排隊(duì)理論(講義)3全概率公式和貝葉斯定理全概率公式：給定一組互斥事件E1，E2，，…，En，這些事件的并集包括所有可能的結(jié)果，同時(shí)給任一個(gè)任意事件A，那么全概率公式可以表示為：

nP(A)=∑P(A|Ei)P(Ei)

i=1把計(jì)算A的概率分解為一些容易計(jì)算的概率之和。貝葉斯定理：

P(Ei|A)=

P(A|Ei)P(Ei)∑P(A|Ei)P(Ei)

也稱為后驗(yàn)概率公式，是在已知結(jié)果發(fā)生的情況下，求導(dǎo)致結(jié)果的某種原因的可能性的大小。6排隊(duì)理論(講義)Part2.隨機(jī)變量的數(shù)字特征隨機(jī)變量X是樣本點(diǎn)的函數(shù)，它的定義域是樣本空間Ω，值域是實(shí)數(shù)集R，即X：Ω→R隨機(jī)變量的數(shù)字特征對(duì)研究隨機(jī)變量是很重要的，常用的數(shù)字特征有：數(shù)學(xué)期望、方差、協(xié)方差和相關(guān)系數(shù)。1數(shù)學(xué)期望：連續(xù)情況：

E[X]=μx=∫xf(x)dx

積分區(qū)間從[-∞，∞]離散情況：E[X]=μx=∑kP{x=k}allk

它是一種統(tǒng)計(jì)平均值，簡(jiǎn)稱均值

2方差：D[X]=E[(X-μx)2]=E[X2]-μx2

它是度量隨機(jī)變量X與其均值E[X]的偏離程度。

均方差：方差的開方稱為均方差，或標(biāo)準(zhǔn)方差，記為σx

二階矩：連續(xù)情況：E[X2]=∫x2f(x)dx積分區(qū)間從[-∞，∞]離散情況：E[X2]=∑k2P{x=k}allk7排隊(duì)理論(講義)3協(xié)方差：兩個(gè)隨機(jī)變量X和Y的協(xié)方差定義如下：Cov(X,Y)=E[(X-μx)(Y-μy)]=E[XY]-E[X]E[Y]4相關(guān)系數(shù):兩個(gè)隨機(jī)變量X和Y的相關(guān)系數(shù)定義如下：r(X,Y)=Cov(X,Y)/σxσy相關(guān)系數(shù)是兩個(gè)隨機(jī)變量線性相關(guān)程度的度量。例3：設(shè)隨機(jī)變量（X，Y）的分布律如下：YX121??

-101/4求E(X),D(X),E(Y),D(Y),cov(X,Y),r(X,Y)8排隊(duì)理論(講義)Part3幾種重要的概率分布1貝努里分布它的概率分布為：P{X=1}=p，P{X=0}=1-p它也稱兩點(diǎn)分布或（0-1）分布。它描述一次貝努里實(shí)驗(yàn)中，成功或失敗的概率。

2

二項(xiàng)分布P{X=k}=Cnkpk(1-p)n-k,k=0,1,…,n它描述n次貝努里實(shí)驗(yàn)中事件A出現(xiàn)k次概率。

3

幾何分布

P{X=k}=p(1-p)k-1,k=1,2,…它描述在k次貝努里實(shí)驗(yàn)中首次出現(xiàn)成功的概率。9排隊(duì)理論(講義)幾何分布有一個(gè)重要的性質(zhì)-----后無(wú)效性：在前n次實(shí)驗(yàn)未出現(xiàn)成功的條件下，再經(jīng)過m次實(shí)驗(yàn)（即在n+m次實(shí)驗(yàn)中）首次出現(xiàn)成功的概率，等于恰好需要進(jìn)行m次實(shí)驗(yàn)出現(xiàn)首次成功的無(wú)條件概率。用式子表達(dá)：P{X=n+m|X>n}=P{X=m}(請(qǐng)同學(xué)們?cè)囎C明之）這種與過去歷史無(wú)關(guān)的性質(zhì)稱為馬爾可夫性。幾何分布在我們下面講的排隊(duì)論中是非常重要。它可以描述某一任務(wù)（或顧客）的服務(wù)持續(xù)時(shí)間。4泊松分布（Poisson）P{X=k}=λke-λ/k!k=0,1,2,…泊松分布是最重要的離散型概率分布之一，它作為表述隨機(jī)現(xiàn)象的一種形式，在計(jì)算機(jī)性能評(píng)價(jià)等實(shí)踐中扮演了重要的角色。在實(shí)際系統(tǒng)模型中，一般都要假定任務(wù)（或顧客）的到來(lái)是服從泊松分布的。實(shí)踐也證明：這種假設(shè)是有效的。10排隊(duì)理論(講義)5

（負(fù)）指數(shù)分布

它是一種連續(xù)型的概率分布，它的概率密度為

f（x）=

λe-λxx≥0

0x<0分布函數(shù)：F（x）=1-e-λxx≥0指數(shù)分布的一個(gè)有用的性質(zhì)是它的數(shù)學(xué)期望等于標(biāo)準(zhǔn)差：

μx=σx=1/λ

在連續(xù)型隨機(jī)變量中，只有指數(shù)分布具有無(wú)后效性。

即：若隨機(jī)變量ζ服從指數(shù)分布，對(duì)任意的

s>0,t>0，有P{ζ>s+t|ζ>s}=P{ζ>t}

在離散型隨機(jī)變量中，只有幾何分布具有無(wú)后效性。這兩種分布可以分別用來(lái)描繪離散等待時(shí)間和連續(xù)等待時(shí)間。在排隊(duì)理論中，指數(shù)分布是很重要的。11排隊(duì)理論(講義)

6

k-愛爾朗分布概率密度:

f(x)=(λkx)n-1λke-λkx/(n-1)!x≥0，λ>0.

0x<0數(shù)字特征：E[X]=1/λ;Var[X]=1/（kλ2）

如果k個(gè)隨機(jī)變量Xi，i=1，2，…,k,分別服從指數(shù)分布，那么隨機(jī)變量X=X1+X2+…+Xk服從愛爾朗分布。即：具有k-愛爾朗分布的隨機(jī)變量可以看作具有同一指數(shù)分布的獨(dú)立的k個(gè)隨機(jī)變量之和。k-愛爾朗分布在排隊(duì)模型中，得到廣泛應(yīng)用。如：假定顧客在到達(dá)窗口排隊(duì)必須通過一個(gè)關(guān)口，這個(gè)關(guān)口由k層構(gòu)成，通過每層的時(shí)間服從參數(shù)為λ的指數(shù)分布，這樣顧客通過整個(gè)關(guān)口到達(dá)窗口排隊(duì)時(shí)，就實(shí)現(xiàn)了愛爾朗分布。

如下圖：

k…2100…00窗口12排隊(duì)理論(講義)Part4隨機(jī)過程

隨機(jī)過程是定義在給定的概率空間上的一族隨機(jī)變量

{X(t)，t∈T}。我們知道：一個(gè)隨機(jī)變量是定義在樣本空間S上的函數(shù)，則隨機(jī)過程實(shí)際上就是一個(gè)函數(shù)族{X（t，s）|s∈S，t∈T}。若t固定，隨機(jī)過程X（t，s）就是隨機(jī)變量X（t）所取的值，稱為在t時(shí)刻的狀態(tài)。若s固定，它是t的函數(shù)，稱為隨機(jī)過程的樣本函數(shù)或樣本曲線。13排隊(duì)理論(講義)隨機(jī)過程的例子

為了更好的理解隨機(jī)過程，我們從一個(gè)例子開始。例如，n個(gè)同樣的電阻，同時(shí)記錄它們熱噪聲的電壓波形。電阻上的熱噪聲是由于電阻中的電子的熱運(yùn)動(dòng)引起的，因此，在t1時(shí)刻電阻上的熱噪聲電壓是一個(gè)隨機(jī)變量，并記為x(t1)，也就是說(shuō)t1時(shí)刻任一電阻r(i)上的噪聲電壓x(i,t1)是無(wú)法預(yù)先確切地知道的。這里n支電阻的熱噪聲電壓的集合是這個(gè)隨機(jī)實(shí)驗(yàn)的樣本空間S。對(duì)于某一支電阻，其熱噪聲電壓是一時(shí)間函數(shù)x(i，t)，是隨機(jī)過程的樣本函數(shù)。

對(duì)所有電阻來(lái)說(shuō)，其熱噪聲電壓就是一族時(shí)間函數(shù)，記為x(t)，這族時(shí)間函數(shù)就是“隨機(jī)過程”，族中每一時(shí)間函數(shù)稱為隨機(jī)過程的樣本函數(shù)。14排隊(duì)理論(講義)Part5馬爾可夫過程馬爾可夫過程(MarkovProcess)是具有無(wú)后效性的隨機(jī)過程。無(wú)后效性是指：當(dāng)過程在tn時(shí)刻所處的狀態(tài)為已知時(shí)，過程在大于tn的時(shí)刻所處狀態(tài)的概率特性只與過程在tn時(shí)刻所處的狀態(tài)有關(guān)，而與過程在tn時(shí)刻以前的狀態(tài)無(wú)關(guān)。換言之，對(duì)于隨機(jī)過程{X（t），t∈T}，如果對(duì)于任意參數(shù)t0<t1<t2<…<tn<t,在X(t0),X(t1),…X(tn)的值已知的情況下，X(t)的條件分布只與X(tn)的狀態(tài)有關(guān)，即：

P{X(t)≤x|X(tn)=xn,X(tn-1)=xn-1,…,X(t0)=x0

}=P{X(t)≤x|X(tn)=xn}此條件稱為過程的無(wú)后效性或過程的馬爾可夫性。t0t1tn-1tnt15排隊(duì)理論(講義)Part6生滅過程

生滅過程是一種特殊類型的馬爾可夫過程，在系統(tǒng)性能評(píng)價(jià)等實(shí)際模型中是非常重要的。

（1）離散時(shí)間生滅過程對(duì)于離散時(shí)間生滅過程，所有的一步轉(zhuǎn)移只發(fā)生在相鄰的狀態(tài)之間。轉(zhuǎn)移概率矩陣P是一個(gè)夾層的矩陣，其中，對(duì)于所有的

|i-j|>1有pij

=0(2)連續(xù)時(shí)間生滅過程

一個(gè)連續(xù)時(shí)間，狀態(tài)空間S={0，1，2…}為可數(shù)集的齊次馬爾可夫過程{X(t)，t≥0}，,稱為生滅過程。時(shí)齊性轉(zhuǎn)移概率Pij(t,τ)只與i,j,τ-t有關(guān)，即Pij(τ)=Pij(t,t+τ)16排隊(duì)理論(講義)練習(xí)練習(xí)：1。有10個(gè)電阻，其電阻值分別為1Ω，2Ω，…，10Ω，從中取出三個(gè)，要求取出的三個(gè)電阻，一個(gè)小于5Ω，一個(gè)等于5Ω，另一個(gè)大于5，Ω，問：取一次就能達(dá)到要求的概率。2．一袋內(nèi)裝有5只球，編號(hào)為1，2，3，4，5，從中任取3只，求被抽取3只球中，中間號(hào)碼X的分布規(guī)律。17排隊(duì)理論(講義)習(xí)題解答1．把從10個(gè)電阻中取出3個(gè)的各種可能取法作為樣本點(diǎn)全體，這是古典概率，其總數(shù)為C（10，3），有利場(chǎng)合為C（4，1）C（1，1）C（5，1）故，所求概率為：P=C（4，1）C（1，1）C（5，1）/C（10，3）=1/62．依題意，X的可能值為2，3，4，當(dāng)取中間號(hào)碼為k時(shí)，則另外兩只球必須分別在號(hào)碼小于k的k-1個(gè)中取一個(gè)，和在號(hào)碼大于k的5-k個(gè)中取一個(gè)，于是：

pk=P{X=k}=C(k-1,1)C(5-k,1)/C(5,3),k=2,3,4

所以，X的分布律為：

X234Pk0.30.40.3♂18排隊(duì)理論(講義)UNIT1排隊(duì)模型排隊(duì)論（queueingtheory），或稱隨機(jī)服務(wù)系統(tǒng)理論，作為運(yùn)籌學(xué)研究的一種有力手段，研究的內(nèi)容有3個(gè)方面：系統(tǒng)的性態(tài)，即與排隊(duì)有關(guān)的數(shù)量指標(biāo)的概率規(guī)律性；系統(tǒng)的優(yōu)化問題；統(tǒng)計(jì)推斷，根據(jù)資料合理建立模型。目的是正確設(shè)計(jì)和有效運(yùn)行各個(gè)服務(wù)系統(tǒng)，使之發(fā)揮最佳效益。

排隊(duì)論不僅在理論上達(dá)到了成熟階段，而且其應(yīng)用范圍不斷增加。概括起來(lái)，它已在電話交換網(wǎng)、公路、鐵路、航空運(yùn)輸、工程管理、公共服務(wù)、貨物存儲(chǔ)和生產(chǎn)流水線過程等方面得到了廣泛的應(yīng)用。特別地，排隊(duì)論是計(jì)算機(jī)通信網(wǎng)絡(luò)和計(jì)算機(jī)系統(tǒng)中通信信息量研究的基礎(chǔ)理論，信息系統(tǒng)通信問題的定量研究往往要求借助于排對(duì)論才能得到解決。19排隊(duì)理論(講義)排隊(duì)常常是件很令人惱火的事情……

尤其是在我們這樣的人口大國(guó)

電話亭－1978年在北京15%的電話要在1小時(shí)后才能接通。在電報(bào)大樓打電話的人還要帶著午飯去排隊(duì)

銀行窗口，ATM游樂場(chǎng)的游樂項(xiàng)目醫(yī)院、理發(fā)、火車售票…在現(xiàn)實(shí)生活中，為了接受某種服務(wù)，排隊(duì)等待是常見的現(xiàn)象。從排隊(duì)等待得到抽象的物理模型，進(jìn)一步建立數(shù)學(xué)模型的一整套理論就是所謂的排隊(duì)論。20排隊(duì)理論(講義)什么是排隊(duì)論？排隊(duì)論是專門研究帶有隨機(jī)因素，產(chǎn)生擁擠現(xiàn)象的優(yōu)化理論。亦稱為隨機(jī)服務(wù)系統(tǒng)理論。因?yàn)楸环?wù)者到達(dá)系統(tǒng)的時(shí)間是不確定的。有關(guān)于由服務(wù)設(shè)施與被服務(wù)者構(gòu)成的排隊(duì)服務(wù)系統(tǒng)的理論。21排隊(duì)理論(講義)本講主要掌握：基本模型M/M/1模型M/M/c模型其他模型應(yīng)用：校園網(wǎng)的設(shè)計(jì)和調(diào)節(jié)收費(fèi)♂※22排隊(duì)理論(講義)基本的排隊(duì)模型基本組成概念與記號(hào)指數(shù)分布和生滅過程♂23排隊(duì)理論(講義)典型排隊(duì)系統(tǒng)模型

顧客到達(dá):在隊(duì)列中排隊(duì)服務(wù)臺(tái)服務(wù)

顧客離開

輸入源的到達(dá)規(guī)律隊(duì)列大??？特性？到達(dá)方式？服務(wù)規(guī)律？服務(wù)協(xié)議？

在本單元中，我們主要介紹排隊(duì)系統(tǒng)的組成和特征，排隊(duì)系統(tǒng)的到達(dá)和服務(wù)，經(jīng)典排隊(duì)模型等內(nèi)容。顧客到達(dá)規(guī)律和服務(wù)規(guī)律都是通過概率來(lái)描述的，所以概率論是排隊(duì)論的基礎(chǔ)。輸入源。。。24排隊(duì)理論(講義)基本組成輸入來(lái)源隊(duì)列服務(wù)機(jī)構(gòu)排隊(duì)系統(tǒng)顧客服務(wù)完離開排隊(duì)系統(tǒng)的三個(gè)基本組成部分.輸入過程(顧客按照怎樣的規(guī)律到達(dá));排隊(duì)規(guī)則(顧客按照一定規(guī)則排隊(duì)等待服務(wù));服務(wù)機(jī)構(gòu)(服務(wù)機(jī)構(gòu)的設(shè)置,服務(wù)臺(tái)的數(shù)量,服務(wù)的方式,服務(wù)時(shí)間分布等)♂25排隊(duì)理論(講義)基本排隊(duì)模型－輸入過程顧客來(lái)源有限/無(wú)限顧客數(shù)量有限無(wú)限經(jīng)常性的顧客來(lái)源顧客到達(dá)間隔時(shí)間:到下一個(gè)顧客到達(dá)的時(shí)間.服從某一概率分布.(指數(shù)分布)顧客的行為假定在未服務(wù)之前不會(huì)離開;當(dāng)看到隊(duì)列很長(zhǎng)的時(shí)候離開；從一個(gè)隊(duì)列移到另一個(gè)隊(duì)列。♂

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

顧客的到達(dá)或到達(dá)時(shí)間通常假定為相互獨(dú)立的且遵從同一分布的隨機(jī)變量。26排隊(duì)理論(講義)基本排隊(duì)模型－隊(duì)列/排隊(duì)規(guī)則隊(duì)列隊(duì)列容量有限/無(wú)限排隊(duì)方式單隊(duì)列并聯(lián)式多隊(duì)列串聯(lián)式多隊(duì)列雜亂隊(duì)列♂

對(duì)于一個(gè)有限大小的隊(duì)列來(lái)說(shuō)，顧客可能從隊(duì)列中丟失。有什么樣的服務(wù)協(xié)議就有什么樣的與之對(duì)應(yīng)的排隊(duì)方式。

27排隊(duì)理論(講義)基本排隊(duì)模型－服務(wù)規(guī)則服務(wù)機(jī)構(gòu)服務(wù)設(shè)施，服務(wù)渠道與服務(wù)臺(tái)服務(wù)臺(tái)數(shù)量單服務(wù)臺(tái)系統(tǒng)多服務(wù)臺(tái)系統(tǒng)無(wú)限服務(wù)臺(tái)系統(tǒng)服務(wù)協(xié)議先來(lái)先服務(wù)（FCFS）后來(lái)先服務(wù)（LCFS）隨機(jī)服務(wù)（RSS）有優(yōu)先權(quán)的服務(wù)（PR）服務(wù)時(shí)間分布指數(shù),常數(shù),k階Erlang♂

一般服務(wù)臺(tái)對(duì)顧客是一個(gè)一個(gè)進(jìn)行服務(wù)的，且對(duì)每一個(gè)顧客的服務(wù)時(shí)間長(zhǎng)短不一。

將服務(wù)時(shí)間看作隨機(jī)變量，那么它們是相互獨(dú)立的且遵循同一分布。因此描述服務(wù)規(guī)律時(shí)，采用服務(wù)時(shí)間的概率分布，即服務(wù)分布。

服務(wù)分布同到達(dá)分布一樣，到底屬于哪一種概率分布，要根據(jù)具體排隊(duì)問題進(jìn)行分析。28排隊(duì)理論(講義)服務(wù)協(xié)議（a）先來(lái)先服務(wù)

顧客到達(dá)的先后次序排隊(duì)接受服務(wù)，用FCFS（first－come－first－served）表示。（b）后來(lái)先服務(wù)（或稱先來(lái)后服務(wù)）

隊(duì)列是一種堆棧形式（臨時(shí)寄存貨物的地方）。當(dāng)某一顧客服務(wù)結(jié)束時(shí)，如果在隊(duì)列中有兩個(gè)以上等待的顧客，則把最后到達(dá)的顧客作為下一個(gè)服務(wù)的對(duì)象。用LCFS（last－come—first－served）表示。（c）隨機(jī)選擇服務(wù)

在服務(wù)時(shí)從等待顧客中隨意抽取一個(gè)進(jìn)行服務(wù)。（d）優(yōu)先服務(wù)和動(dòng)態(tài)優(yōu)先服務(wù)

預(yù)先規(guī)定優(yōu)先順序位的類別、且給到達(dá)顧客規(guī)定優(yōu)先順序位作為標(biāo)記的優(yōu)先權(quán)。通常按FCFS進(jìn)行服務(wù)。優(yōu)先權(quán)分為三類：排隊(duì)優(yōu)先權(quán)、中斷優(yōu)先權(quán)、動(dòng)態(tài)優(yōu)先權(quán)。如計(jì)算機(jī)中斷的優(yōu)先級(jí)。（e）處理器共享（processorsharing，PS）

服務(wù)臺(tái)的處理能力被平均分配給隊(duì)列中的所有顧客，沒有排隊(duì)現(xiàn)象出現(xiàn)，當(dāng)顧客的數(shù)量增加時(shí)，只是顧客的服務(wù)時(shí)間變長(zhǎng)。如：網(wǎng)絡(luò)服務(wù)系統(tǒng)。（f）無(wú)限服務(wù)臺(tái)（infiniteserver，Is）

在這種情況下，隊(duì)列中的每個(gè)顧客接受完全相同的服務(wù)，而且就好像它是唯一的一個(gè)顧客一樣。好像對(duì)于每個(gè)顧客都可以“克隆”出一個(gè)新的服務(wù)臺(tái)，而且克隆的數(shù)目可以無(wú)限。♂29排隊(duì)理論(講義)排隊(duì)系統(tǒng)的到達(dá)和服務(wù)1到達(dá)規(guī)律的描述（1）主要描述參數(shù)（a）到達(dá)時(shí)點(diǎn)

將某一時(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ù)叫到達(dá)速率，也稱到達(dá)密度或輸入速率。（2）到達(dá)規(guī)律

顧客的到達(dá)規(guī)律可以用概率來(lái)描述，兩個(gè)顧客到達(dá)的時(shí)間間隔是獨(dú)立的隨機(jī)變量，服從同一概率分布時(shí)。常用的分布規(guī)律有：（a）一般到達(dá)（b）泊松到達(dá)（c）愛爾朗到達(dá)（d）等間隔到達(dá)30排隊(duì)理論(講義)泊松分布和負(fù)指數(shù)分布在排隊(duì)論中的應(yīng)用泊松分布（Poisson）：

P{X=k}=λke-λ/k!k=0,1,2,…，μx=σx=λ泊松分布是最重要的離散型概率分布之一，也是表述隨機(jī)現(xiàn)象的一種重要形式。在實(shí)際系統(tǒng)模型中，一般都要假定任務(wù)（或顧客）的到來(lái)是泊松分布的。實(shí)踐也證明：這種假設(shè)有效。

如果顧客到達(dá)的人數(shù)是符合泊松分布，即在時(shí)間T內(nèi)到達(dá)有k個(gè)顧客到達(dá)的概率為：p=（λT）ke-λT/k!，在時(shí)間T內(nèi)顧客到達(dá)的平均顧客數(shù)=λT，平均到達(dá)速度（顧客數(shù)/秒）=λ服從泊松分布過程的到達(dá)被認(rèn)為是隨機(jī)到達(dá)，因?yàn)楫?dāng)顧客根據(jù)泊松過程到達(dá)時(shí)，顧客在各個(gè)時(shí)刻到達(dá)的可能性相同并與其它顧客的到達(dá)無(wú)關(guān)。

31排隊(duì)理論(講義)（負(fù)）指數(shù)分布：

它是一種連續(xù)型的概率分布，它的概率密度：

f（x）=λe-λxx≥0它的分布函數(shù)：F（x）=1-e-λxx≥0指數(shù)分布的一個(gè)有用的性質(zhì)是它的數(shù)學(xué)期望等于標(biāo)準(zhǔn)差：μx=σx=1/λ泊松分布和指數(shù)分布的關(guān)系：

如果顧客以泊松到達(dá),則顧客到達(dá)的時(shí)間間隔Ta服從指數(shù)分布，即：P{Ta<t}=1-e-λt,E[Ta]=1/λ因此，平均到達(dá)的時(shí)間間隔是到達(dá)速率的倒數(shù)。32排隊(duì)理論(講義)負(fù)指數(shù)分布密度函數(shù)均值方差隨機(jī)變量T（兩個(gè)顧客相繼到達(dá)的時(shí)間間隔）分布函數(shù)

fT(t)t33排隊(duì)理論(講義)負(fù)指數(shù)分布性質(zhì)1

fT(t)tttfT(t)是一個(gè)嚴(yán)格下降函數(shù)34排隊(duì)理論(講義)負(fù)指數(shù)分布性質(zhì)2無(wú)后效性（無(wú)記憶性）不管多長(zhǎng)時(shí)間(t)已經(jīng)過去，逗留時(shí)間的概率分布與下一個(gè)事件的相同.或者說(shuō)，后一個(gè)顧客到來(lái)所需時(shí)間與前一個(gè)顧客到來(lái)所需時(shí)間無(wú)關(guān)。35排隊(duì)理論(講義)負(fù)指數(shù)分布性質(zhì)3幾個(gè)獨(dú)立的指數(shù)分布的隨機(jī)變量的最小也服從指數(shù)分布幾個(gè)獨(dú)立的指數(shù)分布的隨機(jī)變量的和還是一個(gè)服從指數(shù)分布的隨機(jī)變量T1(

1)T1(

2)T1(

3)T

(

1+2+3)36排隊(duì)理論(講義)負(fù)指數(shù)分布性質(zhì)4負(fù)指數(shù)分布Poisson分布在t時(shí)間內(nèi)已經(jīng)服務(wù)n個(gè)顧客的概率1/:平均服務(wù)時(shí)間平均服務(wù)率=相繼顧客到達(dá)平均間隔時(shí)間37排隊(duì)理論(講義)負(fù)指數(shù)分布性質(zhì)5♂38排隊(duì)理論(講義)排隊(duì)論基本概念部分練習(xí)練習(xí)1：1。指出下列排隊(duì)系統(tǒng)中的顧客和服務(wù)臺(tái)：（1）自行車修理店；（2）按客戶訂單進(jìn)行加工的加工車間（3）機(jī)場(chǎng)起飛的客機(jī)（4）十字路口紅燈前的車輛2。判斷正誤（1）若到達(dá)排隊(duì)系統(tǒng)的顧客人數(shù)服從泊松分布，則依次到達(dá)的兩名顧客之間的間隔時(shí)間服從指數(shù)分布。（2）在一個(gè)排隊(duì)系統(tǒng)中，不管顧客到達(dá)和服務(wù)時(shí)間的情況如何，只要運(yùn)行時(shí)間足夠長(zhǎng)的時(shí)間后，系統(tǒng)將進(jìn)入穩(wěn)定狀態(tài)。（3）在排隊(duì)系統(tǒng)中，顧客等待時(shí)間的分布不受排隊(duì)規(guī)則的影響。

39排隊(duì)理論(講義)2服務(wù)規(guī)律的描述(1)主要描述參量

（a）平均服務(wù)時(shí)間設(shè)服務(wù)時(shí)間的分布函數(shù)為F（t），則服務(wù)時(shí)間的平均表示為:1/μ=∫tdF(t)其中μ稱為平均服務(wù)速率，平均一個(gè)顧客的服務(wù)時(shí)間。（b）服務(wù)速率一般指平均服務(wù)速率，單位時(shí)間內(nèi)被服務(wù)完的顧客數(shù)，用μ來(lái)表示。(2)服務(wù)規(guī)律

服務(wù)規(guī)律通常是就服務(wù)時(shí)間的分布而言的。服務(wù)時(shí)間分布典型地有指數(shù)分布、愛爾朗分布、一般分布等。

結(jié)論：顧客到達(dá)規(guī)律和服務(wù)規(guī)律都是通過概率來(lái)描述的，所以概率論是排隊(duì)論的基礎(chǔ)。40排隊(duì)理論(講義)

經(jīng)典排隊(duì)模型它的格式為：

A／B／n／S／Z其中符號(hào)的含義如下：

A：顧客到達(dá)的規(guī)律；B：服務(wù)時(shí)間分布；n：服務(wù)臺(tái)的數(shù)目；S：隊(duì)列容量的大?。籞：服務(wù)規(guī)程。當(dāng)隊(duì)列的大小為無(wú)窮大、且服務(wù)規(guī)程為先來(lái)先服務(wù)時(shí)，經(jīng)典排隊(duì)模型可簡(jiǎn)化為

A／B／n不同類型的排隊(duì)，A、B可用如下約定的字母表示。M：如果用于描述到達(dá)，表示泊松到達(dá)過程，到達(dá)時(shí)間間隔符合指數(shù)分布；如果用于描述服務(wù)，則指具有指數(shù)分布的時(shí)間。M表示Markov的第一個(gè)字母。G：一般分布。表示到達(dá)間隔時(shí)間或服務(wù)時(shí)間服從一般分布。G是General的第一個(gè)字母。

Ek：k-愛爾朗分布。表示到達(dá)間隔時(shí)間或服務(wù)時(shí)間服從k-愛爾朗分布。E是Erlang的第一個(gè)字母。D:定長(zhǎng)分布(常數(shù)時(shí)間)H：超幾何分布。

L：H項(xiàng)式分布。Z代表的服務(wù)規(guī)程典型的有：

FCFS：先來(lái)先服務(wù)；LCFS：后來(lái)先服務(wù)；RSS：隨機(jī)選擇服務(wù)；

PR：優(yōu)先權(quán)服務(wù)。

Ba：集體（批量）服務(wù)。

GD：一般規(guī)約服務(wù)，即通用規(guī)約服務(wù)。41排隊(duì)理論(講義)3基本排隊(duì)關(guān)系在對(duì)排隊(duì)進(jìn)行分析時(shí)，為了便于分析，經(jīng)常做一些簡(jiǎn)化假設(shè)。對(duì)一個(gè)排隊(duì)系統(tǒng)，若滿足以下三個(gè)條件：（1）排隊(duì)系統(tǒng)能夠進(jìn)入統(tǒng)計(jì)平衡狀態(tài)；（2）服務(wù)員的忙期與閑期交替出現(xiàn)，即系統(tǒng)不是總處于忙的狀態(tài)；（3）系統(tǒng)中任一顧客不會(huì)永遠(yuǎn)等待，系統(tǒng)也不會(huì)永無(wú)顧客到達(dá)。

則下列Little公式成立（排隊(duì)論中的通用公式）：（1）Lq=λWq

我們知道一個(gè)顧客的平均排隊(duì)等待時(shí)間是Wq，且顧客是以平均速率λ到達(dá)，所以在時(shí)間Wq內(nèi)有λWq個(gè)顧客到達(dá)，Lq表示排隊(duì)等待服務(wù)的平均顧客數(shù)量，所以有：Lq=λWq（2）L=λW

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

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

42排隊(duì)理論(講義)4隊(duì)列分析的任務(wù)和假設(shè)條件

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

給出如下輸入信息（概率分布）：到達(dá)速率（λ）服務(wù)時(shí)間（1/)

求出如下輸出信息（均值、標(biāo)準(zhǔn)差）：等待顧客的數(shù)量（Lq,σLq）等待時(shí)間（Wq，σwq）系統(tǒng)中顧客的數(shù)量（L，σL）逗留時(shí)間（W，σw）排隊(duì)論中的假設(shè)：在排隊(duì)分析中，最重要的一個(gè)假設(shè)是到達(dá)速率服從泊松分布，等效的說(shuō)法是到達(dá)間隔時(shí)間服從指數(shù)分布，這又等價(jià)于說(shuō)到達(dá)是隨機(jī)的并彼此獨(dú)立。我們幾乎一直要作這一假定。沒有它，大部分的排隊(duì)分析是不可能的。在這個(gè)假定的條件下，我們會(huì)發(fā)現(xiàn)僅僅知道到達(dá)速率和服務(wù)時(shí)間的均值和標(biāo)準(zhǔn)差就可以得到許多有用的結(jié)果。43排隊(duì)理論(講義)模型之：M/M/c排隊(duì)模型1.M/M/1模型

顧客按照速率為λ的泊松過程到達(dá)，顧客的服務(wù)時(shí)間是獨(dú)立同分布的隨機(jī)變量，通常分布設(shè)為均值為1／μ的指數(shù)分布。假設(shè)顧客按照到達(dá)的順序接受服務(wù)，即FCFS服務(wù)。例如，如果“顧客”表示到達(dá)計(jì)算機(jī)系統(tǒng)的作業(yè)任務(wù)，那么“服務(wù)臺(tái)”代表計(jì)算機(jī)系統(tǒng)。另外一種M/M/1隊(duì)列的解釋為：顧客代表消息，而服務(wù)臺(tái)代表通信信道。44排隊(duì)理論(講義)隨機(jī)過程和概率論在排隊(duì)論中的應(yīng)用1.把排隊(duì)過程看成生滅過程如果N（t）表示時(shí)刻t系統(tǒng)中的顧客數(shù)，則{N（t），t≥0}就構(gòu)成了一個(gè)隨機(jī)過程。如果用“生”表示顧客的到達(dá)，“滅”表示顧客的離去，則對(duì)許多排隊(duì)過程來(lái)說(shuō)，{N（t），t≥0}是一類特殊的隨機(jī)過程---生滅過程。服務(wù)員忙的時(shí)間比率：ρ=λ/μ=顧客到達(dá)速率/服務(wù)速率，也稱為服務(wù)強(qiáng)度ρ。2.由生滅過程得到幾何分布根據(jù)連續(xù)生滅過程穩(wěn)定的條件，要求ρ<1，根據(jù)連續(xù)時(shí)間生滅過程的計(jì)算公式，以得到系統(tǒng)在穩(wěn)定狀態(tài)下，有k個(gè)顧客的概率如下：Pk=(1-ρ)ρk,P0=1-ρ對(duì)于穩(wěn)定的系統(tǒng)(ρ<1),穩(wěn)定狀態(tài)概率服從參數(shù)為1-ρ的改進(jìn)型幾何分布。3.由幾何分布可以得到系統(tǒng)中平均顧客數(shù)量和等待時(shí)間

幾何分布：P{X=k}=p(1-p)k-1,k=1,2,…幾何分布的數(shù)學(xué)期望為：1/p,方差為:q/p2

令p=1-ρ,計(jì)算出系統(tǒng)中顧客數(shù)量的均值和方差：L=E[N]=ρ/(1-ρ)Var[N]=ρ/(1-ρ)2令隨機(jī)變量R代表穩(wěn)定狀態(tài)的響應(yīng)時(shí)間，即一個(gè)顧客在系統(tǒng)中花費(fèi)的時(shí)間，則W=E[R]，根據(jù)L=λW，可以得到:W=1/[μ(1-ρ)]45排隊(duì)理論(講義)隨機(jī)過程和概率論在排隊(duì)論中的應(yīng)用4.由系統(tǒng)中顧客平均數(shù)量和等待時(shí)間得隊(duì)列中顧客數(shù)量w和等待時(shí)間Tw令隨機(jī)變量Wt代表等待時(shí)間，St代表服務(wù)時(shí)間，則：R=Wt+StE[R]=E[Wt]+E[St]=E[Wt]+1/μ所以顧客的平均等待時(shí)間Wq=E[Wt]=E[R]-1/μ=ρ/[μ(1-ρ)]

即：Wq=ρ/μ(1-ρ)令隨機(jī)變量Wi表示隊(duì)列中正在等待的顧客數(shù)量，再根據(jù)little公式，Lq=E[Wi]=λ*E[Wt]=λ*ρ/[μ(1-ρ)]=ρ2/(1-ρ)

即：Lq=ρ2/(1-ρ)

♂46排隊(duì)理論(講義)M/M/1系統(tǒng)運(yùn)行指標(biāo)系統(tǒng)中平均顧客數(shù)：

L=ρ/(1-ρ),

顧客在系統(tǒng)中平均等待時(shí)間：

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

Wq=ρ/[μ(1-ρ)]隊(duì)列中平均顧客數(shù)：

Lq=ρ2/(1-ρ)在單服務(wù)臺(tái)系統(tǒng)中的little公式：

ρ=λ1/,L=Lq+ρ通用的little公式：

Lq=λWq

L=λWW=Wq+1/

47排隊(duì)理論(講義)M/M/1模型練習(xí)練習(xí)2：1一個(gè)書店平均每分鐘有3個(gè)顧客到達(dá)，正常情況有48個(gè)顧客在書店中，求每一個(gè)顧客在商店花費(fèi)的平均時(shí)間？2一條通信線路的帶寬是2000位/秒，該線路用來(lái)傳8位一個(gè)的字符，所以該線路的最大速率是250字符/秒,來(lái)自應(yīng)用要求是12000字符/分。求：（1）等待被傳輸?shù)钠骄址麛?shù)Lq,（2）每個(gè)字符平均傳輸時(shí)間W.3假定一個(gè)電話通話的持續(xù)時(shí)間平均3分鐘，一個(gè)人等待電話平均最大可以忍耐3分鐘，求可以支持的最大呼叫量？48排隊(duì)理論(講義)M/M/1模型練習(xí)4。某修理店只有一個(gè)修理工，來(lái)修理的顧客到達(dá)過程為Poission流，平均4人/小時(shí)；修理時(shí)間服從負(fù)指數(shù)分布，平均需要6分鐘。試求：（1）修理店空閑的概率；（2）店內(nèi)恰有三個(gè)顧客的概率（3）店內(nèi)至少有一個(gè)顧客的概率（4）在店內(nèi)的平均顧客數(shù)（5）每位顧客在店內(nèi)的平均逗留時(shí)間（6）等待服務(wù)的平均顧客數(shù)（7）每位顧客平均等待服務(wù)時(shí)間（8）顧客在店內(nèi)等待時(shí)間超過10分鐘的概率M/M/1模型中常用公式：系統(tǒng)中有k個(gè)顧客的概率，μk=(1-ρ)ρk,μ0=1-ρ系統(tǒng)中顧客數(shù)量的均值和方差：E[N]=ρ/(1-ρ)Var[N]=ρ/(1-ρ)2M/M/1隊(duì)列中一般的公式：L=E[N],W=1/μ(1-ρ)，Wq=ρ/μ(1-ρ)，Lq=ρ2/(1-ρ)在單服務(wù)員系統(tǒng)中的little公式：ρ=λ1/,L=Lq+ρ通用的little公式：Lq=λWq

L=λWW=Wq+1/

顧客在系統(tǒng)中的逗留時(shí)間T，服從參數(shù)為μ-λ的負(fù)指數(shù)分布，即：P{T>t}=e–(μ-λ)t49排隊(duì)理論(講義)2.M/M/c模型M/M/c隊(duì)列模型如下：

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

λk=

λ，k=0,1,2,…

μk=cμk≧c根據(jù)的生滅過程特點(diǎn)，可以得到下面在M/M/c隊(duì)列中的常用公式。C個(gè)服務(wù)臺(tái)50排隊(duì)理論(講義)M/M/c模型系統(tǒng)運(yùn)行指標(biāo)系統(tǒng)的服務(wù)強(qiáng)度ρ，所有服務(wù)臺(tái)是空的概率P0,所有服務(wù)臺(tái)都在忙的概率P,，平均等待顧客數(shù)量Lq,系統(tǒng)中平均顧客數(shù)量L，平均系統(tǒng)逗留時(shí)間W,平均排隊(duì)等候時(shí)間Wq,分別為：51排隊(duì)理論(講義)M/M/c模型系統(tǒng)運(yùn)行指標(biāo)等價(jià)地：系統(tǒng)中的平均顧客數(shù)量L=cρ+ρP0(cρ)c/[c!(1-ρ)2]其中，平均等待顧客數(shù)量Lq=ρP0(cρ)c/[c!(1-ρ)2]令隨機(jī)變量M表示“忙”服務(wù)臺(tái)的數(shù)量，E[M]=cρ=λ/μ

所以，任意一個(gè)服務(wù)臺(tái)的利用率ρ=λ/（cμ）在多服務(wù)臺(tái)系統(tǒng)中的Little公式：ρ=λ/（cμ），L=Lq+ρc。請(qǐng)同學(xué)們思考：一個(gè)M/M/c系統(tǒng)與c個(gè)M/M/1系統(tǒng)比較，那一種效率高？52排隊(duì)理論(講義)基本排隊(duì)模型－記號(hào)方案ServerQueueArrival顧客到達(dá)時(shí)間間隔分布/服務(wù)時(shí)間分布/服務(wù)臺(tái)數(shù)目/排隊(duì)系統(tǒng)允許的最大顧客容量/顧客總體數(shù)量/排隊(duì)規(guī)則(Kendall記號(hào))M/M/1/

/

/FCFS

M/M/1/

M:負(fù)指數(shù)分布(Markovian)D:定長(zhǎng)分布(常數(shù)時(shí)間)Ek:k階Erlang分布G:普通的概率分布(任意概率分布)53排隊(duì)理論(講義)基本排隊(duì)模型－記號(hào)系統(tǒng)狀態(tài):L=排隊(duì)系統(tǒng)顧客的數(shù)量,隊(duì)長(zhǎng)。N(t)=在時(shí)間t排隊(duì)系統(tǒng)中顧客的數(shù)量。Lq=等待服務(wù)的顧客的數(shù)量,隊(duì)列長(zhǎng)度。Pn(t)=在時(shí)間t,排隊(duì)系統(tǒng)中恰好有n個(gè)顧客的概率。 s=

服務(wù)臺(tái)的數(shù)目。54排隊(duì)理論(講義)基本排隊(duì)模型－

統(tǒng)計(jì)平穩(wěn)條件下的記號(hào)

n= 系統(tǒng)有n個(gè)顧客時(shí)的平均到達(dá)率（單位時(shí)間內(nèi)平均到達(dá)的顧客人數(shù)即是平均到達(dá)率）

n= 系統(tǒng)有n個(gè)顧客時(shí)的平均服務(wù)率（單位時(shí)間內(nèi)被服務(wù)完的顧客數(shù)即是平均服務(wù)率）= 對(duì)任何n都是常數(shù)的平均到達(dá)率.= 對(duì)任何n都是常數(shù)的平均服務(wù)率.1/= 期望到達(dá)間隔時(shí)間1/= 期望服務(wù)時(shí)間

= 服務(wù)強(qiáng)度，或稱使用因子，/

55排隊(duì)理論(講義)統(tǒng)計(jì)平穩(wěn)條件下的系統(tǒng)運(yùn)行指標(biāo)平均系統(tǒng)隊(duì)長(zhǎng)平均等待隊(duì)長(zhǎng)平均排隊(duì)等待時(shí)間平均系統(tǒng)逗留時(shí)間56排隊(duì)理論(講義)L,W,Lq,Wq的關(guān)系Little’sformulae♂57排隊(duì)理論(講義)M/M/1//或M/M/1模型一個(gè)基本的排列模型.顧客到達(dá)時(shí)間間隔以及服務(wù)時(shí)間都服從負(fù)指數(shù)分布，一個(gè)服務(wù)臺(tái)。

稱為服務(wù)強(qiáng)度，與到達(dá)率、服務(wù)率滿足：58排隊(duì)理論(講義)M/M/1舉例59排隊(duì)理論(講義)M/M/1/N/單一服務(wù)臺(tái)，固定長(zhǎng)度固定長(zhǎng)度排隊(duì)意味著若到了最大系統(tǒng)容量顧客將不能進(jìn)入系統(tǒng).60排隊(duì)理論(講義)M/M/1/N/舉例♂61排隊(duì)理論(講義)增加更多服務(wù)臺(tái)M/M/c所有服務(wù)臺(tái)是空的概率P0,和所有服務(wù)臺(tái)都在忙的概率P

,需要下面比較復(fù)雜的公式:62排隊(duì)理論(講義)M/M/c舉例♂63排隊(duì)理論(講義)其他模型，分類規(guī)則M/M/c/K/K顧客來(lái)源是有限的服務(wù)系統(tǒng).例如：一個(gè)飯店有X張桌子和Y個(gè)服務(wù)生服務(wù)來(lái)源有限的顧客.M/D/1服務(wù)時(shí)間不變的服務(wù)系統(tǒng).D/M/1確定性到達(dá)模式,及負(fù)指數(shù)分布服務(wù)時(shí)間.例如：醫(yī)生赴約治病的時(shí)間表.M/Ek/1服務(wù)服從Erlang分布.例如：用相同平均時(shí)間去完成一些程序?！?4排隊(duì)理論(講義)應(yīng)用：校園網(wǎng)的設(shè)計(jì)和調(diào)節(jié)收費(fèi)問題的提出：根據(jù)用戶數(shù)量研究通信端口的設(shè)計(jì)規(guī)模，以及通過適當(dāng)收取線路調(diào)節(jié)費(fèi)來(lái)控制上網(wǎng)時(shí)間。1）m個(gè)用戶，每個(gè)用戶平均每天（16h計(jì)）上網(wǎng)1.5h，求n/m。(n為通信端口數(shù))2）m=150,按設(shè)定的n討論平均每個(gè)用戶每天上網(wǎng)1h,1.5h,2h,3h,4h,5h的可能性，線路忙產(chǎn)生抱怨的可能性及通信端口的平均使用率3）給出一種合理的分段計(jì)時(shí)收取線路調(diào)節(jié)費(fèi)的方案。65排隊(duì)理論(講義)問題的分析：排隊(duì)系統(tǒng)：由信息網(wǎng)絡(luò)和用戶構(gòu)成服務(wù)臺(tái)：網(wǎng)絡(luò)的通信端口，個(gè)數(shù)n顧客：用戶，個(gè)數(shù)（顧客源數(shù)）m,顧客總體無(wú)限（因?yàn)樯暇W(wǎng)次數(shù)不限）平均忙期：一天連續(xù)工作實(shí)際時(shí)間，16h系統(tǒng)服務(wù)：即時(shí)制（只要時(shí)間允許，不限制上網(wǎng)人數(shù)，但不允許用戶在系統(tǒng)內(nèi)排隊(duì)等候）66排隊(duì)理論(講義)問題的假設(shè)：1）每個(gè)用戶上網(wǎng)隨機(jī)獨(dú)立，記

為單位時(shí)間平均到達(dá)（上網(wǎng)）率2）n個(gè)通信端口的使用隨機(jī)獨(dú)立，記

為單位時(shí)間平均服務(wù)率（上網(wǎng)人數(shù)）3）顧客接受一次服務(wù)后仍回顧客總體4）收費(fèi)僅為了調(diào)節(jié)線路，控制上網(wǎng)時(shí)間，不追求經(jīng)濟(jì)利益。5）不考慮現(xiàn)實(shí)生活中要收取的線路基本費(fèi)。67排隊(duì)理論(講義)模型的建立與求解：用戶平均上網(wǎng)人數(shù)（顧客平均到達(dá)率）服從參數(shù)為

的泊松分布平均上網(wǎng)（服務(wù)）時(shí)間服從參數(shù)為

的負(fù)指數(shù)分布排隊(duì)模型為:M/M/n/n/

（容量有限系統(tǒng)）顧客到達(dá)時(shí)間間隔分布/服務(wù)時(shí)間分布/

服務(wù)臺(tái)數(shù)目/

排隊(duì)系統(tǒng)允許的最大顧客容量/顧客總體數(shù)量/排隊(duì)規(guī)則68排隊(duì)理論(講義)模型求解：?jiǎn)栴}1，m個(gè)用戶，每個(gè)用戶平均每天（16h計(jì)）上網(wǎng)1.5h，求n/m。(n為通信端口數(shù))T:每天總上網(wǎng)時(shí)間69排隊(duì)理論(講義)問題2，m=150,按設(shè)定的n討論平均每個(gè)用戶每天上網(wǎng)1h,1.5h,2h,3h,4h,5h的可能性，線路忙產(chǎn)生抱怨的可能性及通信端口的平均使用率通常通信端口為16口、32口、64口、128口等每個(gè)用戶每天上網(wǎng)時(shí)間為1.5h時(shí)，即服務(wù)時(shí)間1/μ=1.570排隊(duì)理論(講義)系統(tǒng)滿員率：系統(tǒng)可上網(wǎng)率單位時(shí)間端口的平均使用率：71排隊(duì)理論(講義)=12.4263-16*0.3906*0.8837

=6.9035其它指標(biāo)值：72排隊(duì)理論(講義)♂73排隊(duì)理論(講義)UNIT2排隊(duì)網(wǎng)絡(luò)模型

在工程實(shí)踐中，除遇到孤立的排隊(duì)問題外，分析人員還經(jīng)常遇到多個(gè)互連排隊(duì)的問題，如顧客流的分開與合并，隊(duì)列的串并連組合等。排隊(duì)網(wǎng)絡(luò)模型就是來(lái)解決這些問題。

主要包括開環(huán)排隊(duì)網(wǎng)絡(luò)和閉環(huán)排隊(duì)網(wǎng)絡(luò)，具體應(yīng)用請(qǐng)查閱相關(guān)資料?！?4排隊(duì)理論(講義)QuickPass系統(tǒng)

排隊(duì)問題UNIT3應(yīng)用之：排隊(duì)理論(講義)在游樂園中的頻頻排隊(duì)會(huì)極為掃興……DisneyLand中的FastPass(QuickPass)系統(tǒng)就是想解決這個(gè)問題的76排隊(duì)理論(講義)WhatisQuickPass?工作原理：到達(dá)的顧客將自己的票插入FastPass的slot中FastPass計(jì)算出建議顧客返回的時(shí)間間隔(time

interval)或時(shí)間點(diǎn)或時(shí)間窗(timewindow)顧客無(wú)需排隊(duì)，在指定的時(shí)間返回就可持票進(jìn)入77排隊(duì)理論(講義)怎樣縮短排隊(duì)的等待時(shí)間？銀行的排隊(duì)叫號(hào)機(jī)只是有序的組織了顧客，并沒有減少等待時(shí)間如果能實(shí)現(xiàn)知道輪到自己需要等待多少時(shí)間，再選擇合適的時(shí)間來(lái)，豈不很好？

78排隊(duì)理論(講義)FastPass存在的問題：預(yù)知的返回時(shí)間間隔存在誤差－－按時(shí)返回卻仍需要排隊(duì)建議的返回時(shí)間間隔太長(zhǎng)－－如果告訴你4小時(shí)以后再回來(lái)呢？顧客可能不會(huì)完全按照安排的時(shí)間返回如果新來(lái)的顧客不想使用FastPass系統(tǒng)？79排隊(duì)理論(講義)我們的目的就是對(duì)FastPass系統(tǒng)建立

合理的離散統(tǒng)計(jì)模型（DistributedStatisticalModel），求出最優(yōu)的顧客返回時(shí)間。

建模的一般步驟以及：*模型的改進(jìn)*啟發(fā)與待解決的問題80排隊(duì)理論(講義)1模型的假設(shè)游樂園開放時(shí)間為8:00-18:00,一天中不同時(shí)間的顧客流量不同，比如上午10:00和下午3:00的顧客流量是最大的。顧客的到達(dá)時(shí)間符合非時(shí)間齊次泊松過程(NonhomogeneousPossionProcess)，到達(dá)速率是λ(t)。81排隊(duì)理論(講義)PoissonProcess82排隊(duì)理論(講義)PoissonProcess83排隊(duì)理論(講義)分析1：能否得到準(zhǔn)確的返回時(shí)間？

2在我們開始動(dòng)手建模之前，

先要問幾個(gè)問題：84排隊(duì)理論(講義)分析2：使用FastPass后排隊(duì)是不是可以避免的？FastPass給出的返回時(shí)間只是期望值，而非確定值假設(shè)所有的顧客都使用FastPass,但需考慮有的顧客可能會(huì)不遵守FastPass給出的返回時(shí)間

2在我們開始動(dòng)手建模之前，

先要問幾個(gè)問題：85排隊(duì)理論(講義)分析3：我們優(yōu)化的目標(biāo)函數(shù)（或costfunction）是什么？是排隊(duì)時(shí)間嗎？

2在我們開始動(dòng)手建模之前，

先要問幾個(gè)問題：86排隊(duì)理論(講義)優(yōu)化問題的目標(biāo)函數(shù)為：

3模型的建立（1）－目標(biāo)函數(shù)87排隊(duì)理論(講義)根據(jù)排隊(duì)論（queueingtheory）的分類規(guī)則,（X/Y/Z/A）代表一類排隊(duì)的規(guī)則，其中X:顧客流到達(dá)所符合的分布Y:顧客接受服務(wù)的時(shí)間所服從的分布Z:服務(wù)臺(tái)的個(gè)數(shù)A:服務(wù)臺(tái)一次可服務(wù)的顧客數(shù)量（系統(tǒng)的容量）針對(duì)各個(gè)游樂項(xiàng)目的特點(diǎn)，我們主要討論兩種排隊(duì)系統(tǒng):模型的建立（2）－排隊(duì)模型的分類88排隊(duì)理論(講義)特點(diǎn)：系統(tǒng)容量為1，顧客的到達(dá)是Poisson流，服務(wù)時(shí)間服從指數(shù)分布，只有一條隊(duì)列模型的建立（3）－電話亭模型89排隊(duì)理論(講義)求出這類系統(tǒng)的代價(jià)函數(shù)表達(dá)式模型的建立（3）－電話亭模型90排隊(duì)理論(講義)近似將總的優(yōu)化目標(biāo)函數(shù)等效為對(duì)顧客i的目標(biāo)函數(shù)：模型的建立（3）－電話亭模型91排隊(duì)理論(講義)模型的建立（3）－電話亭模型92排隊(duì)理論(講義)如果簡(jiǎn)化c1,c2為常數(shù)，并計(jì)算第二個(gè)人的無(wú)需等待返回時(shí)間的期望值，得用MatLab能夠作出的函數(shù)，并從圖中得出結(jié)果模型的求解（4）－電話亭模型93排隊(duì)理論(講義)模型的求解（4）－電話亭模型Averagecalltime(min*10’)U2t2508.051617.08023.051632.594排隊(duì)理論(講義)第三個(gè)人的無(wú)需等待返回時(shí)間的期望值，同理可以算出，并用圖解法求出模型的求解（4）－電話亭模型95排隊(duì)理論(講義)但是第4個(gè)人，第5個(gè)人……呢？這種方法太繁瑣似乎不好用可否有近似的算法？96排隊(duì)理論(講義)與前一個(gè)模型的區(qū)別在于：系統(tǒng)容量是c>1,服務(wù)時(shí)間固定，顧客的到達(dá)仍然是Poisson流。模型的建立（5）－過山車模型97排隊(duì)理論(講義)還要考慮：實(shí)際的FastPass系統(tǒng)有兩條隊(duì)列：FastPass和Standby隊(duì)列不考慮standby隊(duì)列，將得到Greedyalgorithm模型考慮standby隊(duì)列，將得到效用函數(shù)模型模型的建立（5）－過山車98排隊(duì)理論(講義)99排隊(duì)理論(講義)最簡(jiǎn)單的情況：只有一條隊(duì)列，即所有的人都只用FastPass系統(tǒng)為了防止前面的人等的時(shí)間太長(zhǎng)，過山車只要載滿一定數(shù)量的人后就開車，假設(shè)為80％c。用貪心算法（greedyalgorithm),將每個(gè)顧客盡量安排在離顧客到達(dá)時(shí)間最近的，且還沒有安排滿人的一班車上。假設(shè)被安排的顧客按照Beta分布到達(dá)所被安排的時(shí)間段內(nèi)模型的建立（5）－過山車模型100排隊(duì)理論(講義)貪心算法模型的建立（5）－過山車模型101排隊(duì)理論(講義)很容易想到，全局優(yōu)化的目標(biāo)變量

1.如果開車的時(shí)間不固定，則a%是多少最優(yōu)？就是說(shuō)顧客坐滿多少就開車？2.如果開車的時(shí)間間隔是固定的，則多長(zhǎng)時(shí)間開一次是最優(yōu)的？衡量的標(biāo)準(zhǔn)：目標(biāo)函數(shù)模型的建立（5）－過山車模型102排隊(duì)理論(講義)一個(gè)區(qū)間內(nèi)的顧客返回示意圖103排隊(duì)理論(講義)目標(biāo)函數(shù)：模型的建立（5）－過山車模型104排隊(duì)理論(講義)模型的建立（5）－過山車模型怎樣求解最優(yōu)的a%c和最優(yōu)的開