《管理運籌學》10-服務系統(tǒng)規(guī)劃

1、編輯課件編輯課件服務系統(tǒng)規(guī)劃服務系統(tǒng)規(guī)劃編輯課件編輯課件第一節(jié)：服務排隊現(xiàn)象及其建模第一節(jié)：服務排隊現(xiàn)象及其建模第二節(jié)：排隊系統(tǒng)的常用分布第二節(jié)：排隊系統(tǒng)的常用分布第三節(jié)：單服務臺模型第三節(jié)：單服務臺模型第四節(jié)：多服務臺模型第四節(jié)：多服務臺模型第五節(jié)：其他服務時間分布模型第五節(jié)：其他服務時間分布模型第六節(jié)：服務系統(tǒng)規(guī)劃的應用第六節(jié)：服務系統(tǒng)規(guī)劃的應用編輯課件編輯課件一、現(xiàn)實中的服務排隊現(xiàn)象一、現(xiàn)實中的服務排隊現(xiàn)象所謂排隊排隊，是指需要得到某種服務的對象加入等待的隊列。需要得到服務的對象泛稱為顧客顧客，而從事服務的設(shè)施或人等泛稱為服務臺服務臺。顧客與服務臺構(gòu)成一個系統(tǒng)，稱為服務系統(tǒng)服務系統(tǒng)。在一

2、個服務系統(tǒng)中，若某一時刻顧客的數(shù)目超過服務臺的數(shù)目，則稱為擁擠，這時必然導致一些顧客不能立即得到服務而需要等待，從而產(chǎn)生排隊現(xiàn)象。由于擁擠而產(chǎn)生排隊現(xiàn)象的服務系統(tǒng)稱為排隊系統(tǒng)排隊系統(tǒng)。編輯課件編輯課件在日常的工作與生活中，人們經(jīng)常會遇到各種各樣的服務系統(tǒng)如進食堂就餐、到圖書館借書、去車站乘公共汽車、去醫(yī)院看病、到售票處購票、上高速公路行駛（如圖9-1）等，食堂的服務員與就餐者、圖書館的管理員與借閱者、公共汽車與乘客、醫(yī)生與病人、售票員與顧客、高速公路與車輛均構(gòu)成了服務系統(tǒng)。編輯課件編輯課件在各種排隊系統(tǒng)中：顧客可以是人，也可以是物。如待分類的圖書、待送的郵件，等等，這些是有形的顧客；還有無形的

3、顧客，如呼叫電話、故障信號、新聞、事務，等等。因此顧客的等待排隊也可以是有形的或無形的，集中的或分散的。服務臺可以是人，如維修工人；也可以是設(shè)施，如投幣電話亭；還可以是一個系統(tǒng)，如醫(yī)生、護士、手術(shù)臺、手術(shù)機械、藥品等的有機整體構(gòu)成一個服務臺；服務臺可以是固定的，也可以是流動的，如沿街叫賣的個體商販；服務方式也可以是登門服務，如自來水、供電、煤氣公司派人到用戶住址看表計價，維修工人到故障機器前進行維修，等等。編輯課件編輯課件表9-1 現(xiàn)實中的各種服務系統(tǒng)顧客服務內(nèi)容服務臺考生報名登記招考登記員病人診斷病情醫(yī)生電話呼叫通話交換臺駛?cè)敫劭诘呢洿b（卸）貨裝（卸）貨碼頭（泊位）文件稿打字打字員提貨單提

4、取存貨倉庫管理員不能運轉(zhuǎn)的機器修理修理技工上游河水進入水庫放水，調(diào)整水位水閘管理員進入我方陣地的敵機我方高射炮進行射擊我方高射炮編輯課件編輯課件二、排隊系統(tǒng)的組成和特征二、排隊系統(tǒng)的組成和特征 一般的排隊系統(tǒng)都有三個基本組成部分：輸入過程；排隊規(guī)則；服務機構(gòu)。編輯課件編輯課件1. 輸入過程輸入過程 輸入即指顧客到達排隊系統(tǒng)，可能有以下各種不同情況。 顧客的總體（顧客源）的組成可能是有限的，也可能是無限的。上游河水流入水庫可以認為總體是無限的，工廠內(nèi)停機待修的機器顯然是有限的總體。 顧客到來的方式可能是一個一個的，也可能是成批的。例如到餐廳就餐就有單個到來的顧客和受邀請來參加宴會的成批顧客，我們

5、將只研究單個到來的情形。 顧客相繼到達的間隔時間可以是確定型的，也可以是隨機型的。如在自動裝配線上裝配的各部件就必須按確定的時間間隔到達裝配點，定期運行的班車、班輪、班機的到達也都是確定型的。但一般到商店購物的顧客、到醫(yī)院診病的病人、通過路口的車輛等，它們的到達都是隨機型的。對于隨機型的情形，要知道單位時間內(nèi)的顧客到達數(shù)或相繼到達的間隔時間的概率分布。編輯課件編輯課件 顧客的到達可以是相互獨立的，就是說，以前的到達情況對以后顧客的到來沒有影響，否則就是有關(guān)聯(lián)的。例如，工廠內(nèi)的機器在一個短的時間區(qū)間內(nèi)出現(xiàn)停機（顧客到達）的概率就受已經(jīng)待修或被修理的機器數(shù)目的影響。本章主要討論的是相互獨立的情形。

6、 輸入過程可以是平穩(wěn)的，或稱對時間是齊次的，是指描述相繼到達的間隔時間分布和所含參數(shù)（如期望值、方差等）都是與時間無關(guān)的，否則稱為非平穩(wěn)的。非平穩(wěn)情形的數(shù)學處理是很困難的。編輯課件編輯課件2. 排隊規(guī)則排隊規(guī)則 顧客到達時，若所有服務臺都正被占用，在這種情形下顧客可以隨即離去，也可以排隊等候。隨即離去的稱為即時制或稱損失制（因為失掉許多顧客）；排隊等候的稱為等待制。普通市內(nèi)電話的呼喚屬于前者，而登記市外長途電話的呼喚屬于后者。編輯課件編輯課件對于等待制，為顧客進行服務的次序可采用下列各種規(guī)則：1）先到先服務，即按顧客到達次序接受服務，這是最通常的情形。2）后到先服務，如乘電梯的顧客常是后入先出

