管理運(yùn)籌學(xué)10服務(wù)系統(tǒng)規(guī)劃

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

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

3、無形的，集中的或分散的。服務(wù)臺可以是人，如維修工人；也可以是設(shè)施，如投幣電話亭；還可以是一個(gè)系統(tǒng)，如醫(yī)生、護(hù)士、手術(shù)臺、手術(shù)機(jī)械、藥品等的有機(jī)整體構(gòu)成一個(gè)服務(wù)臺；服務(wù)臺可以是固定的，也可以是流動(dòng)的，如沿街叫賣的個(gè)體商販；服務(wù)方式也可以是登門服務(wù)，如自來水、供電、煤氣公司派人到用戶住址看表計(jì)價(jià)，維修工人到故障機(jī)器前進(jìn)行維修，等等。表9-1 現(xiàn)實(shí)中的各種服務(wù)系統(tǒng)顧客服務(wù)內(nèi)容服務(wù)臺考生報(bào)名登記招考登記員病人診斷病情醫(yī)生電話呼叫通話交換臺駛?cè)敫劭诘呢洿b（卸）貨裝（卸）貨碼頭（泊位）文件稿打字打字員提貨單提取存貨倉庫管理員不能運(yùn)轉(zhuǎn)的機(jī)器修理修理技工上游河水進(jìn)入水庫放水，調(diào)整水位水閘管理員進(jìn)入我方陣地的

4、敵機(jī)我方高射炮進(jìn)行射擊我方高射炮二、排隊(duì)系統(tǒng)的組成和特征二、排隊(duì)系統(tǒng)的組成和特征 一般的排隊(duì)系統(tǒng)都有三個(gè)基本組成部分：輸入過程；排隊(duì)規(guī)則；服務(wù)機(jī)構(gòu)。1. 輸入過程輸入過程 輸入即指顧客到達(dá)排隊(duì)系統(tǒng)，可能有以下各種不同情況。 顧客的總體（顧客源）的組成可能是有限的，也可能是無限的。上游河水流入水庫可以認(rèn)為總體是無限的，工廠內(nèi)停機(jī)待修的機(jī)器顯然是有限的總體。 顧客到來的方式可能是一個(gè)一個(gè)的，也可能是成批的。例如到餐廳就餐就有單個(gè)到來的顧客和受邀請來參加宴會(huì)的成批顧客，我們將只研究單個(gè)到來的情形。 顧客相繼到達(dá)的間隔時(shí)間可以是確定型的，也可以是隨機(jī)型的。如在自動(dòng)裝配線上裝配的各部件就必須按確定的時(shí)間

5、間隔到達(dá)裝配點(diǎn)，定期運(yùn)行的班車、班輪、班機(jī)的到達(dá)也都是確定型的。但一般到商店購物的顧客、到醫(yī)院診病的病人、通過路口的車輛等，它們的到達(dá)都是隨機(jī)型的。對于隨機(jī)型的情形，要知道單位時(shí)間內(nèi)的顧客到達(dá)數(shù)或相繼到達(dá)的間隔時(shí)間的概率分布。 顧客的到達(dá)可以是相互獨(dú)立的，就是說，以前的到達(dá)情況對以后顧客的到來沒有影響，否則就是有關(guān)聯(lián)的。例如，工廠內(nèi)的機(jī)器在一個(gè)短的時(shí)間區(qū)間內(nèi)出現(xiàn)停機(jī)（顧客到達(dá)）的概率就受已經(jīng)待修或被修理的機(jī)器數(shù)目的影響。本章主要討論的是相互獨(dú)立的情形。 輸入過程可以是平穩(wěn)的，或稱對時(shí)間是齊次的，是指描述相繼到達(dá)的間隔時(shí)間分布和所含參數(shù)（如期望值、方差等）都是與時(shí)間無關(guān)的，否則稱為非平穩(wěn)的。非平

6、穩(wěn)情形的數(shù)學(xué)處理是很困難的。2. 排隊(duì)規(guī)則排隊(duì)規(guī)則 顧客到達(dá)時(shí)，若所有服務(wù)臺都正被占用，在這種情形下顧客可以隨即離去，也可以排隊(duì)等候。隨即離去的稱為即時(shí)制或稱損失制（因?yàn)槭У粼S多顧客）；排隊(duì)等候的稱為等待制。普通市內(nèi)電話的呼喚屬于前者，而登記市外長途電話的呼喚屬于后者。對于等待制，為顧客進(jìn)行服務(wù)的次序可采用下列各種規(guī)則：1）先到先服務(wù)，即按顧客到達(dá)次序接受服務(wù)，這是最通常的情形。2）后到先服務(wù)，如乘電梯的顧客常是后入先出的。倉庫中存放的厚鋼板也是如此。在情報(bào)系統(tǒng)中，最后到達(dá)的信息往往是最有價(jià)值的，而采用后到先服務(wù)（指被采用）的規(guī)則。3）隨機(jī)服務(wù)，指服務(wù)員從等待的顧客中隨機(jī)選取其一進(jìn)行服務(wù)，而不

7、管到達(dá)的先后，如電話交換臺接通呼喚的電話就是如此。4）有優(yōu)先權(quán)的服務(wù)，如醫(yī)院對病情嚴(yán)重的患者將給予優(yōu)先治療。 從占有的空間來看，隊(duì)列可以排在具體的處所（如售票處、候診室等），也可以是抽象的（如向電話交換臺要求通話的呼喚）。 由于空間的限制或其他原因，有的系統(tǒng)要規(guī)定容量（即允許進(jìn)入排隊(duì)系統(tǒng)的顧客數(shù)）的最大限制；有的沒有這種限制（即認(rèn)為容量可以是無限的）。 從隊(duì)列的數(shù)目看，可以是單列，也可以是多列。在多列的情形，各列間的顧客有的可以相互轉(zhuǎn)移，有的不能（如用繩子或欄桿隔開）。有的排隊(duì)顧客因等候時(shí)間過長而中途退出，有的不能退出（如高速公路上的汽車流），必須堅(jiān)持到被服務(wù)為止。本章將只討論各隊(duì)列間不能互相

8、轉(zhuǎn)移，也不能中途退出的情形。3.服務(wù)機(jī)構(gòu)服務(wù)機(jī)構(gòu)從機(jī)構(gòu)形式和工作情況來看有以下幾種情況。 服務(wù)機(jī)構(gòu)可以沒有服務(wù)員，也可以有一個(gè)或多個(gè)服務(wù)員（服務(wù)臺、通道、窗口等）。例如，在敞架售書的書店，顧客選書時(shí)就沒有服務(wù)員，但交款時(shí)可能有多個(gè)服務(wù)員。 在有多個(gè)服務(wù)臺的情形中，它們可以是平行排列（并列）的，可以是前后排列（串列）的，也可以是混合的。如圖9-2所示。 服務(wù)方式可以對單個(gè)顧客進(jìn)行，也可以對成批顧客進(jìn)行，公共汽車對在站臺等候的顧客就成批進(jìn)行服務(wù)。本章將只研究單獨(dú)的服務(wù)方式。 和輸入過程一樣，服務(wù)時(shí)間也分確定型的和隨機(jī)型的。自動(dòng)沖洗汽車的裝置對每輛汽車沖洗（服務(wù)）的時(shí)間就是確定型的，但大多數(shù)情形的服

