管理運籌學 課件 12排隊論

OperationalResearch

運籌學哈爾濱理工大學管理學院SchoolofManagement

HarbinUniversityofScienceandTechnology田世海教授

第三章

排隊論本章要點：

1.排隊系統(tǒng)的組成；

2.排隊模型的研究方式；

3.典型排隊系統(tǒng)模型結(jié)構(gòu)及應(yīng)用。

內(nèi)容框架：輸入過程排隊規(guī)則服

務(wù)

臺排隊系統(tǒng)符號表示研究方式

明確系統(tǒng)意義

畫狀態(tài)轉(zhuǎn)移速度圖→

狀態(tài)概率方程

計算基本數(shù)量指標

應(yīng)用舉例分

類典型模型及其應(yīng)用

3.1排隊系統(tǒng)的特征與基本排隊系統(tǒng)一、引言1、排隊服務(wù)系統(tǒng)

在生產(chǎn)和日常生活中，經(jīng)?？梢耘龅礁鞣N各樣的服務(wù)系統(tǒng)。比如：（1）到商店買東西，顧客和售貨員構(gòu)成一個服務(wù)系統(tǒng)，服務(wù)的對象是顧客，服務(wù)機構(gòu)是售貨員；（2）病人到醫(yī)院看病也構(gòu)成一個服務(wù)系統(tǒng)，服務(wù)的對象是病人，服務(wù)機構(gòu)是醫(yī)生。這些服務(wù)系統(tǒng)都有一個共同的特征——排隊等候服務(wù)。這是因為，在某時刻要求服務(wù)的數(shù)量超過服務(wù)機構(gòu)（售貨員，醫(yī)生等）的容量時，也就是說，到達的顧客不能立即得到服務(wù)時，這時（若情況允許排隊等候的話）有的必須等候，因而出現(xiàn)排隊現(xiàn)象，稱這種排隊等候服務(wù)系統(tǒng)為排隊服務(wù)系統(tǒng)。

定義1稱排隊等候服務(wù)系統(tǒng)為排隊服務(wù)系統(tǒng)。說明：（1）排隊服務(wù)系統(tǒng)遠不僅在個人日常生活中出現(xiàn)。例如，電話局的占線問題，車站、碼頭等交通樞紐的車船堵塞和疏通，故障機器的停機待修，水庫的存貯調(diào)節(jié)等都是排隊服務(wù)系統(tǒng)。在一個服務(wù)系統(tǒng)中，若到達服務(wù)系統(tǒng)的顧客完全按固定的間隔時間到達，又服務(wù)設(shè)施用在每個顧客身上的服務(wù)時間也是固定的，就象工廠流水生產(chǎn)線的生產(chǎn)那樣，有固定的節(jié)拍，那么這類服務(wù)系統(tǒng)的設(shè)計計算是比較方便的。（2）在大多數(shù)服務(wù)系統(tǒng)中顧客到達是隨機的，服務(wù)設(shè)施用于每個顧客身上的服務(wù)時間也是隨機的。

定義2若一個排隊服務(wù)系統(tǒng)中顧客到達是隨機的，服務(wù)設(shè)施用于每個顧客身上的服務(wù)時間也是隨機的，則稱此排隊服務(wù)系統(tǒng)為隨機服務(wù)系統(tǒng)。

對于隨機服務(wù)系統(tǒng)，我們應(yīng)開設(shè)多少服務(wù)設(shè)施比較合適呢？如果開設(shè)多了，就要增加服務(wù)人員及相應(yīng)的設(shè)施，增加服務(wù)費用；如果開設(shè)少了排隊現(xiàn)象就會嚴重，對顧客個人和對社會都會帶來不利影響，到底怎樣才能做到既保證一定的服務(wù)質(zhì)量指標，又使服務(wù)設(shè)施費用經(jīng)濟合理，恰當?shù)亟鉀Q顧客排隊時間與服務(wù)設(shè)施費用大小這對矛盾，這就是研究隨機服務(wù)系統(tǒng)的理論——排隊論所要研究解決的問題。（3）排隊系統(tǒng)的統(tǒng)計推斷，即判斷一個給定的排隊系統(tǒng)符合那種類型，以便根據(jù)排隊理論進行分析研究。本章著重研究性態(tài)問題。排隊論研究的內(nèi)容有下列三部分：（1）性態(tài)問題：即研究各種隨機服務(wù)系統(tǒng)的概率規(guī)律性。如研究隊長分布、等待時間分布和忙期分布等。（2）最優(yōu)化問題：分靜態(tài)最優(yōu)和動態(tài)最優(yōu)，前者指最優(yōu)設(shè)計；后者指現(xiàn)有排隊系統(tǒng)的最優(yōu)運營；2、什么是排隊論？