7、的。倉庫中存放的厚鋼板也是如此。在情報系統(tǒng)中，最后到達的信息往往是最有價值的，而采用后到先服務（指被采用）的規(guī)則。3）隨機服務，指服務員從等待的顧客中隨機選取其一進行服務，而不管到達的先后，如電話交換臺接通呼喚的電話就是如此。4）有優(yōu)先權(quán)的服務，如醫(yī)院對病情嚴重的患者將給予優(yōu)先治療。編輯課件編輯課件 從占有的空間來看，隊列可以排在具體的處所（如售票處、候診室等），也可以是抽象的（如向電話交換臺要求通話的呼喚）。 由于空間的限制或其他原因，有的系統(tǒng)要規(guī)定容量（即允許進入排隊系統(tǒng)的顧客數(shù)）的最大限制；有的沒有這種限制（即認為容量可以是無限的）。編輯課件編輯課件 從隊列的數(shù)目看，可以是單列，也可以是

8、多列。在多列的情形，各列間的顧客有的可以相互轉(zhuǎn)移，有的不能（如用繩子或欄桿隔開）。有的排隊顧客因等候時間過長而中途退出，有的不能退出（如高速公路上的汽車流），必須堅持到被服務為止。本章將只討論各隊列間不能互相轉(zhuǎn)移，也不能中途退出的情形。編輯課件編輯課件3.服務機構(gòu)服務機構(gòu)從機構(gòu)形式和工作情況來看有以下幾種情況。 服務機構(gòu)可以沒有服務員，也可以有一個或多個服務員（服務臺、通道、窗口等）。例如，在敞架售書的書店，顧客選書時就沒有服務員，但交款時可能有多個服務員。 在有多個服務臺的情形中，它們可以是平行排列（并列）的，可以是前后排列（串列）的，也可以是混合的。如圖9-2所示。編輯課件編輯課件編輯課件

9、編輯課件編輯課件編輯課件編輯課件編輯課件 服務方式可以對單個顧客進行，也可以對成批顧客進行，公共汽車對在站臺等候的顧客就成批進行服務。本章將只研究單獨的服務方式。 和輸入過程一樣，服務時間也分確定型的和隨機型的。自動沖洗汽車的裝置對每輛汽車沖洗（服務）的時間就是確定型的，但大多數(shù)情形的服務時間是隨機型的。對于隨機型的服務時間，需要知道它的概率分布。 和輸入過程一樣，服務時間的分布總假定是平穩(wěn)的，即分布的期望值、方差等參數(shù)都不受時間的影響。編輯課件編輯課件三、排隊模型的分類三、排隊模型的分類為了區(qū)別各種排隊系統(tǒng)，根據(jù)輸入過程、排隊規(guī)則和服務機構(gòu)的變化對排隊模型進行描述或分類。1953年肯道爾（K

10、endall）提出一個分類方法，稱為Kendall符號，其形式是 X / Y / Z；在1971年一次關(guān)于排隊論符號標準化國際會議上，將Kendall符號擴充為以下標準形式：X / Y / Z / A / B / C 或者 X / Y / Z : A / B / C 編輯課件編輯課件Kendall各符號的意義：(1) X:表示顧客相繼到達時間間隔的概率分布，可以取 M、D 、Ek、 G等，其中：M 表示到達過程為泊松過程或負指數(shù)分布；D 表示定長輸入；Ek 表示K階愛爾朗（Erlang）分布；G 表示一般相互獨立的隨機分布；(2) Y: 表示服務時間分布，所用符號與X相同編輯課件編輯課件 Z：

11、表示服務臺個數(shù)，取正整數(shù)。1表示單個服務臺，s 表示多個服務臺。 A：表示系統(tǒng)中顧客容量限制，或稱等待空間容量。 B：表示顧客源限制，可取正整數(shù)或，即有限與無限兩種。 C：表示服務規(guī)則，如先到先服務（FCFS），后到先服務(LCFS)等。并規(guī)定，若略去后三項，即指X / Y / Z / / / FCFS的情形。本章只討論先到先服務FCFS的情形，因此一般略去第六項。編輯課件編輯課件四、排隊問題的求解四、排隊問題的求解一個實際的系統(tǒng)模型在分析求解時，先要研究整個系統(tǒng)的組成部分屬于哪種類型，如顧客的輸入過程、排隊規(guī)則、服務機構(gòu)的組織結(jié)構(gòu)等。其中，顧客的相繼到達間隔和服務時間的分布都需要通過統(tǒng)計檢驗

12、后確定。解排隊問題的目的是研究排隊系統(tǒng)運行的效率，估計服務質(zhì)量，確定系統(tǒng)參數(shù)的最優(yōu)值，以決定系統(tǒng)的結(jié)構(gòu)是否合理，研究設(shè)計改進措施等。因此必須確定用以衡量系統(tǒng)運行優(yōu)劣的基本數(shù)量指標，解決排隊問題首先要求出這些數(shù)量指標的概率分布或特征數(shù)。常用的系統(tǒng)運行指標有如下幾個。編輯課件編輯課件(1) 損失率在損失制服務系統(tǒng)中，由于服務臺全被占用而使顧客損失的概率，是損失制系統(tǒng)的主要服務質(zhì)量指標。編輯課件編輯課件(2)隊長與隊列長隊長指服務系統(tǒng)中逗留的顧客總數(shù)，其期望值記作Ls ；隊列長指服務系統(tǒng)中排隊等待的顧客總數(shù)，其期望值記作Lq 編輯課件編輯課件(3)逗留時間和等待時間逗留時間指一個顧客進入服務系統(tǒng)后到

13、離開服務系統(tǒng)的時間，包括等待時間和接受服務的時間，其期望值記作Ws；等待時間是顧客排隊等待服務的時間，其期望值記作Wq；一般系統(tǒng)中，等待時間是主要的質(zhì)量指標，但有些系統(tǒng)，如碼頭卸船則不僅要計算等待時間，也要計算服務時間。編輯課件編輯課件(4)服務設(shè)施利用率服務設(shè)施利用率指服務設(shè)施包括服務臺的工時利用情況。這是一個重要的經(jīng)濟效益指標，這一指標往往是和服務質(zhì)量指標相矛盾的。編輯課件編輯課件(5)忙期忙期指服務臺不間斷地為顧客一段時間的長度。對服務臺來說，忙期與閑期總是交替出現(xiàn)的。忙期長說明服務臺的工時利用率高，工作強度大。編輯課件編輯課件計算上述指標的基礎(chǔ)是表達系統(tǒng)狀態(tài)的概率。所謂系統(tǒng)狀態(tài)是指系統(tǒng)

