第3講排隊系統(tǒng)的基本概念ppt課件

1、北京郵電大學自動化學院物流工程北京郵電大學自動化學院物流工程 蘇志遠蘇志遠 系統(tǒng)建模與仿真整理課件1第三講 排隊系統(tǒng)的基本概念北京郵電大學自動化學院物流工程北京郵電大學自動化學院物流工程 蘇志遠蘇志遠 系統(tǒng)建模與仿真整理課件2知識回顧離散事件系統(tǒng)（DEDS或DES)基本概念、基本要素DES系統(tǒng)舉例離散事件系統(tǒng)仿真步驟離散事件系統(tǒng)策略1. 手工仿真 排隊系統(tǒng)北京郵電大學自動化學院物流工程北京郵電大學自動化學院物流工程 蘇志遠蘇志遠 系統(tǒng)建模與仿真整理課件3排隊系統(tǒng)的特征 排隊除了有形的隊列外，還可以是無形的隊列。電話預定租車服務；網絡傳輸；排隊的可以是人，也可以是物。生產線上的原材料、半成品；故

2、障待修的機器；要進站的火車由于展臺被占而等待；網絡打印北京郵電大學自動化學院物流工程北京郵電大學自動化學院物流工程 蘇志遠蘇志遠 系統(tǒng)建模與仿真整理課件4排隊系統(tǒng)的形式 單服務臺的排隊系統(tǒng)北京郵電大學自動化學院物流工程北京郵電大學自動化學院物流工程 蘇志遠蘇志遠 系統(tǒng)建模與仿真整理課件5排隊系統(tǒng)的形式 S 個服務臺，一個隊列的排隊系統(tǒng)北京郵電大學自動化學院物流工程北京郵電大學自動化學院物流工程 蘇志遠蘇志遠 系統(tǒng)建模與仿真整理課件6排隊系統(tǒng)的形式 S 個服務臺，S個隊列的排隊系統(tǒng)北京郵電大學自動化學院物流工程北京郵電大學自動化學院物流工程 蘇志遠蘇志遠 系統(tǒng)建模與仿真整理課件7排隊系統(tǒng)的形式

3、多個服務臺的串聯排隊北京郵電大學自動化學院物流工程北京郵電大學自動化學院物流工程 蘇志遠蘇志遠 系統(tǒng)建模與仿真整理課件8排隊系統(tǒng)描述 實際中的排隊系統(tǒng)各不相同，但概括起來都由三個基本部分組成：輸入過程、排隊及排隊規(guī)則和服務機制。北京郵電大學自動化學院物流工程北京郵電大學自動化學院物流工程 蘇志遠蘇志遠 系統(tǒng)建模與仿真整理課件9輸入過程 說明顧客是按什么樣的規(guī)律到達系統(tǒng)，需說明顧客是按什么樣的規(guī)律到達系統(tǒng)，需要從三個方面來描述要從三個方面來描述顧客總數?？梢允怯邢薜?，也可以是無限的；到達方式。單個到達還是成批到達。庫存問題中的進貨為成批到達；顧客相繼到達時間間隔的分布。定長分布（D）。最簡流（P