9、務(wù)時(shí)間是隨機(jī)型的。對于隨機(jī)型的服務(wù)時(shí)間，需要知道它的概率分布。 和輸入過程一樣，服務(wù)時(shí)間的分布總假定是平穩(wěn)的，即分布的期望值、方差等參數(shù)都不受時(shí)間的影響。三、排隊(duì)模型的分類三、排隊(duì)模型的分類為了區(qū)別各種排隊(duì)系統(tǒng)，根據(jù)輸入過程、排隊(duì)規(guī)則和服務(wù)機(jī)構(gòu)的變化對排隊(duì)模型進(jìn)行描述或分類。1953年肯道爾（kendall）提出一個(gè)分類方法，稱為kendall符號，其形式是 x / y / z；在1971年一次關(guān)于排隊(duì)論符號標(biāo)準(zhǔn)化國際會(huì)議上，將kendall符號擴(kuò)充為以下標(biāo)準(zhǔn)形式：x / y / z / a / b / c 或者 x / y / z : a / b / c kendall各符號的意義：(1)

10、x:表示顧客相繼到達(dá)時(shí)間間隔的概率分布，可以取 m、d 、ek、 g等，其中：m 表示到達(dá)過程為泊松過程或負(fù)指數(shù)分布；d 表示定長輸入；ek 表示k階愛爾朗（erlang）分布；g 表示一般相互獨(dú)立的隨機(jī)分布；(2) y: 表示服務(wù)時(shí)間分布，所用符號與x相同 z：表示服務(wù)臺個(gè)數(shù)，取正整數(shù)。1表示單個(gè)服務(wù)臺，s 表示多個(gè)服務(wù)臺。 a：表示系統(tǒng)中顧客容量限制，或稱等待空間容量。 b：表示顧客源限制，可取正整數(shù)或，即有限與無限兩種。 c：表示服務(wù)規(guī)則，如先到先服務(wù)（fcfs），后到先服務(wù)(lcfs)等。并規(guī)定，若略去后三項(xiàng)，即指x / y / z / / / fcfs的情形。本章只討論先到先服務(wù)fc

11、fs的情形，因此一般略去第六項(xiàng)。四、排隊(duì)問題的求解四、排隊(duì)問題的求解一個(gè)實(shí)際的系統(tǒng)模型在分析求解時(shí)，先要研究整個(gè)系統(tǒng)的組成部分屬于哪種類型，如顧客的輸入過程、排隊(duì)規(guī)則、服務(wù)機(jī)構(gòu)的組織結(jié)構(gòu)等。其中，顧客的相繼到達(dá)間隔和服務(wù)時(shí)間的分布都需要通過統(tǒng)計(jì)檢驗(yàn)后確定。解排隊(duì)問題的目的是研究排隊(duì)系統(tǒng)運(yùn)行的效率，估計(jì)服務(wù)質(zhì)量，確定系統(tǒng)參數(shù)的最優(yōu)值，以決定系統(tǒng)的結(jié)構(gòu)是否合理，研究設(shè)計(jì)改進(jìn)措施等。因此必須確定用以衡量系統(tǒng)運(yùn)行優(yōu)劣的基本數(shù)量指標(biāo)，解決排隊(duì)問題首先要求出這些數(shù)量指標(biāo)的概率分布或特征數(shù)。常用的系統(tǒng)運(yùn)行指標(biāo)有如下幾個(gè)。(1) 損失率在損失制服務(wù)系統(tǒng)中，由于服務(wù)臺全被占用而使顧客損失的概率，是損失制系統(tǒng)的主

12、要服務(wù)質(zhì)量指標(biāo)。(2)隊(duì)長與隊(duì)列長隊(duì)長指服務(wù)系統(tǒng)中逗留的顧客總數(shù)，其期望值記作ls ；隊(duì)列長指服務(wù)系統(tǒng)中排隊(duì)等待的顧客總數(shù)，其期望值記作lq (3)逗留時(shí)間和等待時(shí)間逗留時(shí)間指一個(gè)顧客進(jìn)入服務(wù)系統(tǒng)后到離開服務(wù)系統(tǒng)的時(shí)間，包括等待時(shí)間和接受服務(wù)的時(shí)間，其期望值記作ws；等待時(shí)間是顧客排隊(duì)等待服務(wù)的時(shí)間，其期望值記作wq；一般系統(tǒng)中，等待時(shí)間是主要的質(zhì)量指標(biāo)，但有些系統(tǒng)，如碼頭卸船則不僅要計(jì)算等待時(shí)間，也要計(jì)算服務(wù)時(shí)間。(4)服務(wù)設(shè)施利用率服務(wù)設(shè)施利用率指服務(wù)設(shè)施包括服務(wù)臺的工時(shí)利用情況。這是一個(gè)重要的經(jīng)濟(jì)效益指標(biāo)，這一指標(biāo)往往是和服務(wù)質(zhì)量指標(biāo)相矛盾的。(5)忙期忙期指服務(wù)臺不間斷地為顧客一段時(shí)間

13、的長度。對服務(wù)臺來說，忙期與閑期總是交替出現(xiàn)的。忙期長說明服務(wù)臺的工時(shí)利用率高，工作強(qiáng)度大。計(jì)算上述指標(biāo)的基礎(chǔ)是表達(dá)系統(tǒng)狀態(tài)的概率。所謂系統(tǒng)狀態(tài)是指系統(tǒng)中逗留的顧客數(shù)，如果系統(tǒng)中有 j個(gè)顧客，就說明系統(tǒng)處于j狀態(tài)。系統(tǒng)狀態(tài)一般是隨時(shí)間改變的，我們通常只計(jì)算在時(shí)刻t系統(tǒng)狀態(tài)為j的概率，用pj(t) 表示。系統(tǒng)狀態(tài)數(shù)受系統(tǒng)容量和排隊(duì)規(guī)則的限制。例如，在損失制系統(tǒng)中，系統(tǒng)狀態(tài)數(shù)最多和服務(wù)臺數(shù)相等，而在隊(duì)長不受限制的系統(tǒng)中，系統(tǒng)狀態(tài)數(shù)可以是無限的。 求狀態(tài)概率pj(t) ，先要建立含pj(t)的方程組，因j只能是非負(fù)整數(shù)，而t是連續(xù)變量，所建立的方程組一般屬微分方程組，其解是瞬態(tài)性質(zhì)，不容易求解。因此