14、中逗留的顧客數(shù)，如果系統(tǒng)中有 j個顧客，就說明系統(tǒng)處于j狀態(tài)。系統(tǒng)狀態(tài)一般是隨時間改變的，我們通常只計算在時刻t系統(tǒng)狀態(tài)為j的概率，用Pj(t) 表示。系統(tǒng)狀態(tài)數(shù)受系統(tǒng)容量和排隊規(guī)則的限制。例如，在損失制系統(tǒng)中，系統(tǒng)狀態(tài)數(shù)最多和服務臺數(shù)相等，而在隊長不受限制的系統(tǒng)中，系統(tǒng)狀態(tài)數(shù)可以是無限的。 編輯課件編輯課件求狀態(tài)概率Pj(t) ，先要建立含Pj(t)的方程組，因j只能是非負整數(shù)，而t是連續(xù)變量，所建立的方程組一般屬微分方程組，其解是瞬態(tài)性質(zhì)，不容易求解。因此，我們常取穩(wěn)態(tài)解，即令 lim t Pj(t) = Pj穩(wěn)態(tài)解的物理意義是，當系統(tǒng)開始運行一定長度的時間后，系統(tǒng)的狀態(tài)概率分布逐漸趨于穩(wěn)

15、定，不再隨時間的變化而變化。編輯課件編輯課件實際上，并不需要t ，系統(tǒng)才會穩(wěn)定下來。如百貨商場剛開門時，顧客必然進的多，出的少， Pj(t)隨時間改變，但當過一段時間后，進、出的顧客大體上就達到平衡，狀態(tài)概率就呈現(xiàn)穩(wěn)定狀態(tài)，所以穩(wěn)態(tài)也稱統(tǒng)計平衡狀態(tài)。求穩(wěn)態(tài)概率是，只需令Pj(t) =0 即可。編輯課件編輯課件在排隊系統(tǒng)中，顧客相繼到達的時間間隔與服務的時間分布主要有:負指數(shù)分布;泊松分布;愛爾朗分布等。編輯課件編輯課件一、泊松過程一、泊松過程設(shè)N(t) 表示在0,t) 時段內(nèi)到達的顧客數(shù)(t0) 令Pn(t1,t2) 表示在時間區(qū)間t1,t2) (t2t1) 內(nèi)有n(n0) 個顧客到達（隨機事

16、件）的概率，即:編輯課件編輯課件當 Pn(t1,t2)符合以下三個條件時，就說顧客的到達形成泊松流。 在不相重疊的時間區(qū)間內(nèi)顧客到達數(shù)是相互獨立的，稱為無后效性。 對充分小的t ，在時間區(qū)間 t , t+ t) 內(nèi)有1個顧客到達的概率與t無關(guān)，近似與區(qū)間長t成正比，即 其中，o(t ) ，當 t 0時，是關(guān)于t的高階無窮小。 0是常數(shù)，表示單位時間有一個顧客到達的概率，稱為概率強度。 對于充分小的 t ，在時間區(qū)間t , t+ t) 內(nèi)有2個或2個以上顧客到達的概率極小，以至于可以忽略，即編輯課件編輯課件在上述條件下，我們研究顧客到達數(shù)n的概率分布.由條件，我們總可以取時間由0算起,簡記Pn(

17、0, t) = Pn(t) 由條件和，容易推得在t , t+ t) 區(qū)間內(nèi)沒有顧客到達的概率在求Pn(t)時，用通常建立未知函數(shù)的微分方程的方法，先求未知函數(shù)Pn(t)由時刻t到t+ t的改變量，從而建立t時刻的概率分布與t+ t時刻概率分布的關(guān)系方程。對于區(qū)間 0 , t+ t) 可分成兩個互不重疊的區(qū)間 0 , t) 和 t , t+ t) ?，F(xiàn)在到達總數(shù)n，分別出現(xiàn)在這兩區(qū)間上，只有以下三種情況。各種情況出現(xiàn)個數(shù)和概率見下表9-2。 編輯課件編輯課件表9-2 各種情況出現(xiàn)個數(shù)和概率編輯課件編輯課件在0 , t+ t) 內(nèi)到達n個顧客應是表中互不相容的情況之一，所以概率Pn(t + t)

18、應是表中三個概率之和（各 o(t)合為一項） 令t 0, 得下列方程，并注意到初始條件，則有編輯課件編輯課件當n=0時，(B)、(C)兩種情況不存在，所以得解上述兩式，就得Pn(t)表示長為t的時間區(qū)間內(nèi)到達n個顧客的概率，由上式(9-9)，根據(jù)概率論可知，隨機變量N(t)=N(s+t)-N(s)服從泊松分布。 期望值EN(t)= t；方差VarN(t)= t期望值與方差相等，是泊松分布的一個重要特征，可以利用此性質(zhì)對一個經(jīng)驗分布是否合于泊松分布進行初步的判別。編輯課件編輯課件二、負指數(shù)分布二、負指數(shù)分布若隨機變量T的概率密度為則稱T服從負指數(shù)分布。其分布函數(shù)為數(shù)學期望 方差 標準差 編輯課件

19、編輯課件負指數(shù)分布有以下性質(zhì)：(1)密度函數(shù)fT(t) 對時間t嚴格遞減(2)由條件概率公式容易證明 稱為無記憶性或馬爾可夫性。若T表示排隊系統(tǒng)中顧客到達的間隔時間，該性質(zhì)說明一個顧客到來所需的時間與過去一個顧客到來所需的時間s 無關(guān)，這種情形下的顧客到達是完全隨機的；編輯課件編輯課件(3)當輸入的過程是泊松流時，那么顧客相繼到達的間隔時間T必須服從負指數(shù)分布。這是因為對于泊松流,在 0 , t)區(qū)間內(nèi)至少有1個顧客到達的概率是 此概率又可以表示為 因此，相繼到達的間隔時間是獨立且為同負指數(shù)分布（密度函數(shù) e- t ,t 0），與輸入過程為泊松流（參數(shù)為 ）是等價的。所以在Kendall記號中