排隊論是研究擁擠現(xiàn)象的一門學科。

它是在研究各種排隊系統(tǒng)概率規(guī)律性的基礎(chǔ)上，解決有關(guān)排隊系統(tǒng)的最優(yōu)設(shè)計（靜態(tài)）和最優(yōu)控制（動態(tài)）問題。3、排隊論的起源與應(yīng)用領(lǐng)域

20世紀初——Bell電話公司為減少用戶呼叫，研究電話線路合理配置問題；

1909年丹麥工程師A.K.Erlang

受熱力學統(tǒng)計平衡概念啟發(fā)

論文“概率論與電話交換”，解決了上述問題；

應(yīng)用于：通訊系統(tǒng)、交通運輸、機器維修、庫存控制、計算機設(shè)計……

二、排隊系統(tǒng)的特征及其組成1、排隊系統(tǒng)的特征即擁擠現(xiàn)象的共性:

有請求服務(wù)的人或物

；

有為顧客服務(wù)的人或物

；

具有隨機性

；（各種排隊系統(tǒng)中，顧客相繼到達的間隔時間以及對每一位顧客的服務(wù)時間是隨機的）

隨機性是排隊系統(tǒng)的一個重要特征

。2、排隊系統(tǒng)的基本組成

顧客源等待隊列顧客離去（輸出）服務(wù)機構(gòu)排隊規(guī)則？（1）輸入過程

：

刻劃顧客到達排隊系統(tǒng)的規(guī)律。排隊系統(tǒng)123顧客到達（輸入）服務(wù)機構(gòu)

顧客總體數(shù)（顧客源）有限或無限；

顧客到達方式是單個到達或成批到達；

顧客相繼到達的間隔時間服從什麼樣的概率分布；（2）服務(wù)規(guī)則

：描述顧客到達排隊系統(tǒng)后接受服務(wù)的先后次序，一般可分為即時制或損失制、等待制和混合制三類：

損失制(Losingsystem)——當顧客到達排隊系統(tǒng)時，若所有的服務(wù)臺均被占用(正在進行服務(wù))，則離開系統(tǒng)，永不再來

；

等待制(Waitingsystem)——顧客到達系統(tǒng)時，所有的服務(wù)臺均被占用（正在進行服務(wù)），顧客就加入排隊行列等待服務(wù)，服務(wù)臺可按照下面的規(guī)則進行排序服務(wù)：①

先到先服務(wù)（FCFS）FirstComeFirstserve②

后到先服務(wù)（LCFS）Last

ComeFirstserve③

隨機服務(wù)（SIRO）ServeInRandomOrder④

有優(yōu)先權(quán)的服務(wù)（PR）Preference

混合制(LosingsystemandWaitingsystem)——損失制和等待制的結(jié)合，一般是指允許排隊，但又不允許隊列無限長下去。主要有以下3種情況：①隊長有限。當?shù)却?wù)的顧客人數(shù)超過規(guī)定數(shù)量時，后來的顧客就自動離去，另求服務(wù)，即系統(tǒng)的等待空間是有限的。②等待時間有限。即顧客在系統(tǒng)中的等待時間不超過某一給定的長度T，當?shù)却龝r間超過時間T時，顧客將自動離去，并不再回來。③逗留時間（等待時間與服務(wù)時間之和）有限。（3）服務(wù)機構(gòu)（服務(wù)臺）：

數(shù)量及布置形式——見下頁圖

