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

1、排隊(duì)論Queueing Theory,主講：周在瑩,排隊(duì)論課件,2,CONTENTS,PREPARATION:概率論與隨機(jī)過程 UNIT 1 排隊(duì)模型 UNIT 2 排隊(duì)網(wǎng)絡(luò)模型 UNIT 3 應(yīng)用之：QUICK PASS系統(tǒng) 結(jié)束語(yǔ),排隊(duì)論課件,3,PREPARATION 概率論和隨機(jī)過程,Part 1概率論基礎(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的

2、概率p。 總共有36種可能的結(jié)果，所以N= 36 有6種結(jié)果(1, 6), (2, 5), (3, 4), (4, 3), (5, 2)和(6, 1)為所求。 所以NA = 6， 從而 p = 6/36 =1/6,排隊(duì)論課件,4,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 ，有0P（A）1 （b） P（ ）=1 （c）

3、如果A和B是互斥的，則P（A U B）=P（A）+P（B,排隊(duì)論課件,5,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è)事件,排隊(duì)論課件,6,3 全概率公式和貝葉斯定理 全概率公式：給定一組互斥事件E1，E2，En，這些事件的并集包括所有可能的結(jié)果，同時(shí)給任一個(gè)任意事件A，那么全概率公式可以表示為： n P(A)=P(A|Ei)P(Ei) i=1 把計(jì)算A的概率分解為一些容易計(jì)算的概率之和。 貝

4、葉斯定理： P(Ei|A)= P(A|Ei)P(Ei) P(A|Ei)P(Ei) 也稱為后驗(yàn)概率公式，是在已知結(jié)果發(fā)生的情況下，求導(dǎo)致結(jié)果的某種原因的可能性的大小,排隊(duì)論課件,7,Part 2. 隨機(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ù)情況： EX = x =xf(x)dx 積分區(qū)間從-， 離散情況：EX =x = kPx=k all k 它是一種統(tǒng)計(jì)平均值，簡(jiǎn)稱均值 2 方差：DX=E(X-x)2=EX2-x2 它是

5、度量隨機(jī)變量X與其均值EX的偏離程度。 均方差：方差的開方稱為均方差，或標(biāo)準(zhǔn)方差，記為x 二階矩：連續(xù)情況： EX2 =x2f(x)dx 積分區(qū)間從-， 離散情況：EX2 = k2Px=k all k,排隊(duì)論課件,8,3 協(xié)方差：兩個(gè)隨機(jī)變量X和Y的協(xié)方差定義如下： Cov(X,Y)=E(X-x)(Y-y)=EXY-EXEY 4 相關(guān)系數(shù): 兩個(gè)隨機(jī)變量X和Y的相關(guān)系數(shù)定義如下： r(X,Y)=Cov(X,Y) /xy 相關(guān)系數(shù)是兩個(gè)隨機(jī)變量線性相關(guān)程度的度量。 例3：設(shè)隨機(jī)變量（X，Y）的分布律如下： Y X 1 2 1 -1 0 1/4 求 E(X),D(X),E(Y),D(Y),cov(

6、X,Y),r(X,Y,排隊(duì)論課件,9,Part 3 幾種重要的概率分布,1 貝努里分布 它的概率分布為：PX=1=p，PX=0=1-p 它也稱兩點(diǎn)分布或（0-1）分布。它描述一次貝努里實(shí)驗(yàn)中，成功或失敗的概率。 2 二項(xiàng)分布 PX=k=Cnkpk(1-p)n-k, k=0,1,n 它描述n次貝努里實(shí)驗(yàn)中事件A出現(xiàn)k次概率。 3 幾何分布 PX=k=p(1-p)k-1, k=1,2, 它描述在k次貝努里實(shí)驗(yàn)中首次出現(xiàn)成功的概率,排隊(duì)論課件,10,幾何分布有一個(gè)重要的性質(zhì)-后無效性：在前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)

7、首次成功的無條件概率。 用式子表達(dá)： PX=n+m | Xn=PX=m (請(qǐng)同學(xué)們?cè)囎C明之） 這種與過去歷史無關(guān)的性質(zhì)稱為馬爾可夫性。 幾何分布在我們下面講的排隊(duì)論中是非常重要。它可以描述某一任務(wù)（或顧客）的服務(wù)持續(xù)時(shí)間。 4 泊松分布（Poisson） PX = k = k e -/ k! k=0,1,2, 泊松分布是最重要的離散型概率分布之一，它作為表述隨機(jī)現(xiàn)象的一種形式，在計(jì)算機(jī)性能評(píng)價(jià)等實(shí)踐中扮演了重要的角色。 在實(shí)際系統(tǒng)模型中，一般都要假定任務(wù)（或顧客）的到來是服從泊松分布的。實(shí)踐也證明：這種假設(shè)是有效的,排隊(duì)論課件,11,5 （負(fù)）指數(shù)分布 它是一種連續(xù)型的概率分布，它的概率密度為