20、都用M表示。對于泊松流， 表示單位時間平均到達的顧客，所以1/ 就表示相繼顧客到達平均間隔時間，而這正和ET的意義相符。編輯課件編輯課件服務時間v是對一顧客的服務時間，也就是在忙期相繼離開系統(tǒng)的兩顧客的間隔時間，一般也服從負指數(shù)分布。設(shè)它的分布函數(shù)和密度分別是其中， 表示單位時間接受服務的顧客數(shù)，稱為平均服務率1/=E(v) 表示一個顧客的平均服務時間，即期望值。編輯課件編輯課件三、愛爾朗分布三、愛爾朗分布若隨機變量V具有下述密度函數(shù)：則稱V服從參數(shù)為的k階愛爾朗分布，記為 V Ek()。由概率論，若隨機變量為 V Ek() ，則其期望與方差為編輯課件編輯課件愛爾朗分布具有已下性質(zhì)(1)當k=

21、1時，愛爾朗分布就成為指數(shù)分布；當k增大，方差 減小，的取值密集于均值 附近，愛爾朗分布近似于正態(tài)分布；當k 時，D (V) 0, V趨近于常數(shù) ，愛爾朗分布近似于定長分布。編輯課件編輯課件(2)設(shè)隨機變量 V1,V2,V3,Vk相互獨立且服從于相同參數(shù)k的指數(shù)分布。設(shè)V=V1+V2+V3+Vk= Vi ，則V Ek()性質(zhì)的實際意義：假設(shè)一個服務系統(tǒng)具有個串聯(lián)服務臺，每臺服務時間Vi (i=1,2,k)相互獨立，都服從具有參數(shù)k 的指數(shù)分布，而且k個服務臺依次全部完成對一個顧客的服務后，下一個顧客才進入第一個服務臺開始接受服務，那么該系統(tǒng)對任一顧客服務時間 為： 編輯課件編輯課件單服務臺的排

22、隊系統(tǒng)，它的輸入過程服從泊松分布的過程，服務時間服從負指數(shù)分布。討論以下三種情形： 標準的 M/M/1模型，即 M/M/1/ / ； 系統(tǒng)容量有限，即M/M/1/ N/ ； 顧客源為有限，即 M/M/1/ /m 。編輯課件編輯課件一、一、 標準的標準的 M/M/1模型模型 （ M/M/1/ / ）標準的 M/M/1 模型的排隊系統(tǒng)符合以下條件： 輸入過程顧客源是無限的，顧客單個到來，相互獨立，一定時間的到達數(shù)服從泊松分布，到達過程是平穩(wěn)的。 排隊規(guī)則單隊，隊長無限制，先到先服務。 服務機構(gòu)各顧客的服務時間是相互獨立的，服從相同的負指數(shù)分布。此外，假設(shè)顧客相繼到達的間隔時間和服務時間是相互獨立的

23、。編輯課件編輯課件分析標準的M/M/1 模型首先要求出系統(tǒng)在任意時刻t的狀態(tài)n（系統(tǒng)中有n個顧客）的概率Pn(t) ，它決定了系統(tǒng)的運行的特征。因已知到達規(guī)律服從參數(shù)為 的泊松過程，服務時間服從參數(shù)為的負指數(shù)分布，所以在 t , t+ t)時間區(qū)間內(nèi)分為： 有1個顧客到達的概率為 t+o(t) ；沒有顧客到達的概率為1- t+o(t) 。 當有顧客在接受服務時，1個顧客被服務完了（離去）的概率為 t+o(t) ，沒有離去的概率為 1- t+o(t) 。 多于1個的顧客到達或離去的概率是o(t) ，可忽略不計。編輯課件編輯課件在t+ t時刻 ，系統(tǒng)中有n個顧客（n0 ）存在以下四種情況：表9-3

24、系統(tǒng)中有n個顧客的情形編輯課件編輯課件由于這四種情況是互不相容的，所以Pn(t+ t) 應是這四項之和，即（將關(guān)于t) 的高階無窮小合并為一項）令t 0 ，則關(guān)于Pn(t) 的微分方程編輯課件編輯課件當n=0 ，則只有表9-3中的(A)，(B)兩種情況，即同理可得此時系統(tǒng)狀態(tài)(n)隨時間變化的過程就成為生滅過程的一個特殊情形。編輯課件編輯課件解方程(9-16)與(9-17)很復雜，求得的解（瞬態(tài)解）不便于應用，因此只研究穩(wěn)態(tài)的情況，此時 Pn(t)與t無關(guān)，可寫成 Pn，它的導數(shù)為0由以上的微分方程可得這是關(guān)于Pn(t)的差分方程。它表明了各狀態(tài)間的轉(zhuǎn)移關(guān)系如圖9-3所示.圖9-3 狀態(tài)轉(zhuǎn)移關(guān)

25、系編輯課件編輯課件由圖9-3可知，狀態(tài)0轉(zhuǎn)移到狀態(tài)1的轉(zhuǎn)移率為 P0(t) ，狀態(tài)1轉(zhuǎn)移到狀態(tài)0的轉(zhuǎn)移率為 P1(t) 。狀態(tài)0必須滿足以下平衡方程 P0(t) = P1(t) 同樣對任何 n1的狀態(tài)，可得（9-19）平衡方程。求解（9-18）可得P1將其代入（9-19），令 n=1，可得所以P2同理依次推得Pn編輯課件編輯課件設(shè) (否則隊列將排至無限長)，由概率的性質(zhì)可知 ,將Pn的關(guān)系代入，得因此，系統(tǒng)狀態(tài)為n 的概率：由（9-20）式， =1- P0，它描述了服務機構(gòu)的繁忙程度；所以又稱服務機構(gòu)的利用率。編輯課件編輯課件有實際的意義根據(jù)表達式的不同，可以有不同的解釋。當 時，是平均到達率