14、，我們常取穩(wěn)態(tài)解，即令 lim t pj(t) = pj穩(wěn)態(tài)解的物理意義是，當(dāng)系統(tǒng)開始運(yùn)行一定長度的時(shí)間后，系統(tǒng)的狀態(tài)概率分布逐漸趨于穩(wěn)定，不再隨時(shí)間的變化而變化。實(shí)際上，并不需要t ，系統(tǒng)才會(huì)穩(wěn)定下來。如百貨商場剛開門時(shí)，顧客必然進(jìn)的多，出的少， pj(t)隨時(shí)間改變，但當(dāng)過一段時(shí)間后，進(jìn)、出的顧客大體上就達(dá)到平衡，狀態(tài)概率就呈現(xiàn)穩(wěn)定狀態(tài)，所以穩(wěn)態(tài)也稱統(tǒng)計(jì)平衡狀態(tài)。求穩(wěn)態(tài)概率是，只需令pj(t) =0 即可。在排隊(duì)系統(tǒng)中，顧客相繼到達(dá)的時(shí)間間隔與服務(wù)的時(shí)間分布主要有:1.負(fù)指數(shù)分布;2.泊松分布;3.愛爾朗分布等。一、泊松過程一、泊松過程設(shè)n(t) 表示在0,t) 時(shí)段內(nèi)到達(dá)的顧客數(shù)(t0)

15、 令pn(t1,t2) 表示在時(shí)間區(qū)間t1,t2) (t2t1) 內(nèi)有n(n0) 個(gè)顧客到達(dá)（隨機(jī)事件）的概率，即:當(dāng) pn(t1,t2)符合以下三個(gè)條件時(shí)，就說顧客的到達(dá)形成泊松流。 在不相重疊的時(shí)間區(qū)間內(nèi)顧客到達(dá)數(shù)是相互獨(dú)立的，稱為無后效性。 對充分小的t ，在時(shí)間區(qū)間 t , t+ t) 內(nèi)有1個(gè)顧客到達(dá)的概率與t無關(guān)，近似與區(qū)間長t成正比，即 其中，o(t ) ，當(dāng) t 0時(shí)，是關(guān)于t的高階無窮小。 0是常數(shù)，表示單位時(shí)間有一個(gè)顧客到達(dá)的概率，稱為概率強(qiáng)度。 對于充分小的 t ，在時(shí)間區(qū)間t , t+ t) 內(nèi)有2個(gè)或2個(gè)以上顧客到達(dá)的概率極小，以至于可以忽略，即第九章第九章 服務(wù)系統(tǒng)

16、規(guī)劃服務(wù)系統(tǒng)規(guī)劃在上述條件下，我們研究顧客到達(dá)數(shù)n的概率分布.由條件，我們總可以取時(shí)間由0算起,簡記pn(0, t) = pn(t) 由條件和，容易推得在t , t+ t) 區(qū)間內(nèi)沒有顧客到達(dá)的概率在求pn(t)時(shí)，用通常建立未知函數(shù)的微分方程的方法，先求未知函數(shù)pn(t)由時(shí)刻t到t+ t的改變量，從而建立t時(shí)刻的概率分布與t+ t時(shí)刻概率分布的關(guān)系方程。對于區(qū)間 0 , t+ t) 可分成兩個(gè)互不重疊的區(qū)間 0 , t) 和 t , t+ t) ?，F(xiàn)在到達(dá)總數(shù)n，分別出現(xiàn)在這兩區(qū)間上，只有以下三種情況。各種情況出現(xiàn)個(gè)數(shù)和概率見下表9-2。 表9-2 各種情況出現(xiàn)個(gè)數(shù)和概率在0 , t+ t

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

18、分布函數(shù)為數(shù)學(xué)期望 方差 標(biāo)準(zhǔn)差 負(fù)指數(shù)分布有以下性質(zhì)：(1)密度函數(shù)ft(t) 對時(shí)間t嚴(yán)格遞減(2)由條件概率公式容易證明 稱為無記憶性或馬爾可夫性。若t表示排隊(duì)系統(tǒng)中顧客到達(dá)的間隔時(shí)間，該性質(zhì)說明一個(gè)顧客到來所需的時(shí)間與過去一個(gè)顧客到來所需的時(shí)間s 無關(guān)，這種情形下的顧客到達(dá)是完全隨機(jī)的；(3)當(dāng)輸入的過程是泊松流時(shí)，那么顧客相繼到達(dá)的間隔時(shí)間t必須服從負(fù)指數(shù)分布。這是因?yàn)閷τ诓此闪?在 0 , t)區(qū)間內(nèi)至少有1個(gè)顧客到達(dá)的概率是 此概率又可以表示為 因此，相繼到達(dá)的間隔時(shí)間是獨(dú)立且為同負(fù)指數(shù)分布（密度函數(shù) e- t ,t 0），與輸入過程為泊松流（參數(shù)為 ）是等價(jià)的。所以在kenda

19、ll記號中都用m表示。對于泊松流， 表示單位時(shí)間平均到達(dá)的顧客，所以1/ 就表示相繼顧客到達(dá)平均間隔時(shí)間，而這正和et的意義相符。第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃服務(wù)時(shí)間v是對一顧客的服務(wù)時(shí)間，也就是在忙期相繼離開系統(tǒng)的兩顧客的間隔時(shí)間，一般也服從負(fù)指數(shù)分布。設(shè)它的分布函數(shù)和密度分別是其中， 表示單位時(shí)間接受服務(wù)的顧客數(shù)，稱為平均服務(wù)率1/=e(v) 表示一個(gè)顧客的平均服務(wù)時(shí)間，即期望值。第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃三、愛爾朗分布三、愛爾朗分布若隨機(jī)變量v具有下述密度函數(shù)：則稱v服從參數(shù)為的k階愛爾朗分布，記為 v ek()。由概率論，若隨機(jī)變量為 v ek() ，則其期望與方

20、差為第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃愛爾朗分布具有已下性質(zhì)(1)當(dāng)k=1時(shí)，愛爾朗分布就成為指數(shù)分布；當(dāng)k增大，方差 減小，的取值密集于均值 附近，愛爾朗分布近似于正態(tài)分布；當(dāng)k 時(shí)，d (v) 0, v趨近于常數(shù) ，愛爾朗分布近似于定長分布。第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃(2)設(shè)隨機(jī)變量 v1,v2,v3,vk相互獨(dú)立且服從于相同參數(shù)k的指數(shù)分布。設(shè)v=v1+v2+v3+vk= vi ，則v ek()性質(zhì)的實(shí)際意義：假設(shè)一個(gè)服務(wù)系統(tǒng)具有個(gè)串聯(lián)服務(wù)臺，每臺服務(wù)時(shí)間vi (i=1,2,k)相互獨(dú)立，都服從具有參數(shù)k 的指數(shù)分布，而且k個(gè)服務(wù)臺依次全部完成對一個(gè)顧客的服務(wù)后，下一個(gè)顧