8、 f（x）= e-x x0 0 x0 ,t0 ，有 Ps+t|s=Pt 在離散型隨機(jī)變量中，只有幾何分布具有無后效性。這兩種分布可以分別用來描繪離散等待時(shí)間和連續(xù)等待時(shí)間。 在排隊(duì)理論中，指數(shù)分布是很重要的,排隊(duì)論課件,12,6 k-愛爾朗分布 概率密度: f(x)= (kx)n-1ke-kx /(n-1)! x0，0. 0 x0 數(shù)字特征： EX=1/; VarX=1/（k2 ） 如果k個(gè)隨機(jī)變量Xi，i=1，2，,k,分別服從指數(shù)分布，那么隨機(jī)變量X=X1+X2+ +Xk服從愛爾朗分布。即：具有k-愛爾朗分布的隨機(jī)變量可以看作具有同一指數(shù)分布的獨(dú)立的k個(gè)隨機(jī)變量之和。 k-愛爾朗分布在排隊(duì)

9、模型中，得到廣泛應(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 2 1 0000 窗口,排隊(duì)論課件,13,Part 4 隨機(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ù)或樣本曲線,排隊(duì)論課件,1

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

11、,15,Part 5 馬爾可夫過程,馬爾可夫過程(Markov Process)是具有無后效性的隨機(jī)過程。 無后效性是指：當(dāng)過程在tn時(shí)刻所處的狀態(tài)為已知時(shí)，過程在大于tn的時(shí)刻所處狀態(tài)的概率特性只與過程在tn時(shí)刻所處的狀態(tài)有關(guān)，而與過程在tn時(shí)刻以前的狀態(tài)無關(guān)。 換言之，對(duì)于隨機(jī)過程X（t），t T ，如果對(duì)于任意參數(shù) t0t1t2tn 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 此條件稱為過程

12、的無后效性或過程的馬爾可夫性。 t0 t1 tn-1 tn t,排隊(duì)論課件,16,Part 6 生滅過程,生滅過程是一種特殊類型的馬爾可夫過程，在系統(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)，t0 ，,稱為生滅過程。 時(shí)齊性 轉(zhuǎn)移概率Pij(t,)只與i,j,-t有關(guān)，即Pij()=Pij(t,t,排隊(duì)論課件,17,練習(xí),練習(xí)： 1。有10個(gè)電

13、阻，其電阻值分別為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ī)律,排隊(duì)論課件,18,習(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/6 2依題意，X的可能值為2，3，4，當(dāng)取中間號(hào)碼為k時(shí)，則另外兩只球必須分別在號(hào)碼小于k的k-1個(gè)中取一個(gè)

14、，和在號(hào)碼大于k的5-k個(gè)中取一個(gè)，于是： pk=PX=k=C(k-1,1)C(5-k,1) / C(5,3) , k=2,3,4 所以，X的分布律為： X 2 3 4 Pk 0.3 0.4 0.3,排隊(duì)論課件,19,UNIT1 排隊(duì)模型,排隊(duì)論（queueing theory），或稱隨機(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)用范圍不斷增加。概括起來，它已在電話交換網(wǎng)、公路

15、、鐵路、航空運(yùn)輸、工程管理、公共服務(wù)、貨物存儲(chǔ)和生產(chǎn)流水線過程等方面得到了廣泛的應(yīng)用。特別地，排隊(duì)論是計(jì)算機(jī)通信網(wǎng)絡(luò)和計(jì)算機(jī)系統(tǒng)中通信信息量研究的基礎(chǔ)理論，信息系統(tǒng)通信問題的定量研究往往要求借助于排對(duì)論才能得到解決,排隊(duì)論課件,20,排隊(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ì)論,排隊(duì)論課件,21,什么是

16、排隊(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)的理論,排隊(duì)論課件,22,本講主要掌握,基本模型 M/M/1 模型 M/M/c 模型 其他模型 應(yīng)用：校園網(wǎng)的設(shè)計(jì)和調(diào)節(jié)收費(fèi),排隊(duì)論課件,23,基本的排隊(duì)模型,基本組成 概念與記號(hào) 指數(shù)分布和生滅過程,排隊(duì)論課件,24,典型排隊(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ù)

17、，經(jīng)典排隊(duì)模型等內(nèi)容。顧客到達(dá)規(guī)律和服務(wù)規(guī)律都是通過概率來描述的，所以概率論是排隊(duì)論的基礎(chǔ),輸入源,排隊(duì)論課件,25,基本組成,排隊(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í)間分布等,排隊(duì)論課件,26,基本排隊(duì)模型 輸入過程,顧客來源 有限/無限 顧客數(shù)量 有限 無限 經(jīng)常性的顧客來源 顧客到達(dá)間隔時(shí)間: 到下一個(gè)顧客到達(dá)的時(shí)間. 服從某一概率分布. (指數(shù)分布) 顧客的行為假定 在未服務(wù)之前不會(huì)離開; 當(dāng)看到隊(duì)列很長(zhǎng)的時(shí)候離開； 從一個(gè)隊(duì)列移到另一個(gè)隊(duì)列,顧客到達(dá)

18、的方式通常是一個(gè)一個(gè)到達(dá)的，也可能是成批的。顧客的到達(dá)總是有一定規(guī)律，即到達(dá)過程或到達(dá)時(shí)間間隔符合一定的分布，稱到達(dá)分布。 顧客的到達(dá)或到達(dá)時(shí)間通常假定為相互獨(dú)立的且遵從同一分布的隨機(jī)變量,排隊(duì)論課件,27,基本排隊(duì)模型隊(duì)列/排隊(duì)規(guī)則,隊(duì)列 隊(duì)列容量 有限/無限 排隊(duì)方式 單隊(duì)列 并聯(lián)式多隊(duì)列 串聯(lián)式多隊(duì)列 雜亂隊(duì)列,對(duì)于一個(gè)有限大小的隊(duì)列來說，顧客可能從隊(duì)列中丟失。有什么樣的服務(wù)協(xié)議就有什么樣的與之對(duì)應(yīng)的排隊(duì)方式,排隊(duì)論課件,28,基本排隊(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ù)臺(tái)系統(tǒng) 服務(wù)協(xié)議 先來先服務(wù)（FCFS） 后來先服務(wù)

19、（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)行分析,排隊(duì)論課件,29,服務(wù)協(xié)議,a）先來先服務(wù) 顧客到達(dá)的先后次序排隊(duì)接受服務(wù)，用 FCFS（firstcomefirstserved）表示。 （b）后來先服務(wù)（或稱先來后服務(wù)） 隊(duì)列是一種堆棧形式（臨時(shí)寄存貨物的地方）。當(dāng)某一顧

20、客服務(wù)結(jié)束時(shí)，如果在隊(duì)列中有兩個(gè)以上等待的顧客，則把最后到達(dá)的顧客作為下一個(gè)服務(wù)的對(duì)象。用LCFS（lastcomefirstserved）表示。 （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）處理器共享（processor sharing， PS） 服務(wù)臺(tái)的處理能力被平均分配給隊(duì)列中的所有顧客，沒有排隊(duì)現(xiàn)象出現(xiàn)，當(dāng)顧客的數(shù)量增加時(shí)，只是顧客的服務(wù)時(shí)間變長(zhǎng)。如：網(wǎng)絡(luò)服務(wù)系

21、統(tǒng)。 （f）無限服務(wù)臺(tái)（infinite server， Is） 在這種情況下，隊(duì)列中的每個(gè)顧客接受完全相同的服務(wù)，而且就好像它是唯一的一個(gè)顧客一樣。好像對(duì)于每個(gè)顧客都可以“克隆”出一個(gè)新的服務(wù)臺(tái)，而且克隆的數(shù)目可以無限,排隊(duì)論課件,30,排隊(duì)系統(tǒng)的到達(dá)和服務(wù),1 到達(dá)規(guī)律的描述 （1）主要描述參數(shù) （a）到達(dá)時(shí)點(diǎn) 將某一時(shí)刻設(shè)為t0，顧客依次到達(dá)的時(shí)刻用t-1t0t1t2表示，如果在時(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ī)律

22、 顧客的到達(dá)規(guī)律可以用概率來描述，兩個(gè)顧客到達(dá)的時(shí)間間隔是獨(dú)立的隨機(jī)變量，服從同一概率分布時(shí)。常用的分布規(guī)律有： （a）一般到達(dá) （b）泊松到達(dá) （c）愛爾朗到達(dá) （d）等間隔到達(dá),排隊(duì)論課件,31,泊松分布和負(fù)指數(shù)分布在排隊(duì)論中的應(yīng)用,泊松分布（Poisson）： PX = k = k e-/ k! k=0,1,2,， x = x = 泊松分布是最重要的離散型概率分布之一，也是表述隨機(jī)現(xiàn)象的一種重要形式。在實(shí)際系統(tǒng)模型中，一般都要假定任務(wù)（或顧客）的到來是泊松分布的。實(shí)踐也證明：這種假設(shè)有效。 如果顧客到達(dá)的人數(shù)是符合泊松分布，即在時(shí)間T內(nèi)到達(dá)有k個(gè)顧客到達(dá)的概率為： p=（T）k e-T/

23、 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á)無關(guān),排隊(duì)論課件,32,負(fù)）指數(shù)分布： 它是一種連續(xù)型的概率分布，它的概率密度： f（x）=e-x x0 它的分布函數(shù)：F（x）=1-e-x x0 指數(shù)分布的一個(gè)有用的性質(zhì)是它的數(shù)學(xué)期望等于標(biāo)準(zhǔn)差：x = x = 1/ 泊松分布和指數(shù)分布的關(guān)系： 如果顧客以泊松到達(dá),則顧客到達(dá)的時(shí)間間隔Ta服從指數(shù)分布，即： PTat= 1-e-t , ETa=1/ 因此，平均到達(dá)的時(shí)間間隔是到達(dá)速率的倒數(shù),排隊(duì)