4、oission流）（M）：顧客相繼到達的時間間隔為獨立的，且同負指數分布，其密度函數為：000)(ttetat（2.1）北京郵電大學自動化學院物流工程北京郵電大學自動化學院物流工程 蘇志遠蘇志遠 系統(tǒng)建模與仿真整理課件10排隊及排隊規(guī)則排隊無限排隊：系統(tǒng)中的顧客是無限的，隊列可以排到無限長，顧客到達系統(tǒng)后均可以進入系統(tǒng)排隊或接受服務。北京郵電大學自動化學院物流工程北京郵電大學自動化學院物流工程 蘇志遠蘇志遠 系統(tǒng)建模與仿真整理課件11排隊及排隊規(guī)則排隊有限排隊：排隊系統(tǒng)中的顧客數是有限的，即系統(tǒng)的空間是有限的，當系統(tǒng)被占后，后面再來的顧客不能進入系統(tǒng)接受服務。又可以分為以下兩種：損失制排隊系統(tǒng)

5、。當顧客到達系統(tǒng)時，如果所有的服務均被占用，則自動離去，并不再回來?；旌现婆抨犗到y(tǒng)。等待制和損失制的結合，有以下三種：隊長有限，即系統(tǒng)的等待空間是有限的（即隊長容量為K）等待時間有限。即顧客在系統(tǒng)中的等待時間超過給定的等待時間長度T后，即離去并不再回來。 逗留時間有限（等待時間和服務時間之和） 。北京郵電大學自動化學院物流工程北京郵電大學自動化學院物流工程 蘇志遠蘇志遠 系統(tǒng)建模與仿真整理課件12排隊及排隊規(guī)則排隊規(guī)則先來先服務（FCFS）后來先服務（LCFS）：如堆棧具有優(yōu)先權的服務（PS）北京郵電大學自動化學院物流工程北京郵電大學自動化學院物流工程 蘇志遠蘇志遠 系統(tǒng)建模與仿真整理課件13

6、服務機制 排隊系統(tǒng)的服務機制主要包括：服務員的數量及其連接形式（串聯或并聯）；顧客是單個還是成批接受服務；服務時間的分布。在這些因素中，服務時間的分布更為重要。常見的分布有：定長分布（D）：即每個顧客接受服務的時間是一個確定的常數。負指數分布（M）：即每個顧客接受服務的時間相互獨立，具有相同的負指數分布：000 )( ttetbt（2.2）北京郵電大學自動化學院物流工程北京郵電大學自動化學院物流工程 蘇志遠蘇志遠 系統(tǒng)建模與仿真整理課件14K階愛爾朗分布（ ）：每個顧客接受服務的時間服務K階愛爾朗分布，其密度函數為 （2.3）kEtkekktkktb )!1(1) ()( 愛爾朗分布比負指數分

7、布更具有廣泛的適應性。當k=1時，愛爾朗分布為負指數分布；當k增加時，愛爾朗分布逐漸變?yōu)閷ΨQ的。事實上，當k30以后，愛爾朗分布近似于正態(tài)分布。當k時，由方差 為可知，方差將趨近于零，即為完全非隨機的。所以，K階愛爾朗分布可看成完全隨機（k1）與完全非隨機之間的分布，能更廣泛的適應于現實世界。21k北京郵電大學自動化學院物流工程北京郵電大學自動化學院物流工程 蘇志遠蘇志遠 系統(tǒng)建模與仿真整理課件15排隊系統(tǒng)的符號表示 根據輸入過程、排隊規(guī)則和服務機制的變化對排隊模型進行描述或分類，可以給出很多的排隊模型。為了方便對眾多的模型的描述，D.G.Kendall提出了一種目前在排隊論中被廣泛采用的“K

8、endall 記號”，一般形式為： X/Y/Z/A/B/CX 表示顧客相繼達到時間間隔的分布；Y 表示服務時間的分布 Z 表示服務臺的個數 A 表示系統(tǒng)容量，即可容納的最多顧客數 B 表示顧客源的數目 C 表示服務規(guī)則 北京郵電大學自動化學院物流工程北京郵電大學自動化學院物流工程 蘇志遠蘇志遠 系統(tǒng)建模與仿真整理課件16排隊系統(tǒng)的符號表示 M/M/1/FCFS （FIFS/LIFS）M/M/1 M/M/s/K 北京郵電大學自動化學院物流工程北京郵電大學自動化學院物流工程 蘇志遠蘇志遠 系統(tǒng)建模與仿真整理課件17排隊系統(tǒng)的主要數量指標和記號 研究排隊系統(tǒng)的目的是通過了解系統(tǒng)的運行的狀況，對系統(tǒng)進