21、客才進(jìn)入第一個(gè)服務(wù)臺開始接受服務(wù)，那么該系統(tǒng)對任一顧客服務(wù)時(shí)間 為： 第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃單服務(wù)臺的排隊(duì)系統(tǒng)，它的輸入過程服從泊松分布的過程，服務(wù)時(shí)間服從負(fù)指數(shù)分布。討論以下三種情形： 標(biāo)準(zhǔn)的 m/m/1模型，即 m/m/1/ / ； 系統(tǒng)容量有限，即m/m/1/ n/ ； 顧客源為有限，即 m/m/1/ /m 。第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃一、一、 標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的 m/m/1模型模型 （ m/m/1/ / ）標(biāo)準(zhǔn)的 m/m/1 模型的排隊(duì)系統(tǒng)符合以下條件： 輸入過程顧客源是無限的，顧客單個(gè)到來，相互獨(dú)立，一定時(shí)間的到達(dá)數(shù)服從泊松分布，到達(dá)過程是平穩(wěn)的。 排隊(duì)規(guī)則單隊(duì)

22、，隊(duì)長無限制，先到先服務(wù)。 服務(wù)機(jī)構(gòu)各顧客的服務(wù)時(shí)間是相互獨(dú)立的，服從相同的負(fù)指數(shù)分布。此外，假設(shè)顧客相繼到達(dá)的間隔時(shí)間和服務(wù)時(shí)間是相互獨(dú)立的。第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃分析標(biāo)準(zhǔn)的m/m/1 模型首先要求出系統(tǒng)在任意時(shí)刻t的狀態(tài)n（系統(tǒng)中有n個(gè)顧客）的概率pn(t) ，它決定了系統(tǒng)的運(yùn)行的特征。因已知到達(dá)規(guī)律服從參數(shù)為 的泊松過程，服務(wù)時(shí)間服從參數(shù)為的負(fù)指數(shù)分布，所以在 t , t+ t)時(shí)間區(qū)間內(nèi)分為： 有1個(gè)顧客到達(dá)的概率為 t+o(t) ；沒有顧客到達(dá)的概率為1- t+o(t) 。 當(dāng)有顧客在接受服務(wù)時(shí)，1個(gè)顧客被服務(wù)完了（離去）的概率為 t+o(t) ，沒有離去的概率為 1

23、- t+o(t) 。 多于1個(gè)的顧客到達(dá)或離去的概率是o(t) ，可忽略不計(jì)。第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃在t+ t時(shí)刻 ，系統(tǒng)中有n個(gè)顧客（n0 ）存在以下四種情況：第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃表9-3系統(tǒng)中有n個(gè)顧客的情形由于這四種情況是互不相容的，所以pn(t+ t) 應(yīng)是這四項(xiàng)之和，即（將關(guān)于t) 的高階無窮小合并為一項(xiàng)）令t 0 ，則關(guān)于pn(t) 的微分方程第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃當(dāng)n=0 ，則只有表9-3中的(a)，(b)兩種情況，即同理可得此時(shí)系統(tǒng)狀態(tài)(n)隨時(shí)間變化的過程就成為生滅過程的一個(gè)特殊情形。第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃解方

24、程(9-16)與(9-17)很復(fù)雜，求得的解（瞬態(tài)解）不便于應(yīng)用，因此只研究穩(wěn)態(tài)的情況，此時(shí) pn(t)與t無關(guān)，可寫成 pn，它的導(dǎo)數(shù)為0由以上的微分方程可得這是關(guān)于pn(t)的差分方程。它表明了各狀態(tài)間的轉(zhuǎn)移關(guān)系如圖9-3所示.第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃圖9-3 狀態(tài)轉(zhuǎn)移關(guān)系由圖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第九章第九章

25、 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃設(shè) (否則隊(duì)列將排至無限長)，由概率的性質(zhì)可知 ,將pn的關(guān)系代入，得因此，系統(tǒng)狀態(tài)為n 的概率：由（9-20）式， =1- p0，它描述了服務(wù)機(jī)構(gòu)的繁忙程度；所以又稱服務(wù)機(jī)構(gòu)的利用率。第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃有實(shí)際的意義根據(jù)表達(dá)式的不同，可以有不同的解釋。當(dāng) 時(shí)，是平均到達(dá)率與平均服務(wù)率之比；即在相同時(shí)區(qū)內(nèi)顧客到達(dá)的平均數(shù)與被服務(wù)的平均數(shù)之比。若表示為 ，它為一個(gè)顧客的服務(wù)時(shí)間與到達(dá)間隔時(shí)間之比；稱 為服務(wù)強(qiáng)度，或稱 為話務(wù)強(qiáng)度（早期排隊(duì)論是愛爾朗等人在研究電話理論時(shí)用的術(shù)語，沿用至今）。第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃以（9-20）式為基礎(chǔ)，可

26、以算出系統(tǒng)的各個(gè)運(yùn)行指標(biāo)。 在系統(tǒng)中的平均顧客數(shù)（隊(duì)長期望值）(2)在隊(duì)列中等待的平均顧客數(shù)（隊(duì)列長期望值）第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃或者關(guān)于顧客在系統(tǒng)中逗留的時(shí)間w(隨機(jī)變量)，在 m/m/1情形下，它服從參數(shù)為 - 的負(fù)指數(shù)分布，即分布函數(shù) 概率密度 在系統(tǒng)中顧客逗留的時(shí)間的期望值 在隊(duì)列中顧客等待時(shí)間的期望值第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃以上公式總結(jié)：第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃它們之間的關(guān)系如下：稱為little(李特爾)公式例9-1在集裝箱堆場中的作業(yè)集裝箱泊位遵從先到先服務(wù)，車輛經(jīng)過作業(yè)泊位服從負(fù)指數(shù)分布，每輛車平均需要15秒。車輛進(jìn)入車道服從泊松分布

27、，平均每小時(shí)3輛。解：對此隊(duì)列分析如下：模型為m/m/1/ / .(1) 先確定參數(shù)值：由題意知，這是單服務(wù)臺模型系統(tǒng)，有=3(輛/小時(shí)) = 60/15=4(輛/小時(shí)) 故服務(wù)強(qiáng)度為=/=3/4=0.75 (2) 計(jì)算穩(wěn)態(tài)概率 p0=1-=1-0.75=0.25; pn=n p0其中，p0是車道空閑的概率，也是車輛不必等待立即就能進(jìn)入車道的概率。而車輛需要等待的概率，也是車道繁忙的概率為p(n0)=1- p0=1-0.25=0.75第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃 計(jì)算系統(tǒng)的主要工作指標(biāo)：此模型的平均有效到達(dá)率，即是到達(dá)率第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃 為使車輛平均逗留時(shí)間不超