24、論課件,33,負(fù)指數(shù)分布,密度函數(shù),均值,方差,隨機(jī)變量 T（兩個(gè)顧客相繼到達(dá)的時(shí)間間隔,分布函數(shù),排隊(duì)論課件,34,負(fù)指數(shù)分布性質(zhì)1,fT(t) 是一個(gè)嚴(yán)格下降函數(shù),排隊(duì)論課件,35,負(fù)指數(shù)分布性質(zhì)2,無后效性（無記憶性,不管多長(zhǎng)時(shí)間(t)已經(jīng)過去， 逗留時(shí)間的概率分布與下一個(gè)事件的相同.或者說，后一個(gè)顧客到來所需時(shí)間與前一個(gè)顧客到來所需時(shí)間無關(guān),排隊(duì)論課件,36,負(fù)指數(shù)分布性質(zhì)3,幾個(gè)獨(dú)立的指數(shù)分布的隨機(jī)變量的最小也服從指數(shù)分布,幾個(gè)獨(dú)立的指數(shù)分布的隨機(jī)變量的和還是一個(gè)服從指數(shù)分布的隨機(jī)變量,排隊(duì)論課件,37,負(fù)指數(shù)分布性質(zhì)4,負(fù)指數(shù)分布,Poisson分布,在t時(shí)間內(nèi)已經(jīng)服務(wù)n個(gè)顧客的概

