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

2、的結(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） 如果A和B是互斥的，則P（A U B

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

4、) P(A|Ei)P(Ei) 也稱為后驗(yàn)概率公式，是在已知結(jié)果發(fā)生的情況下，求導(dǎo)致結(jié)果的某種原因的可能性的大小。排隊(duì)論課件7Part 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ì)平均值，簡稱均值2 方差：DX=E(X-x)2=EX2-x2 它是度量隨機(jī)變量X與其均值EX的偏離程度。 均方差：方差的開方稱為均方差

5、，或標(biāo)準(zhǔn)方差，記為x 二階矩：連續(xù)情況： EX2 =x2f(x)dx 積分區(qū)間從-， 離散情況：EX2 = k2Px=k all k排隊(duì)論課件83 協(xié)方差：兩個(gè)隨機(jī)變量X和Y的協(xié)方差定義如下： Cov(X,Y)=E(X-x)(Y-y)=EXY-EXEY4 相關(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(X,Y),r(X,Y)排隊(duì)論課件9Part 3 幾種重要的概率分布 1 貝努里分

6、布它的概率分布為：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)首次成功的無條件概率。 用式子表達(dá)：PX=n+m | Xn=PX=m (請(qǐng)同學(xué)們?cè)囎C明之）這種與

7、過去歷史無關(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ì)論課件115 （負(fù)）指數(shù)分布 它是一種連續(xù)型的概率分布，它的概率密度為 f（x）= e-x x0 0 x0 ,t0 ，有 Ps+t|s=Pt 在離散型隨機(jī)變量中，只有幾何分布具有無后效

8、性。這兩種分布可以分別用來描繪離散等待時(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ì)模型中，得到廣泛應(yīng)用。如：假定顧客在到達(dá)窗口排隊(duì)必須通過一個(gè)關(guān)口，這個(gè)關(guān)口由k層構(gòu)成，通過每層的時(shí)間服從參數(shù)為的指數(shù)分布

9、，這樣顧客通過整個(gè)關(guān)口到達(dá)窗口排隊(duì)時(shí)，就實(shí)現(xiàn)了愛爾朗分布。 如下圖： k 2 1 0000 窗口排隊(duì)論課件13Part 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ì)論課件14隨機(jī)過程的例子 為了更好的理解隨機(jī)過程，我們從一個(gè)例子開始。例如， n個(gè)同樣的電阻，同時(shí)記錄它們熱噪聲的電壓波形。 電阻上的熱

10、噪聲是由于電阻中的電子的熱運(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ì)論課件15Part 5 馬爾可夫過程馬爾可夫過程(Markov Process)是具有無后效性的隨機(jī)過程。無后效性是指：當(dāng)過程在tn時(shí)

11、刻所處的狀態(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 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è)電阻，其電阻值分別為1，2，10，從中取出三個(gè)，要求取出的三個(gè)電阻，一個(gè)小于5，一個(gè)等于5，另一個(gè)大于5，問：取一次就能達(dá)到要求的概率。

12、 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），有利場合為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=PX=k=C(k-1,1)C(5-k,1) / C(5,3) , k=2,3,4 所以，X的

13、分布律為： X 2 3 4 Pk 0.3 0.4 0.3排隊(duì)論課件19UNIT1 排隊(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)、公路、鐵路、航空運(yùn)輸、工程管理、公共服務(wù)、貨物存儲(chǔ)和生產(chǎn)流水線過程等方面得到了廣泛的應(yīng)用。特別地，排隊(duì)論是計(jì)算機(jī)通信網(wǎng)絡(luò)和計(jì)算機(jī)系統(tǒng)中通信信息量研究的基

14、礎(chǔ)理論，信息系統(tǒng)通信問題的定量研究往往要求借助于排對(duì)論才能得到解決。排隊(duì)論課件20排隊(duì)常常是件很令人惱火的事情尤其是在我們這樣的人口大國電話亭1978年在北京15%的電話要在1小時(shí)后才能接通。在電報(bào)大樓打電話的人還要帶著午飯去排隊(duì) 銀行窗口，ATM游樂場的游樂項(xiàng)目醫(yī)院、理發(fā)、火車售票在現(xiàn)實(shí)生活中，為了接受某種服務(wù)，排隊(duì)等待是常見的現(xiàn)象。從排隊(duì)等待得到抽象的物理模型，進(jìn)一步建立數(shù)學(xué)模型的一整套理論就是所謂的排隊(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)的理論。排