26、與平均服務率之比；即在相同時區(qū)內(nèi)顧客到達的平均數(shù)與被服務的平均數(shù)之比。若表示為 ，它為一個顧客的服務時間與到達間隔時間之比；稱 為服務強度，或稱 為話務強度（早期排隊論是愛爾朗等人在研究電話理論時用的術(shù)語，沿用至今）。編輯課件編輯課件以（9-20）式為基礎(chǔ)，可以算出系統(tǒng)的各個運行指標。 在系統(tǒng)中的平均顧客數(shù)（隊長期望值）(2)在隊列中等待的平均顧客數(shù)（隊列長期望值）或者編輯課件編輯課件關(guān)于顧客在系統(tǒng)中逗留的時間W(隨機變量)，在 M/M/1情形下，它服從參數(shù)為 - 的負指數(shù)分布，即分布函數(shù) 概率密度 在系統(tǒng)中顧客逗留的時間的期望值 在隊列中顧客等待時間的期望值編輯課件編輯課件以上公式總結(jié)：它們

27、之間的關(guān)系如下：稱為Little(李特爾)公式編輯課件編輯課件例9-1在集裝箱堆場中的作業(yè)集裝箱泊位遵從先到先服務，車輛經(jīng)過作業(yè)泊位服從負指數(shù)分布，每輛車平均需要15秒。車輛進入車道服從泊松分布，平均每小時3輛。解：對此隊列分析如下：模型為M/M/1/ / .(1) 先確定參數(shù)值：由題意知，這是單服務臺模型系統(tǒng)，有=3(輛/小時) = 60/15=4(輛/小時) 故服務強度為=/ (2) 計算穩(wěn)態(tài)概率 p0=1-=1-0.75=0.25; pn=n p0其中，p0是車道空閑的概率，也是車輛不必等待立即就能進入車道的概率。而車輛需要等待的概率，也是車道繁忙的概率為p(n0)=1- p0=編輯課件

28、編輯課件 計算系統(tǒng)的主要工作指標：此模型的平均有效到達率，即是到達率編輯課件編輯課件 為使車輛平均逗留時間不超過半分鐘，車輛經(jīng)過車道的平均時間應減少到多少？由于將=3代入上式解得：5車輛經(jīng)過車道的平均時間為即車輛經(jīng)過車道的平均時間至少應減少3分。編輯課件編輯課件二、系統(tǒng)的容量有限的情況二、系統(tǒng)的容量有限的情況（M/M/1/N/ ）若系統(tǒng)的最大容量為N ，對于單服務臺的情形，排隊等待的顧客最多為N-1 ，在某時刻一顧客到達時，如果系統(tǒng)中已有N個顧客，那么這個顧客就被拒絕進入系統(tǒng)（如圖9-4）。圖9-4 有容量限制的情形當N=1時，為即時制的情形；當N ，為容量無限制的情形。編輯課件編輯課件若只考

29、慮穩(wěn)態(tài)的情形，各狀態(tài)間概率強度的轉(zhuǎn)換關(guān)系如圖9-5。圖9-5狀態(tài)間概率強度的轉(zhuǎn)換關(guān)系編輯課件編輯課件根據(jù)圖9-5列出狀態(tài)概率的穩(wěn)態(tài)方程：解此方程與解（9-18）與（9-19）是相似的，不同的是令 ，得編輯課件編輯課件對于的取值略去=1 情形的討論。當容量沒有限制時，設(shè) 1 時，損失率PN （表示被拒絕排隊的顧客平均數(shù)PN ）很大。編輯課件編輯課件關(guān)于有效到達率e當研究顧客在系統(tǒng)平均逗留時間Ws 和隊列中平均等待時間Wq 時，盡管（9-22）式仍可利用，但要注意平均到達率是在系統(tǒng)中有空時的平均到達率，當系統(tǒng)已滿(n=N) 時，則到達率為0，因此需要求出有效到達率e= (1-PN)可驗證： ,即e

30、 =(1-P0 )編輯課件編輯課件根據(jù)（9-25）可以得出以下指標：(1)隊長（期望值）(2)隊列長（期望值）(3)顧客逗留時間（期望值） (4)顧客等待時間（期望值）編輯課件編輯課件此模型系統(tǒng)的性能指標（當1 時）編輯課件編輯課件例9-2 集裝箱堆場的某作業(yè)集裝箱泊位共7個。當7個處理臺都滿時，后來到的集裝箱不進入該作業(yè)線。集裝箱的平均到達率為3個/小時，處理一個集裝箱平均需要15分。解：則N=7為系統(tǒng)中最大的顧客數(shù)，=3個/小時，=4個/小時。(1)由題意知，模型為（M/M/1/N/）先確定參數(shù)：由題意知，服務強度=/(2)求某集裝箱一到達就能進行作業(yè)的概率。這種情形相當于作業(yè)線內(nèi)沒有集裝

31、箱，所求概率編輯課件編輯課件(3)求作業(yè)線上集裝箱的期望值；需要等待的集裝箱的期望值(4)求有效到達率e e =(1-P0 )=2.11-(1-0.2778)=2.89(個小時)(5)求一集裝箱在作業(yè)線內(nèi)逗留的期望時間；等待時間(6)在可能到來的集裝箱進入其它作業(yè)線的概率(Pn7)。這就是求作業(yè)線內(nèi)有7個集裝箱的概率編輯課件編輯課件三、顧客源有限的情形三、顧客源有限的情形(M/M/1/ /m)該模型中，設(shè)顧客總數(shù)為m，當顧客需要服務時，就進入隊列等待；服務完畢后，重新回到顧客源。如此循環(huán)往復。模型符號的第4項為，表示系統(tǒng)的容量沒有限制，但實際上它決不會超過m，所以跟寫成(M/M/1/m/m)的

32、意義相同。典型的有限顧客源問題是機器維修問題。有m臺機器在運轉(zhuǎn)，單位時間內(nèi)平均出現(xiàn)故障的機器數(shù)即為顧客平均到達率，修理工修理一臺設(shè)備的平均時間即為平均服務時間，已修復的機器仍可能再出現(xiàn)故障（如圖9-6）。圖9-6有限顧客源問題編輯課件編輯課件關(guān)于平均到達率在無限源的情形是按全體顧客來考慮的；在有限源的情形必須按每個顧客來考慮。為簡單起見，設(shè)各個顧客的到達率都是相同的（的含義是每臺機器單位運轉(zhuǎn)時間內(nèi)發(fā)生故障的概率或平均次數(shù)），這時在系統(tǒng)外的顧客平均數(shù)為m-Ls，對系統(tǒng)的有效到達率e應為 e=(m-Ls)編輯課件編輯課件對于此模型的分析依然可以沿用前面的方法。在穩(wěn)態(tài)的情況下，考慮狀態(tài)間的轉(zhuǎn)移率如圖