某一時刻接受服務(wù)的顧客數(shù)——單個服務(wù)還是成批服務(wù)；

服務(wù)時間的分布——最常見的有定常分布、負指數(shù)分布、k階愛爾朗分布、一般分布等

；

。。。。。。12┇n。。。。。。。。。12┇n（a）單隊單臺。。。。。。12312(d)混合多服務(wù)臺。。。。。。。。。12…n(e)串聯(lián)多服務(wù)臺排隊系統(tǒng)服務(wù)臺布置形式

(b)多隊多臺(c)單隊多臺三、排隊模型的符號表示——

肯道爾分類方法(D.G.kendall)

表示為：

A/B/C/D/E/F或

[A/B/C]：[d/e/f]A

表示輸入過程——顧客相繼到達的間隔時間的分布；B

表示服務(wù)時間服從的分布；C

表示服務(wù)臺的個數(shù)；D

表示系統(tǒng)容量；E

表示顧客源包含的全部個體數(shù)量；F表示服務(wù)規(guī)則

；舉例：

M/M/1/∞/∞/FCFS表示泊松輸入、服務(wù)時間服從負指數(shù)分布、1個服務(wù)臺、系統(tǒng)容量無限制（即等待制）、顧客源無限、先到先服務(wù)的排隊系統(tǒng)

；

GI/EK/1/N/∞/FCFS表示一般獨立輸入（顧客到達的間隔時間服從一般獨立分布）、服務(wù)時間服從K階愛爾朗分布、1個服務(wù)臺、系統(tǒng)容量為N、顧客源無限、先到先服務(wù)的排隊系統(tǒng)。

常用的各種分布符號：M——負指數(shù)分布(兼指泊松輸入)；D——定長分布；EK

——

K階愛爾朗分布；GI——

一般獨立隨機分布；G——

一般隨機分布；四、排隊系統(tǒng)研究的問題

1、排隊系統(tǒng)的數(shù)量指標(特征量

)（1）

研究的目的是：了解系統(tǒng)的基本特征和性態(tài)，揭示其表現(xiàn)的概率規(guī)律性，以便對系統(tǒng)作出評價。（2）主要的數(shù)量指標：*

隊長（Ls）——排隊系統(tǒng)中顧客的平均數(shù)（期望值），包括正在接受服務(wù)和等待接受服務(wù)的顧客總數(shù)期望值。

已知隊長分布，就能計算隊長超過某個數(shù)量的概率，據(jù)此可以考慮是否應(yīng)改變服務(wù)方式、設(shè)計合理的等待空間等；*

隊列長（排隊長Lq）——系統(tǒng)中排隊等待接受服務(wù)的顧客數(shù)期望值；*

逗留時間（Ws）——顧客在系統(tǒng)內(nèi)停留時間（包括排隊等待時間和接受服務(wù)的時間）的期望值；*

等待時間（Wq）——顧客從到達系統(tǒng)的時刻到開始接受服務(wù)的時刻止的時間段；

*忙期和閑期分布——忙期指從有顧客到達空閑服務(wù)臺接受服務(wù)開始到服務(wù)臺再度空閑為止的這段時間，即服務(wù)臺連續(xù)工作的時間。“忙期”是一個隨機變量，可以表征服務(wù)臺的工作強度；

服務(wù)臺連續(xù)保持空閑的時間長度稱為閑期。

在排隊系統(tǒng)中忙期和閑期是交替出現(xiàn)的。*

服務(wù)設(shè)備利用率——指服務(wù)設(shè)備工作時間占總時間的比例。

該指標可以衡量服務(wù)設(shè)備的工作強度、磨損和疲勞程度。*顧客損失率——由于服務(wù)能力不足而造成的顧客流失的概率稱為顧客損失率。

該指標過高會造成服務(wù)系統(tǒng)利潤減少，因此損失制和混合制排隊系統(tǒng)均會重視對該指標的研究。

2、統(tǒng)計推斷問題的研究

對實際問題建立排隊模型時，必須判斷該系統(tǒng)適合建立何種排隊模型，從而進一步用排隊理論進行分析研究。