25、率,1/: 平均服務(wù)時(shí)間,平均服務(wù)率=,相繼顧客到達(dá)平均間隔時(shí)間,排隊(duì)論課件,38,負(fù)指數(shù)分布性質(zhì)5,排隊(duì)論課件,39,排隊(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ī)則的影響,排隊(duì)論課件,40,2 服務(wù)

26、規(guī)律的描述,1)主要描述參量 （a）平均服務(wù)時(shí)間 設(shè)服務(wù)時(shí)間的分布函數(shù)為F（t），則服務(wù)時(shí)間的平均表示為: 1/=t dF(t) 其中稱為平均服務(wù)速率，平均一個(gè)顧客的服務(wù)時(shí)間。 （b）服務(wù)速率 一般指平均服務(wù)速率，單位時(shí)間內(nèi)被服務(wù)完的顧客數(shù)，用來表示。 (2)服務(wù)規(guī)律 服務(wù)規(guī)律通常是就服務(wù)時(shí)間的分布而言的。服務(wù)時(shí)間分布典型地有指數(shù)分布、愛爾朗分布、一般分布等。 結(jié)論：顧客到達(dá)規(guī)律和服務(wù)規(guī)律都是通過概率來描述的，所以概率論是排隊(duì)論的基礎(chǔ),排隊(duì)論課件,41,經(jīng)典排隊(duì)模型,它的格式為： ABnSZ 其中符號(hào)的含義如下： A：顧客到達(dá)的規(guī)律；B：服務(wù)時(shí)間分布；n：服務(wù)臺(tái)的數(shù)目； S：隊(duì)列容量的大小；Z

27、：服務(wù)規(guī)程。 當(dāng)隊(duì)列的大小為無窮大、且服務(wù)規(guī)程為先來先服務(wù)時(shí)，經(jīng)典排隊(duì)模型可簡(jiǎn)化為 ABn 不同類型的排隊(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：先來先服務(wù)；LCFS

28、：后來先服務(wù)；RSS：隨機(jī)選擇服務(wù)； PR：優(yōu)先權(quán)服務(wù)。 Ba：集體（批量）服務(wù)。 GD：一般規(guī)約服務(wù)，即通用規(guī)約服務(wù),排隊(duì)論課件,42,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ì)永無顧客到達(dá)。 則下列 Little 公式成立（排隊(duì)論中的通用公式）： （1） Lq = Wq 我們知道一個(gè)顧客的平均排隊(duì)等待時(shí)間是Wq，且顧客是以平均速率到達(dá)，所以在時(shí)間Wq內(nèi)有Wq個(gè)顧客到達(dá)， Lq表示排

29、隊(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í)間,排隊(duì)論課件,43,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ì)分析中

30、，最重要的一個(gè)假設(shè)是到達(dá)速率服從泊松分布，等效的說法是到達(dá)間隔時(shí)間服從指數(shù)分布，這又等價(jià)于說到達(dá)是隨機(jī)的并彼此獨(dú)立。我們幾乎一直要作這一假定。沒有它，大部分的排隊(duì)分析是不可能的。在這個(gè)假定的條件下，我們會(huì)發(fā)現(xiàn)僅僅知道到達(dá)速率和服務(wù)時(shí)間的均值和標(biāo)準(zhǔn)差就可以得到許多有用的結(jié)果,排隊(duì)論課件,44,模型之： 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ì)列的解