28、過半分鐘，車輛經(jīng)過車道的平均時(shí)間應(yīng)減少到多少？由于將=3代入上式解得：5車輛經(jīng)過車道的平均時(shí)間為即車輛經(jīng)過車道的平均時(shí)間至少應(yīng)減少3分。第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃二、系統(tǒng)的容量有限的情況（二、系統(tǒng)的容量有限的情況（m/m/1/n/ ）若系統(tǒng)的最大容量為n ，對于單服務(wù)臺的情形，排隊(duì)等待的顧客最多為n-1 ，在某時(shí)刻一顧客到達(dá)時(shí)，如果系統(tǒng)中已有n個(gè)顧客，那么這個(gè)顧客就被拒絕進(jìn)入系統(tǒng)（如圖9-4）。第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃圖9-4 有容量限制的情形當(dāng)n=1時(shí)，為即時(shí)制的情形；當(dāng)n ，為容量無限制的情形。若只考慮穩(wěn)態(tài)的情形，各狀態(tài)間概率強(qiáng)度的轉(zhuǎn)換關(guān)系如圖9-5。第九章第九章

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

30、e =(1-p0 )第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃根據(jù)（9-25）可以得出以下指標(biāo)：(1)隊(duì)長（期望值）(2)隊(duì)列長（期望值）(3)顧客逗留時(shí)間（期望值） (4)顧客等待時(shí)間（期望值）第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃此模型系統(tǒng)的性能指標(biāo)（當(dāng)1 時(shí)）第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃例9-2 集裝箱堆場的某作業(yè)集裝箱泊位共7個(gè)。當(dāng)7個(gè)處理臺都滿時(shí)，后來到的集裝箱不進(jìn)入該作業(yè)線。集裝箱的平均到達(dá)率為3個(gè)/小時(shí)，處理一個(gè)集裝箱平均需要15分。解：則n=7為系統(tǒng)中最大的顧客數(shù)，=3個(gè)/小時(shí)，=4個(gè)/小時(shí)。(1)由題意知，模型為（m/m/1/n/）先確定參數(shù)：由題意知，服務(wù)強(qiáng)度=/=3

31、/4=0.75(2)求某集裝箱一到達(dá)就能進(jìn)行作業(yè)的概率。這種情形相當(dāng)于作業(yè)線內(nèi)沒有集裝箱，所求概率第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃(3)求作業(yè)線上集裝箱的期望值；需要等待的集裝箱的期望值(4)求有效到達(dá)率e e =(1-p0 )=2.11-(1-0.2778)=2.89(個(gè)小時(shí))(5)求一集裝箱在作業(yè)線內(nèi)逗留的期望時(shí)間；等待時(shí)間(6)在可能到來的集裝箱進(jìn)入其它作業(yè)線的概率(pn7)。這就是求作業(yè)線內(nèi)有7個(gè)集裝箱的概率第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃三、顧客源有限的情形三、顧客源有限的情形(m/m/1/ /m)該模型中，設(shè)顧客總數(shù)為m，當(dāng)顧客需要服務(wù)時(shí)，就進(jìn)入隊(duì)列等待；服務(wù)完畢后，重

32、新回到顧客源。如此循環(huán)往復(fù)。模型符號的第4項(xiàng)為，表示系統(tǒng)的容量沒有限制，但實(shí)際上它決不會(huì)超過m，所以跟寫成(m/m/1/m/m)的意義相同。典型的有限顧客源問題是機(jī)器維修問題。有m臺機(jī)器在運(yùn)轉(zhuǎn)，單位時(shí)間內(nèi)平均出現(xiàn)故障的機(jī)器數(shù)即為顧客平均到達(dá)率，修理工修理一臺設(shè)備的平均時(shí)間即為平均服務(wù)時(shí)間，已修復(fù)的機(jī)器仍可能再出現(xiàn)故障（如圖9-6）。第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃圖9-6有限顧客源問題關(guān)于平均到達(dá)率在無限源的情形是按全體顧客來考慮的；在有限源的情形必須按每個(gè)顧客來考慮。為簡單起見，設(shè)各個(gè)顧客的到達(dá)率都是相同的（的含義是每臺機(jī)器單位運(yùn)轉(zhuǎn)時(shí)間內(nèi)發(fā)生故障的概率或平均次數(shù)），這時(shí)在系統(tǒng)外的顧客平

33、均數(shù)為m-ls，對系統(tǒng)的有效到達(dá)率e應(yīng)為 e=(m-ls)第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃對于此模型的分析依然可以沿用前面的方法。在穩(wěn)態(tài)的情況下，考慮狀態(tài)間的轉(zhuǎn)移率如圖9-7所示。第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃圖9-7狀態(tài)轉(zhuǎn)移根據(jù)圖9-7列出狀態(tài)概率的穩(wěn)態(tài)方程：解此差分方程，用遞推的方法第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃得系統(tǒng)的各項(xiàng)指標(biāo):第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃在機(jī)器故障問題中l(wèi)s就是平均故障臺數(shù)，而(m-ls)表示正常運(yùn)轉(zhuǎn)的平均臺數(shù)。第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃單隊(duì)、并列的多服務(wù)臺（服務(wù)臺數(shù)為c）的情形，討論以下三種情形：(1)標(biāo)準(zhǔn)的m/m/c模型(

34、m/m/c/);(2)系統(tǒng)容量有限制(m/m/c/n/)；(3)有限顧客源(m/m/c/m)。第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃一、標(biāo)準(zhǔn)的一、標(biāo)準(zhǔn)的m/m/c模型模型(m/m/c/) 標(biāo)準(zhǔn)m/m/c模型的各種特征與標(biāo)準(zhǔn)的m/m/1模型的規(guī)定相同。另規(guī)定各服務(wù)臺工作是相互獨(dú)立的（非協(xié)作）且平均服務(wù)率相同1=1=c=。因此整個(gè)服務(wù)機(jī)構(gòu)的平均服務(wù)率c（當(dāng)nc時(shí)）；n（當(dāng)nc時(shí)時(shí)，因?yàn)橹挥衏個(gè)服務(wù)臺，最多有c個(gè)顧客在被服務(wù)，n-c個(gè)顧客在等候，因此系統(tǒng)的服務(wù)率為c，狀態(tài)的轉(zhuǎn)移率應(yīng)為cpn。第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃圖9-8 多服務(wù)臺服務(wù)系統(tǒng)第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃圖9-9

35、多服務(wù)臺服務(wù)系統(tǒng)狀態(tài)轉(zhuǎn)移第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃由圖9-9可得：類似的有pi=1，且1用遞推解差分方程（9-29），求得狀態(tài)概率：系統(tǒng)的運(yùn)行指標(biāo)平均隊(duì)長平均等待時(shí)間和逗留時(shí)間（由little公式求得）第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃例：某售票所有三個(gè)窗口，顧客到達(dá)服從poisson過程，到達(dá) = 0.9 人/分鐘，服務(wù) =0.4人/分鐘。設(shè)顧客到達(dá)后依次排成一隊(duì)向空閑的窗口購票，如圖 a. 圖圖 a 窗口窗口1 1 =0.4 =0.4 窗口窗口2 2 =0.4 =0.4 窗口窗口3 3 =0.4 =0.4 = 0.9 窗口窗口1 1 =0.4 =0.4 窗口窗口2 2 =0

