數(shù)學(xué)建模之排隊(duì)論.ppt

《數(shù)學(xué)建模之排隊(duì)論.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、排隊(duì)論1第8章排隊(duì)論(QueuingTheory)排隊(duì)論（queuing),也稱(chēng)隨機(jī)服務(wù)系統(tǒng)理論，是運(yùn)籌學(xué)的一個(gè)主要分支。1909年，丹麥哥本哈根電子公司電話工程師A.K.Erlang的開(kāi)創(chuàng)性論文“概率論和電話通訊理論”標(biāo)志此理論的誕生。排隊(duì)論的發(fā)展最早是與電話，通信中的問(wèn)題相聯(lián)系的，并到現(xiàn)在是排隊(duì)論的傳統(tǒng)的應(yīng)用領(lǐng)域。近年來(lái)在計(jì)算機(jī)通訊網(wǎng)絡(luò)系統(tǒng)、交通運(yùn)輸、醫(yī)療衛(wèi)生系統(tǒng)、庫(kù)存管理、作戰(zhàn)指揮等各領(lǐng)域中均得到應(yīng)用。28排隊(duì)論8-1前言8-2基本概念8-3輸入過(guò)程和服務(wù)時(shí)間分布8-4泊松輸入—指數(shù)服務(wù)排隊(duì)模型8-5M/M/1無(wú)限源系統(tǒng)8-6系統(tǒng)容量有限的排隊(duì)

2、系統(tǒng)8-7顧客源有限的排隊(duì)系統(tǒng)3排隊(duì)是我們?cè)谌粘Ｉ詈蜕a(chǎn)中經(jīng)常遇到的現(xiàn)象。例如，上、下班搭乘公共汽車(chē)；顧客到商店購(gòu)買(mǎi)物品；病員到醫(yī)院看?。宦每偷绞燮碧庂?gòu)買(mǎi)車(chē)票；學(xué)生去食堂就餐等就常常出現(xiàn)排隊(duì)和等待現(xiàn)象。前言4除了上述有形的排隊(duì)之外，還有大量的所謂“無(wú)形”排隊(duì)現(xiàn)象。如幾個(gè)顧客打電話到出租汽車(chē)站要求派車(chē)，如果出租汽車(chē)站無(wú)足夠車(chē)輛、則部分顧客只得在各自的要車(chē)處等待，他們分散在不同地方，卻形成了一個(gè)無(wú)形隊(duì)列在等待派車(chē)。前言5排隊(duì)的不一定是人，也可以是物：例如，通訊衛(wèi)星與地面若干待傳遞的信息；生產(chǎn)線上原料、半成品等待加工；因故障停止運(yùn)轉(zhuǎn)的機(jī)器等待修理；碼頭的

3、船只等待裝卸貨物；要降落的飛機(jī)因跑道不空而在空中盤(pán)旋等等。前言6上述各種問(wèn)題雖互不相同，但卻都有要求得到某種服務(wù)的人或物和提供服務(wù)的人或機(jī)構(gòu)。排隊(duì)論里把要求服務(wù)的對(duì)象統(tǒng)稱(chēng)為“顧客”,提供服務(wù)的人或機(jī)構(gòu)稱(chēng)為“服務(wù)臺(tái)”或“服務(wù)員”。前言7不同的顧客與服務(wù)組成了各式各樣的服務(wù)系統(tǒng)。顧客為了得到某種服務(wù)而到達(dá)系統(tǒng)、若不能立即獲得服務(wù)而又允許排隊(duì)等待，則加入等待隊(duì)伍，待獲得服務(wù)后離開(kāi)系統(tǒng)，見(jiàn)圖8-1至圖8-5。圖8-1單服務(wù)臺(tái)排隊(duì)系統(tǒng)前言8圖8-2單隊(duì)列——S個(gè)服務(wù)臺(tái)并聯(lián)的排隊(duì)系統(tǒng)圖8-3S個(gè)隊(duì)列——S個(gè)服務(wù)臺(tái)的并聯(lián)排隊(duì)系統(tǒng)前言9圖8-4單隊(duì)——多個(gè)服務(wù)臺(tái)的串