33、9-7所示。圖9-7狀態(tài)轉(zhuǎn)移編輯課件編輯課件根據(jù)圖9-7列出狀態(tài)概率的穩(wěn)態(tài)方程：解此差分方程，用遞推的方法得編輯課件編輯課件系統(tǒng)的各項指標:編輯課件編輯課件在機器故障問題中Ls就是平均故障臺數(shù)，而(m-Ls)表示正常運轉(zhuǎn)的平均臺數(shù)。編輯課件編輯課件單隊、并列的多服務臺（服務臺數(shù)為c）的情形，討論以下三種情形：(1)標準的M/M/c模型(M/M/c/);(2)系統(tǒng)容量有限制(M/M/c/N/)；(3)有限顧客源(M/M/c/m)。編輯課件編輯課件一、標準的一、標準的M/M/c模型模型(M/M/c/) 標準M/M/c模型的各種特征與標準的M/M/1模型的規(guī)定相同。另規(guī)定各服務臺工作是相互獨立的（非

34、協(xié)作）且平均服務率相同1=1=c=。因此整個服務機構(gòu)的平均服務率c（當nc時）；n（當nc時時，因為只有c個服務臺，最多有c個顧客在被服務，n-c個顧客在等候，因此系統(tǒng)的服務率為c，狀態(tài)的轉(zhuǎn)移率應為cPn。圖9-8 多服務臺服務系統(tǒng)編輯課件編輯課件圖9-9多服務臺服務系統(tǒng)狀態(tài)轉(zhuǎn)移編輯課件編輯課件由圖9-9可得：類似的有Pi=1，且1用遞推解差分方程（9-29），求得狀態(tài)概率：編輯課件編輯課件系統(tǒng)的運行指標平均隊長平均等待時間和逗留時間（由little公式求得）編輯課件編輯課件例：某售票所有三個窗口，顧客到達服從Poisson過程，到達 人/分鐘，服務 人/分鐘。設(shè)顧客到達后依次排成一隊向空閑的

35、窗口購票，如圖 a. 圖圖 a 窗口窗口1 1 =0.4 =0.4 窗口窗口2 2 =0.4 =0.4 窗口窗口3 3 =0.4 =0.4 窗口窗口1 1 =0.4 =0.4 窗口窗口2 2 =0.4 =0.4 窗口窗口3 3 =0.4 =0.4 = 0.3 = 0.3 = 0.3 = 0.9圖圖 b編輯課件編輯課件屬于M/M/c型系統(tǒng) c =3, / =2.25, = / cc），與單服務臺情形類似，顧客的到達率是按單個顧客來考慮的，在機器管理問題中，共有m臺機器，有c個修理工人，顧客到達就是機器出了故障，而每個顧客的到達率 是指每臺機器單位運轉(zhuǎn)時間出故障的期望次數(shù)。系統(tǒng)中顧客數(shù)n就是出故障

36、臺數(shù)，當nc時，所有的故障機器都在被修理，有(c-n)個修理工人在空閑；當cnm時，有(n-c)臺機器在停機等待修理，而修理工都在忙碌狀態(tài)。假定這c個工人修理技術(shù)相同，修理時間都服從參數(shù)為的負指數(shù)分布，并假定故障的修復時間和正在生產(chǎn)的機器是否發(fā)生故障是相互獨立的。編輯課件編輯課件其中由于由于P P0 0,P ,Pn n計算公式過于復雜，有專門的表格可以供查閱。計算公式過于復雜，有專門的表格可以供查閱。編輯課件編輯課件系統(tǒng)的性能指標平均顧客數(shù)（即平均故障臺數(shù)）：有效的到達率e為每個顧客的到達率乘以在系統(tǒng)外（正常運轉(zhuǎn)）的機器的期望數(shù)：e=(m-Ls)；在機器故障問題中，即單位時間m臺機器平均出現(xiàn)故

37、障的次數(shù)。編輯課件編輯課件本節(jié)討論服務時間是任意分布的情形，當然，對任何情形都有下面的關(guān)系：E系統(tǒng)中顧客數(shù)=E隊列中顧客數(shù)+E服務機構(gòu)中顧客數(shù)E在系統(tǒng)中逗留時間=E排隊等待時間+E服務時間其中，E.表示求期望值，用符號表示：Ls=Lq+LseWs=Wq+ET編輯課件編輯課件一、一般分布模型一、一般分布模型(M/G/1/)該模型的基本條件：(1) 輸入過程顧客源是無限的，到達過程服從參數(shù)為的泊松過程； (2)排隊規(guī)則單隊，隊長無限制，先到先服務； (3)服務機構(gòu)單服務臺，G表示服務時間T的分布為任意的概率分布，但已知E(T)和方差Var(T)。此模型被稱為單服務臺泊松到達、任意服務時間的排隊模型

38、。編輯課件編輯課件在穩(wěn)態(tài)情況下，當=E(T)1時，可以證明: 此公式又稱P-K（Pollaczek-Khint chine）公式。只要知道、E(T)、Var(T)，無論服務時間T服從什么分布，均可用P-K公式求出平均隊長Ls。其它的運行指標：編輯課件編輯課件二、定長分布模型二、定長分布模型(M/D/1/)服務時間為確定的常數(shù)，如在一條裝配線上完成一件工作的時間一般都是常數(shù)。自動汽車沖洗臺，沖洗一輛汽車的時間就是常數(shù)，可得：編輯課件編輯課件三、愛爾朗服務時間三、愛爾朗服務時間(M/Ek/1/)此模型中每一個顧客必須一次經(jīng)過k個服務臺，接受k次服務后才構(gòu)成一個完整服務過程。在每個服務臺的服務時間T