36、.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, = / c =2.25/3 c），與單服務(wù)臺情形類似，顧客的到達(dá)率是按單個(gè)顧客來考慮的，在機(jī)器管理問題中，共有m臺機(jī)器，有c個(gè)修理工人，顧客到達(dá)就是機(jī)器出了故障，而每個(gè)顧客的到達(dá)率 是指每臺機(jī)器單位運(yùn)轉(zhuǎn)時(shí)間出故障的期望次數(shù)。系統(tǒng)中顧客數(shù)n就是出故障臺數(shù)，當(dāng)nc時(shí)，所有的故障機(jī)器都在被修理，有(c-n)個(gè)修理工人在空閑；當(dāng)cnm時(shí)，有(n-c)臺機(jī)器在停機(jī)等待修理，而修理工都在忙碌狀態(tài)。假定這c個(gè)工人修理技術(shù)相同，修理時(shí)間都服從參數(shù)為的負(fù)指

37、數(shù)分布，并假定故障的修復(fù)時(shí)間和正在生產(chǎn)的機(jī)器是否發(fā)生故障是相互獨(dú)立的。第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃其中第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃由于由于p p0 0,p ,pn n計(jì)算公式過于復(fù)雜，有專門的表格可以供查閱。計(jì)算公式過于復(fù)雜，有專門的表格可以供查閱。系統(tǒng)的性能指標(biāo)平均顧客數(shù)（即平均故障臺數(shù)）：有效的到達(dá)率e為每個(gè)顧客的到達(dá)率乘以在系統(tǒng)外（正常運(yùn)轉(zhuǎn)）的機(jī)器的期望數(shù)：e=(m-ls)；在機(jī)器故障問題中，即單位時(shí)間m臺機(jī)器平均出現(xiàn)故障的次數(shù)。第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃本節(jié)討論服務(wù)時(shí)間是任意分布的情形，當(dāng)然，對任何情形都有下面的關(guān)系：e系統(tǒng)中顧客數(shù)=e隊(duì)列中顧客數(shù)+e服

38、務(wù)機(jī)構(gòu)中顧客數(shù)e在系統(tǒng)中逗留時(shí)間=e排隊(duì)等待時(shí)間+e服務(wù)時(shí)間其中，e.表示求期望值，用符號表示：ls=lq+lsews=wq+et第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃一、一般分布模型一、一般分布模型(m/g/1/)該模型的基本條件：(1) 輸入過程顧客源是無限的，到達(dá)過程服從參數(shù)為的泊松過程； (2)排隊(duì)規(guī)則單隊(duì)，隊(duì)長無限制，先到先服務(wù)； (3)服務(wù)機(jī)構(gòu)單服務(wù)臺，g表示服務(wù)時(shí)間t的分布為任意的概率分布，但已知e(t)和方差var(t)。此模型被稱為單服務(wù)臺泊松到達(dá)、任意服務(wù)時(shí)間的排隊(duì)模型。第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃在穩(wěn)態(tài)情況下，當(dāng)=e(t)1時(shí)，可以證明: 此公式又稱p-k（po

39、llaczek-khint chine）公式。只要知道、e(t)、var(t)，無論服務(wù)時(shí)間t服從什么分布，均可用p-k公式求出平均隊(duì)長ls。其它的運(yùn)行指標(biāo)：第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃二、定長分布模型二、定長分布模型(m/d/1/)服務(wù)時(shí)間為確定的常數(shù)，如在一條裝配線上完成一件工作的時(shí)間一般都是常數(shù)。自動(dòng)汽車沖洗臺，沖洗一輛汽車的時(shí)間就是常數(shù)，可得：第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃三、愛爾朗服務(wù)時(shí)間三、愛爾朗服務(wù)時(shí)間(m/ek/1/)此模型中每一個(gè)顧客必須一次經(jīng)過k個(gè)服務(wù)臺，接受k次服務(wù)后才構(gòu)成一個(gè)完整服務(wù)過程。在每個(gè)服務(wù)臺的服務(wù)時(shí)間ti相互獨(dú)立，并服從相同的負(fù)指數(shù)分布（參數(shù)

40、為k），那么 服從k階愛爾朗分布。第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃對于(m/ek/1/)模型（除服務(wù)時(shí)間外，其它條件與標(biāo)準(zhǔn)的m/m/1/型相同）第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃一、排隊(duì)系統(tǒng)經(jīng)濟(jì)分析一、排隊(duì)系統(tǒng)經(jīng)濟(jì)分析試圖完全消除排隊(duì)現(xiàn)象是不現(xiàn)實(shí)的，那樣顯然會(huì)造成服務(wù)人員和設(shè)施的嚴(yán)重浪費(fèi)。另一方面，如果設(shè)施不足或服務(wù)低水平，將導(dǎo)致過多的等待，因而產(chǎn)生生產(chǎn)和社會(huì)損失。從經(jīng)濟(jì)角度考慮，一般排隊(duì)系統(tǒng)的費(fèi)用應(yīng)該包含于以下兩個(gè)方面： 服務(wù)費(fèi)用。它隨著服務(wù)水平（反映在服務(wù)能力和服務(wù)臺數(shù)量方面）的提高而增加，是服務(wù)水平的遞增函數(shù)。 顧客等待的機(jī)會(huì)損失（費(fèi)用）。顧客由于等待，產(chǎn)生一系列的損失（時(shí)間上

41、、心理上、社會(huì)上等）用經(jīng)濟(jì)費(fèi)用進(jìn)行的估算，稱為顧客等待的機(jī)會(huì)損失。它隨服務(wù)水平的提高而下降，是服務(wù)水平的遞減函數(shù)。 第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃這兩方面構(gòu)成的函數(shù)呈現(xiàn)為一條如圖所示的u型曲線。第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃圖圖9-10 費(fèi)用與服務(wù)水平之間的關(guān)系費(fèi)用與服務(wù)水平之間的關(guān)系f1、f2、y分別是服務(wù)費(fèi)用函數(shù)、等待費(fèi)用函數(shù)、合成費(fèi)用函數(shù)。分別是服務(wù)費(fèi)用函數(shù)、等待費(fèi)用函數(shù)、合成費(fèi)用函數(shù)。系統(tǒng)的最優(yōu)化的目標(biāo)就是尋求這個(gè)合成費(fèi)用曲線的最小點(diǎn)。在這種意義下，排隊(duì)系統(tǒng)的最優(yōu)化問題通常分為兩類：一類稱之系統(tǒng)的靜態(tài)最優(yōu)設(shè)計(jì)，目的在于使設(shè)備到達(dá)最大效益，或者說，在保證一定服務(wù)質(zhì)量指標(biāo)的