31、釋為：顧客代表消息，而服務(wù)臺(tái)代表通信信道,排隊(duì)論課件,45,隨機(jī)過程和概率論在排隊(duì)論中的應(yīng)用,1.把排隊(duì)過程看成生滅過程 如果N（t）表示時(shí)刻 t 系統(tǒng)中的顧客數(shù)，則N（t），t 0就構(gòu)成了一個(gè)隨機(jī)過程。如果用“生”表示顧客的到達(dá)，“滅”表示顧客的離去，則對(duì)許多排隊(duì)過程來說，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)

32、, 穩(wěn)定狀態(tài)概率服從參數(shù)為1- 的改進(jìn)型幾何分布。 3. 由幾何分布可以得到系統(tǒng)中平均顧客數(shù)量和等待時(shí)間 幾何分布：PX=k=p(1-p)k-1, k=1,2, 幾何分布的數(shù)學(xué)期望為：1/p, 方差為: q / p2 令 p= 1- , 計(jì)算出系統(tǒng)中顧客數(shù)量的均值和方差 ： L=EN= /(1- ) VarN= /(1- ) 2 令隨機(jī)變量R代表穩(wěn)定狀態(tài)的響應(yīng)時(shí)間，即一個(gè)顧客在系統(tǒng)中花費(fèi)的時(shí)間， 則W=ER，根據(jù)L=W，可以得到:W=1/(1-,排隊(duì)論課件,46,隨機(jī)過程和概率論在排隊(duì)論中的應(yīng)用,4. 由系統(tǒng)中顧客平均數(shù)量和等待時(shí)間得隊(duì)列中顧客數(shù)量w和等待時(shí)間Tw 令隨機(jī)變量Wt代表等待時(shí)間，

33、St代表服務(wù)時(shí)間，則：R=Wt+St ER=EWt+ESt =EWt+1/ 所以顧客的平均等待時(shí)間Wq=EWt =ER- 1/ = /( 1-) 即：Wq = /( 1-) 令隨機(jī)變量Wi表示隊(duì)列中正在等待的顧客數(shù)量， 再根據(jù)little公式，Lq=EWi= *EWt = * /( 1-) =2 /( 1-) 即： Lq=2 /( 1,排隊(duì)論課件,47,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公式

34、： = 1/, L=Lq+ 通用的little公式： Lq=Wq L=W W=Wq+ 1,排隊(duì)論課件,48,M/M/1 模型練習(xí),練習(xí)2： 1 一個(gè)書店平均每分鐘有3個(gè)顧客到達(dá)，正常情況有48個(gè)顧客在書店中，求每一個(gè)顧客在商店花費(fèi)的平均時(shí)間？ 2 一條通信線路的帶寬是2000位/秒，該線路用來傳8位一個(gè)的字符，所以該線路的最大速率是250字符/秒,來自應(yīng)用要求是12000字符/分。 求：（1）等待被傳輸?shù)钠骄址麛?shù)Lq, （2）每個(gè)字符平均傳輸時(shí)間W. 3 假定一個(gè)電話通話的持續(xù)時(shí)間平均3分鐘，一個(gè)人等待電話平均最大可以忍耐3分鐘，求可以支持的最大呼叫量,排隊(duì)論課件,49,M/M/1模型練習(xí),

35、4。某修理店只有一個(gè)修理工，來修理的顧客到達(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ù)量的均值和方差 ： EN= /(1- ) VarN= /(1- ) 2 M/M/1 隊(duì)列中一般的公式： L=EN,

36、 W=1/( 1-) ，Wq= /( 1-) ，Lq= 2 /( 1-) 在單服務(wù)員系統(tǒng)中的little公式： = 1/, L=Lq+ 通用的little公式： Lq=Wq L=W W=Wq+ 1/ 顧客在系統(tǒng)中的逗留時(shí)間T，服從參數(shù)為-的負(fù)指數(shù)分布，即：PTt=e ( - )t,排隊(duì)論課件,50,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)，可

37、以得到下面在M/M/c隊(duì)列中的常用公式,C個(gè)服務(wù)臺(tái),排隊(duì)論課件,51,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,分別為,排隊(duì)論課件,52,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ù)量，EM=c= / 所以，任意一個(gè)服務(wù)臺(tái)的利用率= /（c） 在多服務(wù)臺(tái)系統(tǒng)中的Little公式： = /（c） ，