首先必須進行現(xiàn)實數(shù)據(jù)的收集、處理；

進而研究相繼到達的間隔時間是否獨立分布、確定其分布類型和有關(guān)參數(shù)，研究服務(wù)時間與相繼到達的間隔時間之間的獨立性以及服務(wù)時間的分布等；

判斷該系統(tǒng)適合建立何種類型的排隊模型，再用排隊理論進行分析研究。

3、排隊系統(tǒng)的優(yōu)化

研究排隊系統(tǒng)最優(yōu)設(shè)計的靜態(tài)優(yōu)化和研究排隊系統(tǒng)最優(yōu)控制的動態(tài)優(yōu)化。

最優(yōu)設(shè)計：通常是在輸入和服務(wù)參數(shù)給定的條件下，確定系統(tǒng)的設(shè)計參數(shù)（如服務(wù)臺數(shù)量），以求系統(tǒng)運行指標達到最優(yōu)。

最優(yōu)控制：在系統(tǒng)運行的參數(shù)可以隨時間或狀態(tài)而變化的情況下（如服務(wù)率隨顧客數(shù)的變化而改變）根據(jù)系統(tǒng)的實際情況假設(shè)一個合理或?qū)嶋H可行的控制策略，然后分析確定系統(tǒng)運行的最佳參數(shù)或者是對一個具體系統(tǒng)研究一個最佳的控制策略。

研究排隊系統(tǒng)的目的就是通過對該系統(tǒng)概率規(guī)律的研究，達到系統(tǒng)的最優(yōu)設(shè)計和最優(yōu)控制，以最少的費用實現(xiàn)系統(tǒng)的最大效益。即使服務(wù)系統(tǒng)既能在適當?shù)某潭壬蠞M足顧客需求，同時又使所需費用達到最小。

服務(wù)費用等待費用費用服務(wù)水平總費用費用優(yōu)化示意圖

1、

泊松分布（Poisson）也稱為泊松流，在排隊論中常稱為最簡單流

。

概率分布

：其中，λ>0為一常數(shù)，t≥0。求N(t)的數(shù)學期望得:則λ=E[N(t)]/t。因此，λ表示單位時間內(nèi)到達系統(tǒng)的平均顧客數(shù),又稱平均到達率

。五、排隊系統(tǒng)中常見的幾種典型理論分布

最簡單流的4個基本性質(zhì)：

平穩(wěn)性：在時間段t內(nèi)，恰有n個顧客到達系統(tǒng)的概率P{N(t)=n}僅與t的長短有關(guān),而與該時間段的起始時刻無關(guān)；

無后效性：在不相交的時間區(qū)間內(nèi)到達的顧客數(shù)是相互獨立的。如：在[a，a+t]時段內(nèi)到達K個顧客的概率與時刻a之前到達多少顧客無關(guān)；

普通性：在充分小的間隔時間內(nèi)至少到達兩個顧客的概率ψ(Δt)=o(t),t→0,即

有限性：在任意有限的時間區(qū)間內(nèi)，到達有限個顧客的概率為1，即

泊松流在排隊論中的意義：

實際問題中最常見；

數(shù)字處理簡單；

當實際流與泊松流有較大出入時，經(jīng)過一定的變換，結(jié)果也可達到一定的精度；

2、

負指數(shù)分布

密度函數(shù)和分布函數(shù)

：

數(shù)學期望和方差：

定理6-1

顧客到達服從參數(shù)為λ的泊松分布等價于顧客相繼到達的間隔時間是獨立的且同為負指數(shù)分布。參數(shù)μ>0表示單位時間內(nèi)完成服務(wù)的顧客平均數(shù),稱為平均服務(wù)率。

3、

愛爾朗分布

當顧客在系統(tǒng)內(nèi)所接受的服務(wù)可以分為K個階段，每個階段的服務(wù)時間T1，T2，…，Tk為服從同一分布