42、前提下，要求機(jī)構(gòu)最為經(jīng)濟(jì)；另一類叫做系統(tǒng)動(dòng)態(tài)最優(yōu)運(yùn)營，是指一個(gè)給定排隊(duì)系統(tǒng)，如何運(yùn)營可使某個(gè)目標(biāo)函數(shù)得到最優(yōu)。本節(jié)只討論系統(tǒng)靜態(tài)的最優(yōu)設(shè)計(jì)問題。第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃歸納起來，排隊(duì)系統(tǒng)常見的優(yōu)化問題在于：確定服務(wù)臺的最優(yōu)平均服務(wù)率*；確定最佳服務(wù)臺數(shù)量s*；選擇最為合適的服務(wù)規(guī)則；確定上述幾個(gè)量得最優(yōu)組合。研究排隊(duì)系統(tǒng)的根本目的在于以最少的設(shè)備得到最大的效益，或者說，在一定的服務(wù)質(zhì)量的指標(biāo)下要求機(jī)構(gòu)最為經(jīng)濟(jì)。第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃二、二、m/m/1系統(tǒng)的最優(yōu)平均服務(wù)率系統(tǒng)的最優(yōu)平均服務(wù)率1標(biāo)準(zhǔn)的m/m/1模型設(shè)c1為當(dāng)=1時(shí)服務(wù)系統(tǒng)單位時(shí)間的平均費(fèi)用，并且這個(gè)平

43、均費(fèi)用與評級均服務(wù)率成正比例；cw為平均每個(gè)顧客在逗留單位時(shí)間的損失；y為整個(gè)系統(tǒng)單位時(shí)間的平均總費(fèi)用。其中c1、cw均為已知（以下情形相同）。目標(biāo)函數(shù)：將m/m/1模型的平均隊(duì)長公式l=/(-)代入(9-41)式，得：第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃顯然，y是關(guān)于決策變量的一元非線性函數(shù)。由一階最優(yōu)性必要條件（駐點(diǎn)條件）解得駐點(diǎn)取算術(shù)平方根是為了保證，這樣，系統(tǒng)才能達(dá)到穩(wěn)態(tài)。又知二階充分條件成立：于是，式(9-43)給出的*為(,)上的全局唯一最小點(diǎn)。將*帶入(9-42)中，可得最小的總平均費(fèi)用第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃若設(shè)cw為平均每個(gè)顧客在隊(duì)列中等待單位時(shí)間的損失，則需

44、要m/m/1模型的平均隊(duì)列長公式 代入式(9-41)中的l，類似可得一階最優(yōu)性必要條件：這是一個(gè)關(guān)于的4次方程，實(shí)際中一般采用數(shù)值法（如牛頓法）來確定其根（最優(yōu)服務(wù)率）*。第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃2. 系統(tǒng)中顧客最大限制為系統(tǒng)中顧客最大限制為n的情形的情形在這情形下，系統(tǒng)中如已有n個(gè)顧客，則后來的顧客即被拒絕，可知：pn 被拒絕的概率；1- pn 能被接受的概率；(1- pn)單位時(shí)間實(shí)際進(jìn)入服務(wù)機(jī)構(gòu)顧客的平均數(shù)。在穩(wěn)定狀態(tài)下，它也等于單位時(shí)間內(nèi)實(shí)際服務(wù)完成的平均顧客數(shù)。第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃設(shè)每服務(wù)1人能收入g元，于是單位時(shí)間收入的期望值是(1- pn)g元。純

45、利潤：最優(yōu)的解*應(yīng)該符合上式(9-45)。上式中c1、g、n都是給定的，但要由上式中解出*是很復(fù)雜的。通常是通過數(shù)值計(jì)算來求*的，或?qū)⑸鲜阶蠓剑▽σ欢ǖ膎）作為的函數(shù)作出圖形進(jìn)行求解。第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃3. 顧客源為有限的情形顧客源為有限的情形按機(jī)械故障問題來考慮。設(shè)共有機(jī)器m臺，各臺連續(xù)運(yùn)轉(zhuǎn)時(shí)間服從負(fù)指數(shù)分布。有1個(gè)修理工人，修理時(shí)間服從負(fù)指數(shù)分布。當(dāng)服務(wù)率=1時(shí)的修理費(fèi)用c1，單位時(shí)間每臺機(jī)器運(yùn)轉(zhuǎn)可得收入g元。平均運(yùn)轉(zhuǎn)臺數(shù)為m-ls，所以單位時(shí)間純利潤：第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃當(dāng)給定m、g、c1、，要由上式中解出*是很困難的，通常是利用泊松分布表通過數(shù)值計(jì)

46、算來求得，或?qū)⑸鲜阶蠓剑▽σ欢ǖ膍）作為的函數(shù)作出圖形進(jìn)行求解。第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃三、三、m/m/c系統(tǒng)的最優(yōu)服務(wù)臺數(shù)系統(tǒng)的最優(yōu)服務(wù)臺數(shù)c設(shè)排隊(duì)系統(tǒng)m/m/c，確定最佳服務(wù)臺數(shù)c的目標(biāo)函數(shù)為：其中：c為待定的共享并聯(lián)服務(wù)臺的個(gè)數(shù)；y(c)為整個(gè)系統(tǒng)單位時(shí)間的平均費(fèi)用，它是關(guān)于服務(wù)臺數(shù)c的函數(shù)；c2為每個(gè)服務(wù)臺單位時(shí)間內(nèi)的平均費(fèi)用（各服務(wù)臺相同）；cw為平均每個(gè)顧客在系統(tǒng)中逗留單位時(shí)間的損失；l(c)為平均隊(duì)長，它是關(guān)于服務(wù)臺數(shù)c的函數(shù)。第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃要確定最優(yōu)服務(wù)臺數(shù)c1,2,，使由于c取值離散，不能采用微分方法或非線性規(guī)劃的方法，因此，只需要同時(shí)滿

47、足下式即可：采用差分法，可導(dǎo)出另一關(guān)系式。把式(9-50)代入式(9-51)中，得第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃令依次計(jì)算時(shí)的值，根據(jù)落在哪兩個(gè)差值之間就可確定c*。另外，若設(shè)cw為平均每個(gè)顧客在隊(duì)列中等待單位時(shí)間的損失，則需要m/m/c模型的平均隊(duì)列長公式lq(c)取代式(9-50)中的l(c)，由于在此情況下不需求導(dǎo)數(shù)，所以只要把相應(yīng)公式中的l(c)用lq(c)取代即可。第九章第九章 服務(wù)系統(tǒng)規(guī)劃服務(wù)系統(tǒng)規(guī)劃第第11章章 排排 隊(duì)隊(duì) 論論113 例例7 某儲(chǔ)蓄所有一個(gè)服務(wù)窗口，顧客按泊松分布平均每小時(shí)某儲(chǔ)蓄所有一個(gè)服務(wù)窗口，顧客按泊松分布平均每小時(shí) 到達(dá)到達(dá)10人。為任一顧客辦理存