39、i相互獨立，并服從相同的負指數(shù)分布（參數(shù)為k），那么 服從k階愛爾朗分布。編輯課件編輯課件對于(M/Ek/1/)模型（除服務時間外，其它條件與標準的M/M/1/型相同）編輯課件編輯課件一、排隊系統(tǒng)經(jīng)濟分析一、排隊系統(tǒng)經(jīng)濟分析試圖完全消除排隊現(xiàn)象是不現(xiàn)實的，那樣顯然會造成服務人員和設(shè)施的嚴重浪費。另一方面，如果設(shè)施不足或服務低水平，將導致過多的等待，因而產(chǎn)生生產(chǎn)和社會損失。從經(jīng)濟角度考慮，一般排隊系統(tǒng)的費用應該包含于以下兩個方面： 服務費用。它隨著服務水平（反映在服務能力和服務臺數(shù)量方面）的提高而增加，是服務水平的遞增函數(shù)。 顧客等待的機會損失（費用）。顧客由于等待，產(chǎn)生一系列的損失（時間上、心

40、理上、社會上等）用經(jīng)濟費用進行的估算，稱為顧客等待的機會損失。它隨服務水平的提高而下降，是服務水平的遞減函數(shù)。 編輯課件編輯課件這兩方面構(gòu)成的函數(shù)呈現(xiàn)為一條如圖所示的U型曲線。圖圖9-10 費用與服務水平之間的關(guān)系費用與服務水平之間的關(guān)系F1、F2、Y分別是服務費用函數(shù)、等待費用函數(shù)、合成費用函數(shù)。分別是服務費用函數(shù)、等待費用函數(shù)、合成費用函數(shù)。編輯課件編輯課件系統(tǒng)的最優(yōu)化的目標就是尋求這個合成費用曲線的最小點。在這種意義下，排隊系統(tǒng)的最優(yōu)化問題通常分為兩類：一類稱之系統(tǒng)的靜態(tài)最優(yōu)設(shè)計，目的在于使設(shè)備到達最大效益，或者說，在保證一定服務質(zhì)量指標的前提下，要求機構(gòu)最為經(jīng)濟；另一類叫做系統(tǒng)動態(tài)最優(yōu)

41、運營，是指一個給定排隊系統(tǒng)，如何運營可使某個目標函數(shù)得到最優(yōu)。本節(jié)只討論系統(tǒng)靜態(tài)的最優(yōu)設(shè)計問題。編輯課件編輯課件歸納起來，排隊系統(tǒng)常見的優(yōu)化問題在于：確定服務臺的最優(yōu)平均服務率*；確定最佳服務臺數(shù)量s*；選擇最為合適的服務規(guī)則；確定上述幾個量得最優(yōu)組合。研究排隊系統(tǒng)的根本目的在于以最少的設(shè)備得到最大的效益，或者說，在一定的服務質(zhì)量的指標下要求機構(gòu)最為經(jīng)濟。編輯課件編輯課件二、二、M/M/1系統(tǒng)的最優(yōu)平均服務率系統(tǒng)的最優(yōu)平均服務率1標準的M/M/1模型設(shè)c1為當=1時服務系統(tǒng)單位時間的平均費用，并且這個平均費用與評級均服務率成正比例；cw為平均每個顧客在逗留單位時間的損失；Y為整個系統(tǒng)單位時間的

42、平均總費用。其中c1、cw均為已知（以下情形相同）。目標函數(shù)：將M/M/1模型的平均隊長公式L=/(-)代入(9-41)式，得：編輯課件編輯課件顯然，Y是關(guān)于決策變量的一元非線性函數(shù)。由一階最優(yōu)性必要條件（駐點條件）解得駐點取算術(shù)平方根是為了保證，這樣，系統(tǒng)才能達到穩(wěn)態(tài)。又知二階充分條件成立：于是，式(9-43)給出的*為(,)上的全局唯一最小點。將*帶入(9-42)中，可得最小的總平均費用編輯課件編輯課件若設(shè)cw為平均每個顧客在隊列中等待單位時間的損失，則需要M/M/1模型的平均隊列長公式 代入式(9-41)中的L，類似可得一階最優(yōu)性必要條件：這是一個關(guān)于的4次方程，實際中一般采用數(shù)值法（如

43、牛頓法）來確定其根（最優(yōu)服務率）*。編輯課件編輯課件2. 系統(tǒng)中顧客最大限制為系統(tǒng)中顧客最大限制為N的情形的情形在這情形下，系統(tǒng)中如已有N個顧客，則后來的顧客即被拒絕，可知：PN 被拒絕的概率；1- PN 能被接受的概率；(1- PN)單位時間實際進入服務機構(gòu)顧客的平均數(shù)。在穩(wěn)定狀態(tài)下，它也等于單位時間內(nèi)實際服務完成的平均顧客數(shù)。編輯課件編輯課件設(shè)每服務1人能收入G元，于是單位時間收入的期望值是(1- PN)G元。純利潤：最優(yōu)的解*應該符合上式(9-45)。上式中c1、G、N都是給定的，但要由上式中解出*是很復雜的。通常是通過數(shù)值計算來求*的，或?qū)⑸鲜阶蠓剑▽σ欢ǖ腘）作為的函數(shù)作出圖形進行求

44、解。編輯課件編輯課件3. 顧客源為有限的情形顧客源為有限的情形按機械故障問題來考慮。設(shè)共有機器m臺，各臺連續(xù)運轉(zhuǎn)時間服從負指數(shù)分布。有1個修理工人，修理時間服從負指數(shù)分布。當服務率=1時的修理費用c1，單位時間每臺機器運轉(zhuǎn)可得收入G元。平均運轉(zhuǎn)臺數(shù)為m-Ls，所以單位時間純利潤：編輯課件編輯課件當給定m、G、c1、，要由上式中解出*是很困難的，通常是利用泊松分布表通過數(shù)值計算來求得，或?qū)⑸鲜阶蠓剑▽σ欢ǖ膍）作為的函數(shù)作出圖形進行求解。編輯課件編輯課件三、三、M/M/c系統(tǒng)的最優(yōu)服務臺數(shù)系統(tǒng)的最優(yōu)服務臺數(shù)c設(shè)排隊系統(tǒng)M/M/c，確定最佳服務臺數(shù)c的目標函數(shù)為：其中：c為待定的共享并聯(lián)服務臺的個