（參數(shù)為kμ的負指數(shù)分布）的k個相互獨立的隨機變量，顧客在完成全部服務(wù)內(nèi)容并離開系統(tǒng)后，另一個顧客才能進入服務(wù)系統(tǒng)，則顧客在系統(tǒng)內(nèi)接受服務(wù)時間之和T=T1+T2+…+Tk服從k階愛爾朗分布Ek，其分布密度函數(shù)為：相應(yīng)的數(shù)學期望和方差為：

當k=1時，愛爾朗分布歸結(jié)為負指數(shù)分布，當k增大時，圖形逐漸變?yōu)閷ΨQ的，當k≥30時，近似于正態(tài)分布，當k→∞，由D(T)=0可知,愛爾朗分布歸結(jié)為定長分布。因此，愛爾朗分布類可以看成完全隨機與完全確定的中間型，能對現(xiàn)實問題提供更廣泛的模型類。k=∞k=3k=2k=1

3.2單服務(wù)臺負指數(shù)分布排隊系統(tǒng)

一、標準的M/M/1模型，即M/M/1/∞

/∞

二、系統(tǒng)容量有限制，即M/M/1/N

/∞

三、顧客源為有限制，即M/M/1/∞/m

一、標準的M/M/1模型1、系統(tǒng)的特點：顧客按泊松流輸入、平均到達率為λ，服務(wù)時間服從負指數(shù)分布、平均服務(wù)率為μ，1個服務(wù)臺，系統(tǒng)容量和顧客源均為無限。當顧客來到系統(tǒng)時，若服務(wù)臺忙，則顧客排隊等待服務(wù)，排隊規(guī)則為先到先服務(wù)的排隊系統(tǒng)。由于是單服務(wù)臺，單位時間到達系統(tǒng)的顧客數(shù)為λ，單位時間被服務(wù)完的顧客數(shù)為μ。且顧客源無限，因此，在各種狀態(tài)的情況下，系統(tǒng)的“出生率”為λ，系統(tǒng)的“死亡率”為μ。系統(tǒng)在穩(wěn)態(tài)情況下的狀態(tài)轉(zhuǎn)移如下圖所示

0

1

2n-1

nn+1…P0

P1P2Pn-1

PnPn+12、系統(tǒng)的狀態(tài)轉(zhuǎn)移速度圖：3、狀態(tài)概率方程：根據(jù)以上狀態(tài)轉(zhuǎn)移圖，可以得出如下平衡方程…………遞推求解P1，P2，…，Pn，…，得ρ表示平均到達率與平均服務(wù)率之比，稱為服務(wù)強度要求λ/μ<1,否則系統(tǒng)將是超負荷的,不能達到穩(wěn)態(tài)而無法討論?！纠?】高速公路收費處設(shè)有一個收費通道，汽車到達服從泊松分布，平均到達速率為150輛／小時，收費時間服從負指數(shù)分布，平均收費時間為15秒／輛。求(1)收費處空閑的概率；(2)收費處忙的概率；(3)系統(tǒng)中分別有1，2，3輛車的概率?！窘狻扛鶕?jù)題意,

=150輛/小時,1/μ=15秒/輛=1/240（小時/輛）,即μ＝240（輛/小時）。ρ＝λ/μ=150/240=5/8，則有(1)系統(tǒng)空閑的概率為：P0=1－ρ=1－(5/8)=3/8=0.375(2)系統(tǒng)忙的概率為：1-P0=5/8=0.625(3)系統(tǒng)中有1輛車的概率為：P1=ρ(1－ρ)=0.625×0.375=0.234系統(tǒng)中有2輛車的概率為：P2=ρ2(1－ρ)=0.234×0.625=0.146系統(tǒng)中有3輛車的概率為：P3=ρ3(1－ρ)==0.146×0.625=0.0914、系統(tǒng)的運行指標：（1）在系統(tǒng)中的平均顧客數(shù)隊長期望值（2）在隊列中等待的平均顧客數(shù)（隊列長期望值）（3）在系統(tǒng)中顧客逗留時間的期望值（4）在系統(tǒng)中顧客等待時間的期望值（5）系統(tǒng)處于空閑狀態(tài)的概率（6）系統(tǒng)處于忙期的概率（7）系統(tǒng)處于忙期時隊列中顧客平均數(shù)（8）系統(tǒng)處于忙期時顧客平均等待時間Little公式:【例2】輕軌進站口售票處設(shè)有一個售票窗口，乘客到達服從泊松分布，平均到達速率為200人/小時，售票時間服從負指數(shù)分布，平均售票時間為15秒/人。求L、Lq、W和Wq?！窘狻扛鶕?jù)題意，λ=200人/小時，μ=240人/小時，ρ=5/6。1、系統(tǒng)的特征