38、L=Lq+ c,請(qǐng)同學(xué)們思考： 一個(gè)M/M/c系統(tǒng)與c個(gè)M/M/1系統(tǒng)比較，那一種效率高,排隊(duì)論課件,53,基本排隊(duì)模型記號(hào)方案,顧客到達(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: 普通的概率分布 (任意概率分布,排隊(duì)論課件,54,基本排隊(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ì)列

39、長(zhǎng)度。 Pn(t) =在時(shí)間t,排隊(duì)系統(tǒng)中恰好有n個(gè)顧客的概率。 s = 服務(wù)臺(tái)的數(shù)目,排隊(duì)論課件,55,基本排隊(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)度， 或稱使用因子，,排隊(duì)論課件,56,統(tǒng)計(jì)平穩(wěn)條件下的系統(tǒng)運(yùn)行指標(biāo),平均系統(tǒng)隊(duì)長(zhǎng),平均等待隊(duì)長(zhǎng),平均排隊(duì)等待時(shí)間,平均系統(tǒng)逗留時(shí)間,排隊(duì)論課件,57,L, W, Lq, W

40、q的關(guān)系,Littles formulae,排隊(duì)論課件,58,M/M/1/ 或 M/M/1 模型,一個(gè)基本的排列模型. 顧客到達(dá)時(shí)間間隔以及服務(wù)時(shí)間都服從負(fù)指數(shù)分布，一個(gè)服務(wù)臺(tái)。 稱為服務(wù)強(qiáng)度，與到達(dá)率 、服務(wù)率 滿足,排隊(duì)論課件,59,M/M/1 舉例,排隊(duì)論課件,60,M/M/1/N/單一服務(wù)臺(tái)，固定長(zhǎng)度,固定長(zhǎng)度排隊(duì)意味著若到了最大系統(tǒng)容量顧客將不能進(jìn)入系統(tǒng),排隊(duì)論課件,61,M/M/1/N/ 舉例,排隊(duì)論課件,62,增加更多服務(wù)臺(tái) M/M/c,所有服務(wù)臺(tái)是空的概率P0,和所有服務(wù)臺(tái)都在忙的概率 P,需要下面比較復(fù)雜的公式,排隊(duì)論課件,63,M/M/c 舉例,排隊(duì)論課件,64,其他模型，

41、分類規(guī)則,M/M/c/K/K 顧客來源是有限的服務(wù)系統(tǒng). 例如： 一個(gè)飯店有 X 張桌子和 Y個(gè)服務(wù)生服務(wù)來源有限的顧客. M/D/1 服務(wù)時(shí)間不變的服務(wù)系統(tǒng). D/M/1 確定性到達(dá)模式, 及負(fù)指數(shù)分布服務(wù)時(shí)間. 例如：醫(yī)生赴約治病的時(shí)間表. M/Ek/1 服務(wù)服從 Erlang 分布. 例如：用相同平均時(shí)間去完成一些程序,排隊(duì)論課件,65,應(yīng)用：校園網(wǎng)的設(shè)計(jì)和調(diào)節(jié)收費(fèi),問題的提出： 根據(jù)用戶數(shù)量研究通信端口的設(shè)計(jì)規(guī)模，以及通過適當(dāng)收取線路調(diào)節(jié)費(fèi)來控制上網(wǎng)時(shí)間。 1）m個(gè)用戶，每個(gè)用戶平均每天（16h計(jì)）上網(wǎng)1.5h，求n/m。(n為通信端口數(shù)) 2）m=150,按設(shè)定的n討論平均每個(gè)用戶每

42、天上網(wǎng)1h,1.5h,2h,3h,4h,5h的可能性，線路忙產(chǎn)生抱怨的可能性及通信端口的平均使用率 3）給出一種合理的分段計(jì)時(shí)收取線路調(diào)節(jié)費(fèi)的方案,排隊(duì)論課件,66,問題的分析,排隊(duì)系統(tǒng)：由信息網(wǎng)絡(luò)和用戶構(gòu)成 服務(wù)臺(tái) ：網(wǎng)絡(luò)的通信端口，個(gè)數(shù)n 顧客：用戶，個(gè)數(shù)（顧客源數(shù)）m,顧客總體無限（因?yàn)樯暇W(wǎng)次數(shù)不限） 平均忙期：一天連續(xù)工作實(shí)際時(shí)間，16h 系統(tǒng)服務(wù)：即時(shí)制（只要時(shí)間允許，不限制上網(wǎng)人數(shù)，但不允許用戶在系統(tǒng)內(nèi)排隊(duì)等候,排隊(duì)論課件,67,問題的假設(shè),1）每個(gè)用戶上網(wǎng)隨機(jī)獨(dú)立， 記 為單位時(shí)間平均到達(dá)（上網(wǎng)）率 2）n個(gè)通信端口的使用隨機(jī)獨(dú)立，記 為單位時(shí)間平均服務(wù)率（上網(wǎng)人數(shù)） 3）顧客接

43、受一次服務(wù)后仍回顧客總體 4）收費(fèi)僅為了調(diào)節(jié)線路，控制上網(wǎng)時(shí)間，不追求經(jīng)濟(jì)利益。 5）不考慮現(xiàn)實(shí)生活中要收取的線路基本費(fèi),排隊(duì)論課件,68,模型的建立與求解,用戶平均上網(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ī)則,排隊(duì)論課件,69,模型求解,問題1，m個(gè)用戶，每個(gè)用戶平均每天（16h計(jì)）上網(wǎng)1.5h，求n/m。(n為通信端口數(shù)) T:每天總上網(wǎng)時(shí)間,排隊(duì)論課件,70,問題2，m=150,按設(shè)定的

44、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.5,排隊(duì)論課件,71,系統(tǒng)滿員率,系統(tǒng)可上網(wǎng)率,單位時(shí)間端口的平均使用率,排隊(duì)論課件,72,12.4263-16*0.3906*0.8837= 6.9035,其它指標(biāo)值,排隊(duì)論課件,73,排隊(duì)論課件,74,UNIT2 排隊(duì)網(wǎng)絡(luò)模型,在工程實(shí)踐中，除遇到孤立的排隊(duì)問題外，分析人員還經(jīng)常遇到多個(gè)互連排隊(duì)的問題，如顧客流的分開與合并，隊(duì)列的串并連組合等。排隊(duì)網(wǎng)絡(luò)模型就是來解決這些

45、問題。 主要包括開環(huán)排隊(duì)網(wǎng)絡(luò)和閉環(huán)排隊(duì)網(wǎng)絡(luò)，具體應(yīng)用請(qǐng)查閱相關(guān)資料,QuickPass系統(tǒng)排隊(duì)問題,UNIT3 應(yīng)用之,排隊(duì)論課件,76,在游樂園中的頻頻排隊(duì) 會(huì)極為掃興 DisneyLand中 的FastPass (QuickPass)系統(tǒng) 就是想解決這 個(gè)問題的,排隊(duì)論課件,77,What is QuickPass,工作原理： 到達(dá)的顧客將自己的票插入FastPass的slot中 FastPass計(jì)算出建議顧客返回的時(shí)間間隔(time interval) 或時(shí)間點(diǎn)或時(shí)間窗(time window) 顧客無需排隊(duì)，在指定的時(shí)間返回就可持票進(jìn)入,排隊(duì)論課件,78,怎樣縮短排隊(duì)的等待時(shí)間,銀行的

46、排隊(duì)叫號(hào)機(jī) 只是有序的組織了顧客，并沒有減少等待時(shí)間 如果能實(shí)現(xiàn)知道輪到自己需要等待多少時(shí)間，再選擇合適的時(shí)間來，豈不很好,排隊(duì)論課件,79,FastPass存在的問題,預(yù)知的返回時(shí)間間隔存在誤差 按時(shí)返回卻仍需要排隊(duì) 建議的返回時(shí)間間隔太長(zhǎng) 如果告訴你4小時(shí)以后再回來呢？ 顧客可能不會(huì)完全按照安排的時(shí)間返回 如果新來的顧客不想使用FastPass系統(tǒng),排隊(duì)論課件,80,我們的目的就是對(duì)FastPass系統(tǒng)建立合理的離散統(tǒng)計(jì)模型（Distributed Statistical Model），求出最優(yōu)的顧客返回時(shí)間,建模的一般步驟 以及： * 模型的改進(jìn) * 啟發(fā)與待解決的問題,排隊(duì)論課件,81

47、,1 模型的假設(shè),游樂園開放時(shí)間為8:00-18:00,一天中不同時(shí)間的顧客流量不同，比如上午10:00和下午3:00的顧客流量是最大的。 顧客的到達(dá)時(shí)間符合非時(shí)間齊次泊松過程(Nonhomogeneous Possion Process)，到達(dá)速率是(t,排隊(duì)論課件,82,Poisson Process,排隊(duì)論課件,83,Poisson Process,排隊(duì)論課件,84,分析1：能否得到準(zhǔn)確的返回時(shí)間,2 在我們開始動(dòng)手建模之前，先要問幾個(gè)問題,排隊(duì)論課件,85,分析2：使用FastPass后排隊(duì)是不是可以避免的？ FastPass給出的返回時(shí)間只是期望值，而非確定值 假設(shè)所有的顧客都使用F

48、astPass,但需考慮有的顧客可能會(huì)不遵守FastPass給出的返回時(shí)間,2 在我們開始動(dòng)手建模之前，先要問幾個(gè)問題,排隊(duì)論課件,86,分析3：我們優(yōu)化的目標(biāo)函數(shù)（或cost function）是什么？是排隊(duì)時(shí)間嗎,2 在我們開始動(dòng)手建模之前，先要問幾個(gè)問題,排隊(duì)論課件,87,優(yōu)化問題的目標(biāo)函數(shù)為,3 模型的建立（1）目標(biāo)函數(shù),排隊(duì)論課件,88,根據(jù)排隊(duì)論（queueing theory）的分類規(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)

49、，我們主要討論兩種排隊(duì)系統(tǒng),模型的建立（2） 排隊(duì)模型的分類,排隊(duì)論課件,89,特點(diǎn)：系統(tǒng)容量為1，顧客的到達(dá)是Poisson流，服務(wù)時(shí)間服從指數(shù)分布，只有一條隊(duì)列,模型的建立（3） 電話亭模型,排隊(duì)論課件,90,求出這類系統(tǒng)的代價(jià)函數(shù)表達(dá)式,模型的建立（3）電話亭模型,排隊(duì)論課件,91,近似將總的優(yōu)化目標(biāo)函數(shù)等效為對(duì)顧客i的目標(biāo)函數(shù),模型的建立（3）電話亭模型,排隊(duì)論課件,92,模型的建立（3）電話亭模型,排隊(duì)論課件,93,如果簡(jiǎn)化c1,c2為常數(shù)，并計(jì)算第二個(gè)人的無需等待返回時(shí)間的期望值，得 用MatLab能夠作出 的函數(shù)，并從圖中得出結(jié)果,模型的求解（4）電話亭模型,排隊(duì)論課件,94,模

50、型的求解（4）電話亭模型,排隊(duì)論課件,95,第三個(gè)人的無需等待返回時(shí)間的期望值，同理可以算出，并用圖解法求出,模型的求解（4）電話亭模型,排隊(duì)論課件,96,但是第4個(gè)人，第5個(gè)人呢？ 這種方法太繁瑣似乎不好用 可否有近似的算法,排隊(duì)論課件,97,與前一個(gè)模型的區(qū)別在于：系統(tǒng)容量是c1,服務(wù)時(shí)間固定，顧客的到達(dá)仍然是Poisson流,模型的建立（5） 過山車模型,排隊(duì)論課件,98,還要考慮： 實(shí)際的FastPass系統(tǒng) 有兩條隊(duì)列： FastPass和Standby隊(duì)列 不考慮standby隊(duì)列， 將得到Greedy algorithm模型 考慮standby隊(duì)列， 將得到效用函數(shù)模型,模型的建

51、立（5）過山車,排隊(duì)論課件,99,排隊(duì)論課件,100,最簡(jiǎn)單的情況： 只有一條隊(duì)列，即所有的人都只用FastPass系統(tǒng) 為了防止前面的人等的時(shí)間太長(zhǎng)，過山車只要載滿一定數(shù)量的人后就開車，假設(shè)為80c。 用貪心算法（greedy algorithm),將每個(gè)顧客盡量安排在離顧客到達(dá)時(shí)間最近的，且還沒有安排滿人的一班車上。 假設(shè)被安排的顧客按照Beta分布到達(dá)所被安排的時(shí)間段內(nèi),模型的建立（5）過山車模型,排隊(duì)論課件,101,貪心算法,模型的建立（5）過山車模型,排隊(duì)論課件,102,很容易想到，全局優(yōu)化的目標(biāo)變量 1. 如果開車的時(shí)間不固定，則a%是多少最優(yōu)？就是說顧客坐滿多少就開車？ 2.如果

52、開車的時(shí)間間隔是固定的，則多長(zhǎng)時(shí)間開一次是最優(yōu)的？ 衡量的標(biāo)準(zhǔn)：目標(biāo)函數(shù),模型的建立（5）過山車模型,排隊(duì)論課件,103,一個(gè)區(qū)間內(nèi)的顧客返回示意圖,排隊(duì)論課件,104,目標(biāo)函數(shù),模型的建立（5）過山車模型,排隊(duì)論課件,105,模型的建立（5）過山車模型,怎樣求解最優(yōu)的a%c和最優(yōu)的開車間隔？ 對(duì)于這類復(fù)雜的問題，離散仿真是最好 的方法了,排隊(duì)論課件,106,仿真：用計(jì)算機(jī)生成一些符合某種分布的隨機(jī)數(shù)據(jù)點(diǎn)，模擬離散時(shí)間的發(fā)生 這里的仿真用MatLab完成： 步驟：1.生成Poisson顧客流（模擬到達(dá)時(shí)間） 2.給定不同的a%c, 開車時(shí)間間隔不定，計(jì)算代價(jià)函數(shù)，畫出代價(jià)函數(shù)性能曲線 3.開車時(shí)間固定，給出不同的開車時(shí)間間隔，計(jì)算畫出代價(jià)函數(shù)性能曲線 4.得出最優(yōu)的結(jié)論,模型的仿真（5）過山車模型,排隊(duì)論課件,107,過山車模型的仿真（5.1）得到,在第j天的某一固 定時(shí)刻 i 采集樣本, i=1m, j=1100 形成樣本空間的 矩陣,排隊(duì)論課件,108,過山車模型的仿真（5.1,用列向量的均值 估計(jì)參數(shù) 樣本的更新用時(shí)間序