45、數(shù)；Y(c)為整個系統(tǒng)單位時間的平均費用，它是關(guān)于服務臺數(shù)c的函數(shù)；c2為每個服務臺單位時間內(nèi)的平均費用（各服務臺相同）；cw為平均每個顧客在系統(tǒng)中逗留單位時間的損失；L(c)為平均隊長，它是關(guān)于服務臺數(shù)c的函數(shù)。編輯課件編輯課件要確定最優(yōu)服務臺數(shù)c1,2,，使由于c取值離散，不能采用微分方法或非線性規(guī)劃的方法，因此，只需要同時滿足下式即可：采用差分法，可導出另一關(guān)系式。把式(9-50)代入式(9-51)中，得編輯課件編輯課件令依次計算時的值，根據(jù)落在哪兩個差值之間就可確定c*。另外，若設(shè)cw為平均每個顧客在隊列中等待單位時間的損失，則需要M/M/c模型的平均隊列長公式Lq(c)取代式(9-5

46、0)中的L(c)，由于在此情況下不需求導數(shù)，所以只要把相應公式中的L(c)用Lq(c)取代即可。編輯課件編輯課件 例例7 某儲蓄所有一個服務窗口，顧客按泊松分布平均每小時某儲蓄所有一個服務窗口，顧客按泊松分布平均每小時 到達到達10人。為任一顧客辦理存款、取款等業(yè)務的時間人。為任一顧客辦理存款、取款等業(yè)務的時間 V(小時小時), ,2). 試求該儲蓄所空閑的概率及其主要工作指標。試求該儲蓄所空閑的概率及其主要工作指標。 解解從而根據(jù)從而根據(jù)波拉切克波拉切克欣欽欣欽公式，可以導出：公式，可以導出：L q= + 2 2( 1 - -)22(11-53)進而按進而按(11-1)式可算出式可算出L,

47、, W, , Wq; ; 其中其中 = 。 2 =2 (小時小時/人人)2= 10 (人人/小時小時)1= 0.05 (小時小時/人人)編輯課件編輯課件= 該儲蓄所空閑的概率：該儲蓄所空閑的概率： = 1 - - = = 10() = = = 1 - -L = Lq +L q = 0.52+102(0.01)22(1- -0.5)W = LWq =Lq則則主要指標主要指標= 0.26 += =10= (小時小時) (分鐘分鐘)= (小時小時) (分鐘分鐘)編輯課件編輯課件 二、二、 M/ /D/ /1系統(tǒng)系統(tǒng) 該系統(tǒng)對各顧客服務時間相互獨立且為同一個常數(shù)該系統(tǒng)對各顧客服務時間相互獨立且為同一個

48、常數(shù) ，故有故有 E( ) = =1 例例8 某檢測站有一臺自動檢測機器性能的儀器，檢測每臺某檢測站有一臺自動檢測機器性能的儀器，檢測每臺機器都需機器都需6分鐘。送檢機器按泊松分布到達，平均每小時分鐘。送檢機器按泊松分布到達，平均每小時4臺。臺。試求該系統(tǒng)的主要工作指標。試求該系統(tǒng)的主要工作指標。D( ) = 0 (=2)(11-54)Lq= 2(1 - -)2編輯課件編輯課件 = 4臺臺/小時小時 = 6分鐘分鐘/臺臺 =小時小時/ /臺臺 2 = 0，L = Lq+= 2/15 + = 8/15( (臺臺) ) Wq = Lq/ = 2/4(15) = 1/30( (小時小時) ) = 2

49、( (分鐘分鐘) )W = Wq+ 1/= 2 + 6 = 8( (分鐘分鐘) )0.422(1- - 0.4)Lq = = 2/15( (臺臺) )= = 4(0.1) = 0.4解解編輯課件編輯課件 該系統(tǒng)對任一顧客的服務時間該系統(tǒng)對任一顧客的服務時間 VEk()，有，有 E(V) = 1/， D(V) = 1/k2 (=2 )三三、M/ /Ek/ /1系統(tǒng)系統(tǒng)(11-55) +k2(1 - -)L q =2 22 22 2=(k+1) 2k ( 1 - -) 2編輯課件編輯課件 例例9 一個質(zhì)量檢查員平均每小時收到一個質(zhì)量檢查員平均每小時收到兩件兩件送來檢查的送來檢查的樣品，每件樣品要一

50、次完成樣品，每件樣品要一次完成 項檢驗才能判斷是否合格。據(jù)項檢驗才能判斷是否合格。據(jù)統(tǒng)計，每項檢驗所需時間的期望值都是統(tǒng)計，每項檢驗所需時間的期望值都是 分鐘，每項檢驗的分鐘，每項檢驗的時間和送檢產(chǎn)品到到達間隔都為指數(shù)分布。問一件樣品從時間和送檢產(chǎn)品到到達間隔都為指數(shù)分布。問一件樣品從送到至檢查完畢預期要多少時間？送到至檢查完畢預期要多少時間？ 解解 = 2 件件/ /小時小時 k k = 1/(5 ) = 4 (分鐘分鐘/ /件件) E(Vi i) = 1/ /(k k )，i = 1，2，3，4，51/= 20 (分鐘分鐘/件件) = (小時小時/件件)由由有有則則編輯課件編輯課件 = /

51、= 2() = Lq = Wq = Lq/ = / = (小時小時) W = Wq + 1/= + = 11/15 (小時小時) = (5+1 )()225(1 - - )=編輯課件編輯課件 c1 當當= 1時時 服務系統(tǒng)單位時間的平均費用服務系統(tǒng)單位時間的平均費用 cw 平均每個顧客在系統(tǒng)逗留單位時間的損失平均每個顧客在系統(tǒng)逗留單位時間的損失 整個系統(tǒng)單位時間的平均總費用整個系統(tǒng)單位時間的平均總費用 其中其中c1 ，cw可知，目標函數(shù)為可知，目標函數(shù)為 = c1 + cwL一、一、M/M/1/ 系統(tǒng)的最優(yōu)平均服務率系統(tǒng)的最優(yōu)平均服務率設(shè)設(shè)(11-56)將將 L =/（）代入上式，得代入上式，得 = c1 + cw/（）求導求導, ,得得dd= c1 - -cw1（）2編輯課件編輯課件解得駐點解得駐點(11-57)又由又由dyd=2cw（）3 0（因因）知：知：為為（ ， ）上的全局唯一極小點；代入上的全局唯一極小點；代入(11-56)得