顧客按泊松流輸入,平均到達率為λ；

服務(wù)時間服從負指數(shù)分布,平均服務(wù)率為μ；

1個服務(wù)臺；

系統(tǒng)容量為N,顧客源無限,排隊規(guī)則為先到先服務(wù)的混合制排隊系統(tǒng)。

當顧客來到系統(tǒng)時,若系統(tǒng)中的顧客已經(jīng)等于N，則自動離去,另求服務(wù)

。

二、系統(tǒng)容量有限制，即M/M/1/N

/∞顧客到達因隊列滿而離去進入隊列接受服務(wù)服務(wù)完畢后離去2、狀態(tài)轉(zhuǎn)移速度圖（1）系統(tǒng)狀態(tài)

：系統(tǒng)中的顧客數(shù)。（2）狀態(tài)轉(zhuǎn)移速度圖：N-1

NN-2

2

1

0……μμμμλλλλ

M/M/1/N/∞/FCFS系統(tǒng)狀態(tài)轉(zhuǎn)移速度圖

圓圈表示狀態(tài)符號

，箭頭表示從一個狀態(tài)到另一個狀態(tài)的轉(zhuǎn)移；

3、狀態(tài)概率方程：…4、系統(tǒng)的運行指標：(1)系統(tǒng)中的平均顧客數(shù)Ls(2)隊列中的平均顧客數(shù)Lq

λe稱為有效到達率，即單位時間內(nèi)到達并能進入隊列的平均顧客數(shù)。ρe稱為有效服務(wù)強度在研究顧客在系統(tǒng)中平均逗留時間和在隊列中平均等待時間時，雖然可用公式：但要注意平均到達率是在系統(tǒng)中有空時的平均到達率，當系統(tǒng)已滿時，則到達率為0，因此需求出有效到達率。(3)顧客在系統(tǒng)中的平均逗留時間W(4)顧客在隊列中的平均逗留時間(5)有效到達率的另一種計算公式λe=λ（1-PN）+0PN

(系統(tǒng)不滿時顧客以λ的速度進入系統(tǒng)）

=μ（1-P0）+0P0

（系統(tǒng)不空時顧客以μ的速度離開系統(tǒng)）(6)

系統(tǒng)平均每單位時間損失的顧客數(shù)λ損=λ-λe=λPN(7)

系統(tǒng)平均每單位時間損失的顧客數(shù)

從服務(wù)臺閑到下一個顧客來到的平均間隔時間是1/λ，因此平均閑期長為

T閑=1/λ由于服務(wù)臺忙閑間隔出現(xiàn)，故有：平均忙期長T忙/平均閑期長T閑=P忙/P閑=(1-P0)/P0，于是

T忙=T閑[(1-P0)/P0]=1/λ[(1-P0)/P0]【例3】咨詢中心有一位咨詢工作人員，每次只能咨詢一人，另外有4個座位供前來咨詢的人等候。某人到來發(fā)現(xiàn)沒有座位，就不再等待而離去。前來咨詢者到達服從泊松流，到達的平均速率為4人/小時，咨詢?nèi)藛T的平均咨詢時間為10分鐘/人。咨詢時間服從負指數(shù)分布。求：(1)咨詢者到達不用等待就可咨詢的概率(2)咨詢中心的平均人數(shù)以及等待咨詢的平均人數(shù)(3)咨詢者來咨詢中心一次平均花費的時間以及平均等待的時間(4)咨詢者到達后因客滿而離去的概率(5)增加一個座位可以減少的顧客損失率【解】N=4+1