15、隊(duì)論課件21排隊(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ù)，經(jīng)典排隊(duì)模型等內(nèi)容。顧客到達(dá)規(guī)律和服務(wù)規(guī)律都是通過概率來描述的，所以概率論是排隊(duì)論的基礎(chǔ)。輸入源。排隊(duì)論課件25基本組成輸入來源隊(duì) 列服務(wù)機(jī)構(gòu)排隊(duì)系統(tǒng)顧客服務(wù)完離開排隊(duì)系統(tǒng)的三個(gè)基本組成部分.輸入

16、過程 (顧客按照怎樣的規(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ì)列很長的時(shí)候離開；從一個(gè)隊(duì)列移到另一個(gè)隊(duì)列。 顧客到達(dá)的方式通常是一個(gè)一個(gè)到達(dá)的，也可能是成批的。顧客的到達(dá)總是有一定規(guī)律，即到達(dá)過程或到達(dá)時(shí)間間隔符合一定的分布，稱到達(dá)分布。 顧客的到達(dá)或到達(dá)時(shí)間通常假定為相互獨(dú)立的且遵從同一分布的隨機(jī)變量

17、。排隊(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ù)（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í)間長短不一。 將服務(wù)時(shí)間看作隨機(jī)變量，那么它們是相互獨(dú)立的且遵循

18、同一分布。因此描述服務(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)某一顧客服務(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ù)

19、 預(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í)間變長。如：網(wǎng)絡(luò)服務(wù)系統(tǒng)。 （f）無限服務(wù)臺(tái)（infinite server， Is） 在這種情況下，隊(duì)列中的每個(gè)顧客接受完全相同的服務(wù)，而且就好像它是唯一的一個(gè)顧客一樣。好像對(duì)于每個(gè)顧客都可以“克隆”出一個(gè)新的服務(wù)臺(tái)，而且克隆的數(shù)目可以無限。排隊(duì)論課件30排隊(duì)系

20、統(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ī)律 顧客的到達(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 =

21、 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/ 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ù)型的概率分布，它的概率密

22、度： 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ì)論課件33負(fù)指數(shù)分布密度函數(shù)均值方差隨機(jī)變量 T（兩個(gè)顧客相繼到達(dá)的時(shí)間間隔）分布函數(shù)fT(t)t排隊(duì)論課件34負(fù)指數(shù)分布性質(zhì)1fT(t)tttfT(t) 是一個(gè)嚴(yán)格下降函數(shù)排隊(duì)論課件35負(fù)指數(shù)分布性質(zhì)2無后效性（無記憶性）不管多長時(shí)間(t)已經(jīng)過去， 逗留時(shí)間的概率分布與下一

23、個(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ī)變量T1(1)T1(2)T1(3)T (1 +2 +3)排隊(duì)論課件37負(fù)指數(shù)分布性質(zhì)4負(fù)指數(shù)分布Poisson分布 在t時(shí)間內(nèi)已經(jīng)服務(wù)n個(gè)顧客的概率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ī)場起飛

24、的客機(jī) （4）十字路口紅燈前的車輛 2。判斷正誤 （1）若到達(dá)排隊(duì)系統(tǒng)的顧客人數(shù)服從泊松分布，則依次到達(dá)的兩名顧客之間的間隔時(shí)間服從指數(shù)分布。 （2）在一個(gè)排隊(duì)系統(tǒng)中，不管顧客到達(dá)和服務(wù)時(shí)間的情況如何，只要運(yùn)行時(shí)間足夠長的時(shí)間后，系統(tǒng)將進(jìn)入穩(wěn)定狀態(tài)。 （3）在排隊(duì)系統(tǒng)中，顧客等待時(shí)間的分布不受排隊(duì)規(guī)則的影響。 排隊(duì)論課件402 服務(wù)規(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ī)律