4、聯(lián)排隊(duì)系統(tǒng)圖8-5多隊(duì)——多服務(wù)臺(tái)混聯(lián)網(wǎng)絡(luò)系統(tǒng)前言10圖8-6隨機(jī)服務(wù)系統(tǒng)前言一般的排隊(duì)系統(tǒng)，都可由下面圖加以描述。通常稱(chēng)由圖8-6表示的系統(tǒng)為一隨機(jī)聚散服務(wù)系統(tǒng)。任一排隊(duì)系統(tǒng)都是一個(gè)隨機(jī)聚散服務(wù)系統(tǒng)?！熬邸北硎绢櫩偷牡竭_(dá)，“散”表示顧客的離去。11面對(duì)擁擠現(xiàn)象，人們總是希望盡量設(shè)法減少排隊(duì)，通常的做法是增加服務(wù)設(shè)施。但是增加的數(shù)量越多，人力、物力的支出就越大，甚至?xí)霈F(xiàn)空閑浪費(fèi)。如果服務(wù)設(shè)施太少，顧客排隊(duì)等待的時(shí)間就會(huì)很長(zhǎng)，這樣對(duì)顧客會(huì)帶來(lái)不良影響。前言12顧客排隊(duì)時(shí)間的長(zhǎng)短與服務(wù)設(shè)施規(guī)模的大小，就構(gòu)成了設(shè)計(jì)隨機(jī)服務(wù)系統(tǒng)中的一對(duì)矛盾。如何做到既保證

5、一定的服務(wù)質(zhì)量指標(biāo)，又使服務(wù)設(shè)施費(fèi)用經(jīng)濟(jì)合理，恰當(dāng)?shù)亟鉀Q顧客排隊(duì)時(shí)間與服務(wù)設(shè)施費(fèi)用大小這對(duì)矛盾。這就是隨機(jī)服務(wù)系統(tǒng)理論——排隊(duì)論所要研究解決的問(wèn)題。前言13一、排隊(duì)系統(tǒng)的組成與特征排隊(duì)系統(tǒng)一般有三個(gè)基本組成部分：1.輸入過(guò)程；2.排隊(duì)規(guī)則；3.服務(wù)機(jī)構(gòu)。§8-2排隊(duì)系統(tǒng)的基本概念14輸入即為顧客的到達(dá)，可有下列情況：1）顧客源可能是有限的，也可能是無(wú)限的。2）顧客是成批到達(dá)或是單個(gè)到達(dá)。3）顧客到達(dá)間隔時(shí)間可能是隨機(jī)的或確定的。4）顧客到達(dá)可能是相互獨(dú)立或關(guān)聯(lián)的。所謂獨(dú)立就是以前顧客的到達(dá)對(duì)以后顧客的到達(dá)無(wú)影響。5）輸入過(guò)程可以是平穩(wěn)的（statio

6、nary）或說(shuō)是對(duì)時(shí)間齊次的（Homogeneousintime），也可以是非平穩(wěn)的。輸入過(guò)程平穩(wěn)的指顧客相繼到達(dá)的間隔時(shí)間分布和參數(shù)（均值、方差）與時(shí)間無(wú)關(guān)；非平穩(wěn)的則是與時(shí)間相關(guān)，非平穩(wěn)的處理比較困難。1.輸入過(guò)程15這是指服務(wù)臺(tái)從隊(duì)列中選取顧客進(jìn)行服務(wù)的順序?？梢苑譃閾p失制、等待制、混合制3大類(lèi)。(1)損失制。這是指如果顧客到達(dá)排隊(duì)系統(tǒng)時(shí)，所有服務(wù)臺(tái)都已被先來(lái)的顧客占用，那么他們就自動(dòng)離開(kāi)系統(tǒng)永不再來(lái)。典型例子是，如電話拔號(hào)后出現(xiàn)忙音，顧客不愿等待而自動(dòng)掛斷電話，如要再打，就需重新拔號(hào)，這種服務(wù)規(guī)則即為損失制。2.排隊(duì)規(guī)則16(2)等待制。指當(dāng)

7、顧客來(lái)到系統(tǒng)時(shí)，所有服務(wù)臺(tái)都不空，顧客加入排隊(duì)行列等待服務(wù)。例如，排隊(duì)等待售票，故障設(shè)備等待維修等。等待制中，服務(wù)臺(tái)在選擇顧客進(jìn)行服務(wù)時(shí)，常有如下四種規(guī)則：①先到先服務(wù)（FCFS）。按顧客到達(dá)的先后順序?qū)︻櫩瓦M(jìn)行服務(wù)，這是最普遍的情形。②后到先服務(wù)（LCFS）。倉(cāng)庫(kù)中迭放的鋼材，后迭放上去的都先被領(lǐng)走，就屬于這種情況。2.排隊(duì)規(guī)則17③隨機(jī)服務(wù)（RAND）。即當(dāng)服務(wù)臺(tái)空閑時(shí)，不按照排隊(duì)序列而隨意指定某個(gè)顧客去接受服務(wù)，如電話交換臺(tái)接通呼叫電話就是一例。④優(yōu)先權(quán)服務(wù)（PR）。如老人、兒童先進(jìn)車(chē)站；危重病員先就診；遇到重要數(shù)據(jù)需要處理計(jì)算機(jī)立即中斷其他數(shù)

8、據(jù)的處理等，均屬于此種服務(wù)規(guī)則。2.排隊(duì)規(guī)則18(3)混合制．這是等待制與損失制相結(jié)合的一種服務(wù)規(guī)則，一般是