排隊論

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

UNIT1排隊模型

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

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

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

概率的定義

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

求拋兩個骰子并且決定和為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排隊理論(講義)(2)相對頻率定義：

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á)到概率的有效計算。這些公理包括：（a）

對于每一個事件A，有0≤P（A）≤1（b）

P（Ω）=1（c）

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

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

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

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

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

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

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

P(Ei|A)=

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

也稱為后驗(yàn)概率公式，是在已知結(jié)果發(fā)生的情況下，求導(dǎo)致結(jié)果的某種原因的可能性的大小。6排隊理論(講義)Part2.隨機(jī)變量的數(shù)字特征隨機(jī)變量X是樣本點(diǎn)的函數(shù)，它的定義域是樣本空間Ω，值域是實(shí)數(shù)集R，即X：Ω→R隨機(jī)變量的數(shù)字特征對研究隨機(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)計平均值，簡稱均值

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排隊理論(講義)3協(xié)方差：兩個隨機(jī)變量X和Y的協(xié)方差定義如下：Cov(X,Y)=E[(X-μx)(Y-μy)]=E[XY]-E[X]E[Y]4相關(guān)系數(shù):兩個隨機(jī)變量X和Y的相關(guān)系數(shù)定義如下：r(X,Y)=Cov(X,Y)/σxσy相關(guān)系數(shù)是兩個隨機(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排隊理論(講義)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排隊理論(講義)幾何分布有一個重要的性質(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á)：P{X=n+m|X>n}=P{X=m}(請同學(xué)們試證明之）這種與過去歷史無關(guān)的性質(zhì)稱為馬爾可夫性。幾何分布在我們下面講的排隊論中是非常重要。它可以描述某一任務(wù)（或顧客）的服務(wù)持續(xù)時間。4泊松分布（Poisson）P{X=k}=λke-λ/k!k=0,1,2,…泊松分布是最重要的離散型概率分布之一，它作為表述隨機(jī)現(xiàn)象的一種形式，在計算機(jī)性能評價等實(shí)踐中扮演了重要的角色。在實(shí)際系統(tǒng)模型中，一般都要假定任務(wù)（或顧客）的到來是服從泊松分布的。實(shí)踐也證明：這種假設(shè)是有效的。10排隊理論(講義)5

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

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

f（x）=

λe-λxx≥0

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

μx=σx=1/λ

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

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

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

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

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

如下圖：

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

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

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

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

對所有電阻來說，其熱噪聲電壓就是一族時間函數(shù)，記為x(t)，這族時間函數(shù)就是“隨機(jī)過程”，族中每一時間函數(shù)稱為隨機(jī)過程的樣本函數(shù)。14排隊理論(講義)Part5馬爾可夫過程馬爾可夫過程(MarkovProcess)是具有無后效性的隨機(jī)過程。無后效性是指：當(dāng)過程在tn時刻所處的狀態(tài)為已知時，過程在大于tn的時刻所處狀態(tài)的概率特性只與過程在tn時刻所處的狀態(tài)有關(guān)，而與過程在tn時刻以前的狀態(tài)無關(guān)。換言之，對于隨機(jī)過程{X（t），t∈T}，如果對于任意參數(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}此條件稱為過程的無后效性或過程的馬爾可夫性。t0t1tn-1tnt15排隊理論(講義)Part6生滅過程

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

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

|i-j|>1有pij

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

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

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

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

尤其是在我們這樣的人口大國

電話亭－1978年在北京15%的電話要在1小時后才能接通。在電報大樓打電話的人還要帶著午飯去排隊

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

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

顧客離開

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

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

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

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

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

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

一般服務(wù)臺對顧客是一個一個進(jìn)行服務(wù)的，且對每一個顧客的服務(wù)時間長短不一。

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

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

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

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

在服務(wù)時從等待顧客中隨意抽取一個進(jìn)行服務(wù)。（d）優(yōu)先服務(wù)和動態(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)分為三類：排隊優(yōu)先權(quán)、中斷優(yōu)先權(quán)、動態(tài)優(yōu)先權(quán)。如計算機(jī)中斷的優(yōu)先級。（e）處理器共享（processorsharing，PS）

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

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

將某一時刻設(shè)為t0，顧客依次到達(dá)的時刻用…≤t-1≤t0≤t1≤t2≤…表示，如果在時刻tk到達(dá)的顧客為Nk，則到達(dá)時點(diǎn)可用{tk、Nk）表示。（b）平均到達(dá)間隔一個顧客到達(dá)時刻之間的時寬為到達(dá)間隔。（c）到達(dá)速率單位時間到達(dá)顧客的平均數(shù)叫到達(dá)速率，也稱到達(dá)密度或輸入速率。（2）到達(dá)規(guī)律

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

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

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

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

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

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

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

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

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

1)T1(

2)T1(

3)T

(

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

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

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

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

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

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

A／B／n／S／Z其中符號的含義如下：

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

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

Ek：k-愛爾朗分布。表示到達(dá)間隔時間或服務(wù)時間服從k-愛爾朗分布。E是Erlang的第一個字母。D:定長分布(常數(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ù)。41排隊理論(講義)3基本排隊關(guān)系在對排隊進(jìn)行分析時，為了便于分析，經(jīng)常做一些簡化假設(shè)。對一個排隊系統(tǒng)，若滿足以下三個條件：（1）排隊系統(tǒng)能夠進(jìn)入統(tǒng)計平衡狀態(tài)；（2）服務(wù)員的忙期與閑期交替出現(xiàn)，即系統(tǒng)不是總處于忙的狀態(tài)；（3）系統(tǒng)中任一顧客不會永遠(yuǎn)等待，系統(tǒng)也不會永無顧客到達(dá)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

L=ρ/(1-ρ),

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

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

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

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

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

Lq=λWq

L=λWW=Wq+1/

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

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

λk=

λ，k=0,1,2,…

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

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

/

/FCFS

M/M/1/

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

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

統(tǒng)計平穩(wěn)條件下的記號

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

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

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

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

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

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

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

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

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

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

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

服務(wù)臺數(shù)目/

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

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

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

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

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

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

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

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

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

2在我們開始動手建模之前，

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

2在我們開始動手建模之前，

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

2在我們開始動手建模之前，

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

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

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