48、款、取款等業(yè)務(wù)的時(shí)間人。為任一顧客辦理存款、取款等業(yè)務(wù)的時(shí)間 v(小時(shí)小時(shí))n(0.05, ,0.012). 試求該儲(chǔ)蓄所空閑的概率及其主要工作指標(biāo)。試求該儲(chǔ)蓄所空閑的概率及其主要工作指標(biāo)。 解解從而根據(jù)從而根據(jù)波拉切克波拉切克欣欽欣欽公式，可以導(dǎo)出：公式，可以導(dǎo)出：l q= + 2 2( 1 - -)22(11-53)進(jìn)而按進(jìn)而按(11-1)式可算出式可算出l, , w, , wq; ; 其中其中 = 。 2 = 0.012 (小時(shí)小時(shí)/人人)2= 10 (人人/小時(shí)小時(shí))1= 0.05 (小時(shí)小時(shí)/人人)第第11章章 排排 隊(duì)隊(duì) 論論114= 該儲(chǔ)蓄所空閑的概率：該儲(chǔ)蓄所空閑的概率： =

49、1 - - = = 10() = = = 1 - -l = lq +l q = 0.52+102(0.01)22(1- -0.5)w = lwq =lq則則主要指標(biāo)主要指標(biāo)= 0.26 + 0.5= =10= (小時(shí)小時(shí)) (分鐘分鐘)= (小時(shí)小時(shí)) (分鐘分鐘)第第11章章 排排 隊(duì)隊(duì) 論論115 二、二、 m/ /d/ /1系統(tǒng)系統(tǒng) 該系統(tǒng)對各顧客服務(wù)時(shí)間相互獨(dú)立且為同一個(gè)常數(shù)該系統(tǒng)對各顧客服務(wù)時(shí)間相互獨(dú)立且為同一個(gè)常數(shù) ，故有故有 e( ) = =1 例例8 某檢測站有一臺自動(dòng)檢測機(jī)器性能的儀器，檢測每臺某檢測站有一臺自動(dòng)檢測機(jī)器性能的儀器，檢測每臺機(jī)器都需機(jī)器都需6分鐘。送檢機(jī)器按泊

50、松分布到達(dá)，平均每小時(shí)分鐘。送檢機(jī)器按泊松分布到達(dá)，平均每小時(shí)4臺。臺。試求該系統(tǒng)的主要工作指標(biāo)。試求該系統(tǒng)的主要工作指標(biāo)。d( ) = 0 (=2)(11-54)lq= 2(1 - -)2第第11章章 排排 隊(duì)隊(duì) 論論116 = 4臺臺/小時(shí)小時(shí) = 6分鐘分鐘/臺臺 = 0.1小時(shí)小時(shí)/ /臺臺 2 = 0，l = lq+= 2/15 + 0.4 = 8/15( (臺臺) ) wq = lq/ = 2/4(15) = 1/30( (小時(shí)小時(shí)) ) = 2( (分鐘分鐘) )w = wq+ 1/= 2 + 6 = 8( (分鐘分鐘) )0.422(1- - 0.4)lq = = 2/15(

51、(臺臺) )= = 4(0.1) = 0.4解解第第11章章 排排 隊(duì)隊(duì) 論論117 該系統(tǒng)對任一顧客的服務(wù)時(shí)間該系統(tǒng)對任一顧客的服務(wù)時(shí)間 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第第11章章 排排 隊(duì)隊(duì) 論論118 例例9 一個(gè)質(zhì)量檢查員平均每小時(shí)收到一個(gè)質(zhì)量檢查員平均每小時(shí)收到兩件兩件送來檢查的送來檢查的樣品，每件樣品要一次完成樣品，每件樣品要一次完成 項(xiàng)檢驗(yàn)才能判斷是否合格。據(jù)項(xiàng)檢驗(yàn)才能判斷是否合格。據(jù)統(tǒng)計(jì)，每項(xiàng)檢驗(yàn)

52、所需時(shí)間的期望值都是統(tǒng)計(jì)，每項(xiàng)檢驗(yàn)所需時(shí)間的期望值都是 分鐘，每項(xiàng)檢驗(yàn)的分鐘，每項(xiàng)檢驗(yàn)的時(shí)間和送檢產(chǎn)品到到達(dá)間隔都為指數(shù)分布。問一件樣品從時(shí)間和送檢產(chǎn)品到到達(dá)間隔都為指數(shù)分布。問一件樣品從送到至檢查完畢預(yù)期要多少時(shí)間？送到至檢查完畢預(yù)期要多少時(shí)間？ 解解 = 2 件件/ /小時(shí)小時(shí) k k = 1/(5 ) = 4 (分鐘分鐘/ /件件) e(vi i) = 1/ /(k k )，i = 1，2，3，4，51/= 20 (分鐘分鐘/件件) = (小時(shí)小時(shí)/件件)由由有有則則第第11章章 排排 隊(duì)隊(duì) 論論119 = /= 2() = lq = wq = lq/ = / = (小時(shí)小時(shí)) w =

53、wq + 1/= + = 11/15 (小時(shí)小時(shí)) = (5+1 )()225(1 - - )=第第11章章 排排 隊(duì)隊(duì) 論論120 c1 當(dāng)當(dāng)= 1時(shí)時(shí) 服務(wù)系統(tǒng)單位時(shí)間的平均費(fèi)用服務(wù)系統(tǒng)單位時(shí)間的平均費(fèi)用 cw 平均每個(gè)顧客在系統(tǒng)逗留單位時(shí)間的損失平均每個(gè)顧客在系統(tǒng)逗留單位時(shí)間的損失 整個(gè)系統(tǒng)單位時(shí)間的平均總費(fèi)用整個(gè)系統(tǒng)單位時(shí)間的平均總費(fèi)用 其中其中c1 ，cw可知，目標(biāo)函數(shù)為可知，目標(biāo)函數(shù)為 = c1 + cwl一、一、m/m/1/ 系統(tǒng)的最優(yōu)平均服務(wù)率系統(tǒng)的最優(yōu)平均服務(wù)率設(shè)設(shè)(11-56)將將 l =/（ （） ）代入上式，得代入上式，得 = c1 + cw/（ （） ）求導(dǎo)求導(dǎo), ,得得dd= c1 - -cw1（ （） ）2第第11章章 排排 隊(duì)隊(duì) 論論121解得駐點(diǎn)解得駐點(diǎn)(11-57)又由又由dyd=2cw（ （） ）3 0（ （因因） ）知：知：為為（ （ ， ， ） ）上的全局唯一極小點(diǎn)；代入上的全局唯一極小點(diǎn)；代入(11-56)得得(11-58)+ cw/c1yc1+ 2c1cw 另若