25、 服務(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：服務(wù)規(guī)程。 當(dāng)隊(duì)列的大小為無窮大、且服務(wù)規(guī)程為先來先服務(wù)時(shí)，經(jīng)典排隊(duì)模型可簡化為 ABn 不同類型的排隊(duì)，A、B可用如下約定的字母表示。 M：如果用于描述到達(dá)，表示泊松到達(dá)過程，到達(dá)時(shí)間間隔符合指數(shù)分布；如 果用于描述服務(wù)，則指具有指數(shù)分布的時(shí)間。M表示Markov的第

26、一個(gè)字母。 G：一般分布。表示到達(dá)間隔時(shí)間或服務(wù)時(shí)間服從一般分布。G是General的第 一個(gè)字母。 Ek：k-愛爾朗分布。表示到達(dá)間隔時(shí)間或服務(wù)時(shí)間服從k-愛爾朗分布。E是Erlang 的第一個(gè)字母。 D: 定長分布 (常數(shù)時(shí)間) H：超幾何分布。 L：H項(xiàng)式分布。 Z代表的服務(wù)規(guī)程典型的有： FCFS：先來先服務(wù)；LCFS：后來先服務(wù)；RSS：隨機(jī)選擇服務(wù)； PR：優(yōu)先權(quán)服務(wù)。 Ba：集體（批量）服務(wù)。 GD：一般規(guī)約服務(wù)，即通用規(guī)約服務(wù)。排隊(duì)論課件423 基本排隊(duì)關(guān)系在對(duì)排隊(duì)進(jìn)行分析時(shí)，為了便于分析，經(jīng)常做一些簡化假設(shè)。對(duì)一個(gè)排隊(duì)系統(tǒng)，若滿足以下三個(gè)條件：（1）排隊(duì)系統(tǒng)能夠進(jìn)入統(tǒng)計(jì)平衡狀

27、態(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表示排隊(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ì)論

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

29、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ì)列的解釋為：顧客代表消息，而服務(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是一

30、類特殊的隨機(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)(t=e ( - )t排隊(duì)論課件502. 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

31、 c 根據(jù)的生滅過程特點(diǎn)，可以得到下面在M/M/c隊(duì)列中的常用公式。C個(gè)服務(wù)臺(tái)排隊(duì)論課件51M/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ì)論課件52M/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公式： = /（

32、c） ， L=Lq+ c。 請(qǐng)同學(xué)們思考：一個(gè)M/M/c系統(tǒng)與c個(gè)M/M/1系統(tǒng)比較，那一種效率高？排隊(duì)論課件53基本排隊(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: 定長分布 (常數(shù)時(shí)間)Ek: k階Erlang 分布G: 普通的概率分布 (任意概率分布)排隊(duì)論課件54基本排隊(duì)模型記號(hào)系統(tǒng)狀態(tài) : L=排隊(duì)系統(tǒng)顧客的數(shù)量,隊(duì)長。 N(t) =在時(shí)間 t 排隊(duì)系統(tǒng)中顧客的數(shù)量。 Lq =等

33、待服務(wù)的顧客的數(shù)量,隊(duì)列長度。 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ì)長平均等待隊(duì)長平均排隊(duì)等待時(shí)間平均系統(tǒng)逗留時(shí)間排隊(duì)論課件57L, W, Lq, Wq的

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

35、. 例如： 一個(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è)用戶每天上網(wǎng)1h,1.5h,2h,3h,4h,5h的可能性，線路忙產(chǎn)生抱怨的可能性

36、及通信端口的平均使用率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）顧客接受一次服務(wù)后仍回顧客總體4）收費(fèi)僅為了調(diào)節(jié)線路，控制上網(wǎng)時(shí)間，不追求經(jīng)濟(jì)利益。5）不考慮現(xiàn)實(shí)生活

37、中要收取的線路基本費(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è)定的n討論平均每個(gè)用戶每天上網(wǎng)1h,1.5h,2h,3h,4h,5h的可能性，線路忙產(chǎn)生抱怨的可能性及通信端口的平均使用率通常

38、通信端口為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ì)論課件74UNIT2 排隊(duì)網(wǎng)絡(luò)模型 在工程實(shí)踐中，除遇到孤立的排隊(duì)問題外，分析人員還經(jīng)常遇到多個(gè)互連排隊(duì)的問題，如顧客流的分開與合并，隊(duì)列的串并連組合等。排隊(duì)網(wǎng)絡(luò)模型就是來解決這些問題。 主要包括開環(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在游樂園中的

39、頻頻排隊(duì)會(huì)極為掃興DisneyLand中的FastPass(QuickPass)系統(tǒng)就是想解決這個(gè)問題的排隊(duì)論課件77What is QuickPass?工作原理：到達(dá)的顧客將自己的票插入FastPass的slot中FastPass計(jì)算出建議顧客返回的時(shí)間間隔(time interval) 或時(shí)間點(diǎn)或時(shí)間窗(time window)顧客無需排隊(duì)，在指定的時(shí)間返回就可持票進(jìn)入排隊(duì)論課件78怎樣縮短排隊(duì)的等待時(shí)間？銀行的排隊(duì)叫號(hào)機(jī) 只是有序的組織了顧客，并沒有減少等待時(shí)間如果能實(shí)現(xiàn)知道輪到自己需要等待多少時(shí)間，再選擇合適的時(shí)間來，豈不很好？排隊(duì)論課件79FastPass存在的問題：預(yù)知的返回時(shí)間間

40、隔存在誤差按時(shí)返回卻仍需要排隊(duì)建議的返回時(shí)間間隔太長如果告訴你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ì)論課件811 模型的假設(shè)游樂園開放時(shí)間為8:00-18:00,一天中不同時(shí)間的顧客流量不同，比如上午10:00和下午3:00的顧客流量是最大的。顧客的到達(dá)時(shí)間符合非時(shí)間齊次泊松過程(Nonhomogeneous Pos

41、sion Process)，到達(dá)速率是(t)。排隊(duì)論課件82Poisson Process排隊(duì)論課件83Poisson Process排隊(duì)論課件84 分析1：能否得到準(zhǔn)確的返回時(shí)間？ 2 在我們開始動(dòng)手建模之前，先要問幾個(gè)問題：排隊(duì)論課件85 分析2：使用FastPass后排隊(duì)是不是可以避免的？FastPass給出的返回時(shí)間只是期望值，而非確定值假設(shè)所有的顧客都使用FastPass,但需考慮有的顧客可能會(huì)不遵守FastPass給出的返回時(shí)間 2 在我們開始動(dòng)手建模之前，先要問幾個(gè)問題：排隊(duì)論課件86 分析3：我們優(yōu)化的目標(biāo)函數(shù)（或cost function）是什么？是排隊(duì)時(shí)間嗎？ 2 在我們開

42、始動(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)，我們主要討論兩種排隊(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á)式模型的建立

43、（3）電話亭模型排隊(duì)論課件91近似將總的優(yōu)化目標(biāo)函數(shù)等效為對(duì)顧客i的目標(biāo)函數(shù)：模型的建立（3）電話亭模型排隊(duì)論課件92模型的建立（3）電話亭模型排隊(duì)論課件93如果簡化c1,c2為常數(shù)，并計(jì)算第二個(gè)人的無需等待返回時(shí)間的期望值，得用MatLab能夠作出 的函數(shù)，并從圖中得出結(jié)果模型的求解（4）電話亭模型排隊(duì)論課件94模型的求解（4）電話亭模型Average call time (min*10) U2 t2508.051617.08023.051632.5排隊(duì)論課件95第三個(gè)人的無需等待返回時(shí)間的期望值，同理可以算出，并用圖解法求出模型的求解（4）電話亭模型排隊(duì)論課件96但是第4個(gè)人，第5個(gè)人呢？

44、這種方法太繁瑣似乎不好用可否有近似的算法？排隊(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ù)模型模型的建立（5）過山車排隊(duì)論課件99排隊(duì)論課件100最簡單的情況：只有一條隊(duì)列，即所有的人都只用FastPass系統(tǒng)為了防止前面的人等的時(shí)間太長，過山車只要載滿一定數(shù)量的人后就開車，假設(shè)為80c。用貪心算法（

45、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.如果開車的時(shí)間間隔是固定的，則多長時(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）過山車模型怎樣

46、求解最優(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í)間序列的方法（time serial analysis）,計(jì)算列向量的Eucilid距離dthreshold就更新一次排隊(duì)論課件109 對(duì)某一個(gè)或一組變量x(t)進(jìn)行觀察測量，將在一系列時(shí)刻t1, t2, , tn (t為自變量且t1t2 tn )