9、行調整和控制，使系統(tǒng)處于最優(yōu)的運行狀態(tài)。因此，首先需要弄清系統(tǒng)的運行狀況。描述一個排隊系統(tǒng)的主要數量指標有：隊長和排隊長等待時間和逗留時間忙期和閑期北京郵電大學自動化學院物流工程北京郵電大學自動化學院物流工程 蘇志遠蘇志遠 系統(tǒng)建模與仿真整理課件18隊長和排隊長隊長是指系統(tǒng)中的顧客數（排隊等待的顧客數與正在接受服務的顧客數之和），排隊長是指系統(tǒng)中正在排隊等待服務的顧客數。1. 隊長和排隊長一般都是隨機變量。 北京郵電大學自動化學院物流工程北京郵電大學自動化學院物流工程 蘇志遠蘇志遠 系統(tǒng)建模與仿真整理課件19等待時間和逗留時間等待時間：從顧客到達時刻起到他接受服務止這段時間。逗留時間：從顧客到

10、達時刻起到接受服務完成止這段時間。1. 等待時間、逗留時間都是隨機變量北京郵電大學自動化學院物流工程北京郵電大學自動化學院物流工程 蘇志遠蘇志遠 系統(tǒng)建模與仿真整理課件20忙期和閑期忙期是指從顧客到達空閑著的服務機構起，到服務機構再次稱為空閑止的這段時間 。閑期是與忙期相對的，是服務機構連續(xù)保持空閑的時間。 1. 忙期和閑期都是隨機變量北京郵電大學自動化學院物流工程北京郵電大學自動化學院物流工程 蘇志遠蘇志遠 系統(tǒng)建模與仿真整理課件21 上述指標的常用記號 ：時刻t 系統(tǒng)中的顧客數（又稱為系統(tǒng)的狀態(tài)），即隊長。 ：時刻t 系統(tǒng)中排隊的顧客數，即排隊長。 ：時刻t 到達系統(tǒng)的顧客在系統(tǒng)中的逗留時

11、間。 ：時刻t 到達系統(tǒng)的顧客在系統(tǒng)中的等待時間。 )(tN)(tNq)(tT)(tTq北京郵電大學自動化學院物流工程北京郵電大學自動化學院物流工程 蘇志遠蘇志遠 系統(tǒng)建模與仿真整理課件22 平衡狀態(tài)下的指標 當系統(tǒng)達到平衡時處于狀態(tài)n的概率，記為 ，又記： N：系統(tǒng)處于平衡狀態(tài)時的隊長，其均值為L，稱為平均隊長； ：系統(tǒng)處于平衡狀態(tài)時的排隊長，其均值為，稱為平均排隊長； T ：系統(tǒng)處于平衡狀態(tài)時顧客的逗留時間，其均值為W，稱為平均逗留時間； ：系統(tǒng)處于平衡狀態(tài)時顧客的等待時間，其均值為，稱為平均等待時間； ：當系統(tǒng)處于狀態(tài)n時，新來顧客的平均到達率（單位時間內新來到系統(tǒng)的平均顧客數）； ：當

12、系統(tǒng)處于狀態(tài)n時，整個系統(tǒng)的平均服務率（單位時間內可以服務完的顧客數）；npqNqTnn北京郵電大學自動化學院物流工程北京郵電大學自動化學院物流工程 蘇志遠蘇志遠 系統(tǒng)建模與仿真整理課件23 系統(tǒng)的服務強度 北京郵電大學自動化學院物流工程北京郵電大學自動化學院物流工程 蘇志遠蘇志遠 系統(tǒng)建模與仿真整理課件24 忙期和閑期 忙期為B，閑期為I，平均忙期和平均閑期為和 ，s為系統(tǒng)中并行的服務臺數。BI北京郵電大學自動化學院物流工程北京郵電大學自動化學院物流工程 蘇志遠蘇志遠 系統(tǒng)建模與仿真整理課件25排隊系統(tǒng)研究的基本問題 排隊系統(tǒng)研究的首要問題是排隊系統(tǒng)的主要數量指標的概率規(guī)律，即研究系統(tǒng)的整體

13、性質，然后進一步研究系統(tǒng)的優(yōu)化問題。通過研究主要數據指標在瞬時或平衡狀態(tài)下的概率分布及其數字特征，了解系統(tǒng)運行的基本特征。統(tǒng)計推斷問題，建立適當的排隊模型。在建立模型的過程中經常會碰到如下問題：檢驗系統(tǒng)是否已經到達平衡狀態(tài)；檢驗顧客的相繼達到時間間隔的相互獨立性；確定服務時間的分布及其參數等。系統(tǒng)優(yōu)化問題，又稱為系統(tǒng)控制問題或系統(tǒng)運營問題，其基本目的是使系統(tǒng)處于最優(yōu)或最合理的狀態(tài)。系統(tǒng)優(yōu)化問題包括最優(yōu)設計問題和最優(yōu)運營問題，其內容很多，有最少費用問題、服務率控制問題、服務臺的開關策略、顧客（或服務）根據優(yōu)先權的最優(yōu)排序問題。北京郵電大學自動化學院物流工程北京郵電大學自動化學院物流工程 蘇志遠蘇

14、志遠 系統(tǒng)建模與仿真整理課件26 生滅過程簡介 一類非常重要且廣泛存在的排隊系統(tǒng)是生滅過程排隊系統(tǒng)。生滅過程是一類特殊的隨機過程，在生物學、物理學、運籌學中有廣泛的應用。在排隊系統(tǒng)中，如果用N(t)表示時刻t系統(tǒng)中的顧客數，則N(t)，t0就構成了一個隨機過程。如果用“生”表示顧客的到達，“滅”表示顧客的離去，則對許多排隊過程來說，N(t)，t0就是一類特殊的隨機過程 生滅過程。北京郵電大學自動化學院物流工程北京郵電大學自動化學院物流工程 蘇志遠蘇志遠 系統(tǒng)建模與仿真整理課件27定義定義 1： 設N(t)，t0為一個隨機過程。若N(t)的概率分布有如下性質：假設N(t)n，則從時刻t起到下一個

15、顧客到達的時刻止的時間服從參數為 的負指數分布，n0，1，2，。假設N(t)n，則從時刻t起到下一個顧客離去的時刻止的時間服從參數為 的負指數分布，n0，1，2，。同一時刻只有一個顧客到達或者離去。 則稱N(t)，t0是一個生滅過程。nn北京郵電大學自動化學院物流工程北京郵電大學自動化學院物流工程 蘇志遠蘇志遠 系統(tǒng)建模與仿真整理課件28 一般說來，得到N(t)的分布 是比較困難的，因此通常是求當系統(tǒng)達到平衡狀態(tài)后的狀態(tài)分布，記為：.)2 , 1 , 0()(nntNp,.2 , 1 , 0 npn，北京郵電大學自動化學院物流工程北京郵電大學自動化學院物流工程 蘇志遠蘇志遠 系統(tǒng)建模與仿真整理

16、課件29 求解狀態(tài)n的概率 為求平穩(wěn)分布，考慮系統(tǒng)可能處的任一狀態(tài)n。假設記錄了一段時間內進入狀態(tài)n和離開狀態(tài)n的次數，則因為“進入”和“離開”是交替發(fā)生的，所以這兩個數要么相等，要么相差為1。但就這兩種事件的平均發(fā)生概率是相等的。即當系統(tǒng)運行相當時間到達平穩(wěn)狀態(tài)后，對任一狀態(tài)n來說，單位時間內進入該狀態(tài)的平均次數和單位時間內離開該狀態(tài)的平均次數是相等的，這就是系統(tǒng)在統(tǒng)計平衡下的“流入流出”原理。根據這一原理，可得到任一狀態(tài)下的平衡方程如下： ,.2 , 1 , 0 npn，北京郵電大學自動化學院物流工程北京郵電大學自動化學院物流工程 蘇志遠蘇志遠 系統(tǒng)建模與仿真整理課件300011pp1112200)(ppp2223311)(ppp11122)(nnnnnnnpppnnnnnnnppp)(1111 0 1 2 n-1 n（2.4） 北京郵電大學自動化學院物流工程北京郵電大學自動化學院物流工程 蘇志遠蘇志遠 系統(tǒng)建模與仿真整理課件310101pp01221121001121212)(1pppppp01230122323ppp01102111.pppnnnnnnnn0110111.pppnnnnnnnn0 1 2 n-1 n北京郵電大學自動化學院物流工程北京郵電大學自動化學院物流工