吉林大學(xué)遠(yuǎn)程教育 運(yùn)籌學(xué)課件8.1

1、運(yùn) 籌 學(xué) 第八章 排隊(duì)論 1 排隊(duì)服務(wù)系統(tǒng)的基本概念排隊(duì)服務(wù)系統(tǒng)的基本概念n 在生產(chǎn)和日常生活中，經(jīng)常可以碰到各種各樣的服務(wù)系統(tǒng)。如上下班乘公共汽車，公共汽車與乘客構(gòu)成一個(gè)服務(wù)系統(tǒng)；到商店買東西，售貨員與顧客也構(gòu)成一個(gè)服務(wù)系統(tǒng)，都有等候服務(wù)的問(wèn)題。n 有些場(chǎng)合下，服務(wù)系統(tǒng)的構(gòu)成沒(méi)有那么明顯。如從長(zhǎng)春往北京打電話，由于長(zhǎng)春、北京之間同一時(shí)間內(nèi)允許通話對(duì)數(shù)是有限的，因此，要求通話的人數(shù)超過(guò)這個(gè)限度時(shí)，就要排隊(duì)等候。雖然打電話的人分散在全市各處，彼此互不見(jiàn)面，但他們與長(zhǎng)話臺(tái)一起構(gòu)成一個(gè)服務(wù)系統(tǒng)。他們?cè)陂L(zhǎng)話臺(tái)前排成一個(gè)無(wú)形的隊(duì)伍，就如同排隊(duì)等候公共汽車的乘客隊(duì)伍一樣。n 一般在一個(gè)排隊(duì)服務(wù)系統(tǒng)中總是

2、包含一個(gè)或若干個(gè) “服務(wù)設(shè)施” ，有許多“顧客”進(jìn)入該系統(tǒng)要求得到服務(wù)，服務(wù)完畢后即自行離去。倘若顧客到達(dá)時(shí)，服務(wù)系統(tǒng)空閑著，則到達(dá)的顧客立即得到服務(wù)，否則顧客將排隊(duì)等待服務(wù)或離去。 上面說(shuō)的“顧客”是對(duì)要求得到服務(wù)的對(duì)象的代稱，可以是人，也可以是物； “服務(wù)設(shè)施” 也可以各種各樣。如在用自動(dòng)機(jī)床進(jìn)行生產(chǎn)的車間，一個(gè)工人往往要看若干臺(tái)機(jī)床，當(dāng)機(jī)床發(fā)生故障或要求加料、更換刀具時(shí)，要求工人進(jìn)行修理或照管。在同一時(shí)間內(nèi)，一個(gè)工人只能在一臺(tái)機(jī)床上修理或照管，如這時(shí)又有別的機(jī)床需要該工人修理或照管，就必須等待。這樣，工人與需要修理或照管的機(jī)床之間就構(gòu)成了一個(gè)服務(wù)系統(tǒng)，這里工人是“服務(wù)設(shè)施” ，“顧客”是

3、要求修理或照管的機(jī)床。又如，一座水庫(kù)，上游的水滾滾而來(lái)，如果調(diào)節(jié)得好，水庫(kù)水位保持在安全理想水平，既起到防洪作用，又保證正常發(fā)電、航運(yùn)和灌溉。如調(diào)節(jié)不好，水庫(kù)水位過(guò)高或過(guò)低，就影響水庫(kù)綜合效能的發(fā)揮。這里，水庫(kù)與水構(gòu)成一個(gè)服務(wù)系統(tǒng)，水庫(kù)是“服務(wù)設(shè)施” ，水就是要求得到服務(wù)的“顧客”。 類似例子還可以舉出很多，如醫(yī)院和等待診治的病人；機(jī)場(chǎng)跑道同要求起飛降落的飛機(jī)；港口泊位與進(jìn)港待泊的船只；車站售票口與排隊(duì)買票的旅客之間都構(gòu)成了一個(gè)個(gè)排隊(duì)服務(wù)系統(tǒng)。 如果到達(dá)服務(wù)系統(tǒng)的顧客完全按固定的間隔時(shí)間到達(dá)，又服務(wù)設(shè)施用在每個(gè)顧客身上的服務(wù)時(shí)間也是固定的，就象工廠流水生產(chǎn)線的生產(chǎn)那樣有固定的節(jié)拍，那么這類服務(wù)

4、系統(tǒng)的設(shè)計(jì)計(jì)算是比較方便的。但在大多數(shù)的服務(wù)系統(tǒng)中，情況不是這樣，顧客的到達(dá)經(jīng)常是隨機(jī)的，并且服務(wù)設(shè)施用于每個(gè)顧客身上的服務(wù)時(shí)間往往也是隨機(jī)的，對(duì)于這樣一類隨機(jī)服務(wù)系統(tǒng)的設(shè)計(jì)計(jì)算就要困難得多。 車站的售票口應(yīng)開(kāi)設(shè)多少個(gè)比較合適呢？開(kāi)設(shè)越多，方便旅客，減少排隊(duì)時(shí)間，但售票口增多了，就要增加服務(wù)人員及相應(yīng)的設(shè)施，增加服務(wù)費(fèi)用。這樣，顧客排隊(duì)時(shí)間的長(zhǎng)短與服務(wù)設(shè)施規(guī)模的大小就構(gòu)成設(shè)計(jì)隨機(jī)服務(wù)系統(tǒng)的一對(duì)矛盾。有些場(chǎng)合下，如公共汽車的班次可以隨季節(jié)及顧客到達(dá)規(guī)律的變化進(jìn)行調(diào)整，但另一些場(chǎng)合，服務(wù)設(shè)施的規(guī)模，如機(jī)場(chǎng)跑道、港口泊位、電話線路等一旦建成則變動(dòng)不易，因此需要有一個(gè)進(jìn)行設(shè)計(jì)計(jì)算遵循的理論依據(jù)。到底怎

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)題。 排隊(duì)論的理論起源于對(duì)電話服務(wù)系統(tǒng)的研究。從1909年開(kāi)始，丹麥的電話工程師愛(ài)爾朗（A.K.Eelang）等人在這方面進(jìn)行了長(zhǎng)期的工作，取得了最早的成果。以后排隊(duì)論陸續(xù)應(yīng)用于陸空交通、機(jī)器管理、水庫(kù)設(shè)計(jì)和可靠性理論等方面。六十年代，隨著電子計(jì)算機(jī)蓬勃發(fā)展的需要，又應(yīng)用于計(jì)算機(jī)網(wǎng)絡(luò)的最優(yōu)設(shè)計(jì)。在接近九十年的歷史中，排隊(duì)論無(wú)論在理論或應(yīng)用上都有了飛速進(jìn)展。由于在電子計(jì)算機(jī)上進(jìn)行數(shù)字模擬技術(shù)的發(fā)展，排隊(duì)論已成為解決工程設(shè)計(jì)和管理問(wèn)題的有力

6、工具。 1.1 排隊(duì)系統(tǒng)排隊(duì)系統(tǒng)n 現(xiàn)實(shí)中的排隊(duì)現(xiàn)象是多種多樣的，一般排隊(duì)系統(tǒng)都有下述三個(gè)基本組成部分（圖10-1）。顧客源顧客到來(lái)排隊(duì)規(guī)則排隊(duì)結(jié)構(gòu)服務(wù)規(guī)則服務(wù)機(jī)構(gòu)離去排隊(duì)系統(tǒng)圖10-1 1.輸入過(guò)程輸入過(guò)程指顧客到達(dá)服務(wù)系統(tǒng)情況。 顧客總體（顧客源）的組成可能是有限的，也可能是無(wú)限的。上游河水流入水庫(kù)可以認(rèn)為總體是無(wú)限的；工廠內(nèi)停機(jī)待修的機(jī)器，顯然是有限的總體。 顧客相繼到達(dá)的時(shí)間間隔可以是確定的，也可以是隨機(jī)的。如自動(dòng)裝配線上裝配的各部件一般按確定的時(shí)間間隔到達(dá)裝配點(diǎn)；但到醫(yī)院就診的病人，到餐廳就餐的顧客等，他們的到達(dá)都是隨機(jī)的。 顧客的到達(dá)方式可能是一個(gè)一個(gè)的，也可能是成批的。我們將只研

7、究單個(gè)到達(dá)的情形。 2.排隊(duì)規(guī)則排隊(duì)規(guī)則 顧客到達(dá)時(shí)，如果所有服務(wù)臺(tái)都被占用，則顧客離開(kāi)服務(wù)系統(tǒng)，這種方式稱為即時(shí)制即時(shí)制或損失制損失制。例如旅客到旅店住宿就屬于這種方式。另外一種情形，當(dāng)服務(wù)臺(tái)被占用時(shí)，后來(lái)的顧客就排隊(duì)等待服務(wù)，稱為等待制等待制。 有的服務(wù)系統(tǒng)對(duì)進(jìn)入排隊(duì)系統(tǒng)的顧客數(shù)有一定限制，象理發(fā)店供等待服務(wù)的顧客坐的椅子的座位數(shù)是有限的。大多數(shù)服務(wù)系統(tǒng)可以認(rèn)為系統(tǒng)對(duì)顧客是沒(méi)有限制的。 在多服務(wù)臺(tái)情況下，隊(duì)列的數(shù)目可以是單列，也可以是多列。 等待服務(wù)的次序，最常見(jiàn)的是先到先服務(wù)先到先服務(wù)；還有帶優(yōu)先權(quán)的服務(wù)帶優(yōu)先權(quán)的服務(wù)，如加急電報(bào)、醫(yī)院的急診等；隨機(jī)服隨機(jī)服務(wù)務(wù)，指服務(wù)臺(tái)隨機(jī)對(duì)等待的顧客

8、進(jìn)行服務(wù)；后到先服務(wù)后到先服務(wù)，如乘坐電梯的顧客先入后出，后入先出。 3.服務(wù)機(jī)構(gòu)服務(wù)機(jī)構(gòu)n 從服務(wù)設(shè)施的數(shù)量上可分為單服務(wù)臺(tái)與多服務(wù)臺(tái)。n 在多服務(wù)臺(tái)情形，服務(wù)臺(tái)可能是并列的，也可能是串列的。并列服務(wù)系統(tǒng)可以同時(shí)對(duì)多個(gè)顧客進(jìn)行服務(wù)，而串列情況下，每個(gè)顧客要依次經(jīng)過(guò)各個(gè)服務(wù)臺(tái)的服務(wù)才能離開(kāi)系統(tǒng)。圖10-2中（a）是多隊(duì)多臺(tái)并列情形；（b）是單隊(duì)多臺(tái)并列情形；（c）是單隊(duì)多臺(tái)串列情形。n 服務(wù)時(shí)間可以分成確定型和隨機(jī)型兩種情形。自動(dòng)機(jī)床對(duì)零件的加工時(shí)間是確定型的，大多數(shù)情況服務(wù)時(shí)間是隨機(jī)型的。圖圖1010-2-2（a）（b）（c）121122nnn 1.2 排隊(duì)模型的分類排隊(duì)模型的分類n 按照排

9、隊(duì)系統(tǒng)組成部分的主要特征可以對(duì)排隊(duì)模型進(jìn)行分類。1971年排隊(duì)論符號(hào)標(biāo)準(zhǔn)化會(huì)議決定，排隊(duì)模型分類符號(hào)為：n X/Y/Z/A/B/Cn其中 X處填寫顧客相繼到達(dá)時(shí)間間隔的分布；n Y處填寫服務(wù)時(shí)間的分布；n Z處填寫并列的服務(wù)臺(tái)數(shù)量；n A處填寫系統(tǒng)容量限制；n B處填寫顧客源數(shù)量；n C處填寫服務(wù)次序，如先到先服務(wù)FCFS；后到先服務(wù)LCFS等，如果略去該項(xiàng)則表示先到先服務(wù)。先到先服務(wù)。n 表示相繼到達(dá)間隔時(shí)間和服務(wù)時(shí)間的各種分布符號(hào)是：n M 負(fù)指數(shù)分布（Markov）n D 確定型分布（Deterministic） n Ekk階愛(ài)爾朗分布（Erlang）n GI一般獨(dú)立分布的時(shí)間間隔（Ge

10、neral Independent）n G一般服務(wù)時(shí)間的分布（ General ） 例如：M/M/1/表示顧客相繼到達(dá)的間隔時(shí)間為負(fù)指數(shù)分布，服務(wù)時(shí)間為負(fù)指數(shù)分布，單服務(wù)臺(tái)，系統(tǒng)對(duì)顧客無(wú)限制，顧客源無(wú)限，先到先服務(wù)的服務(wù)模型。 1.3 排隊(duì)模型的參數(shù)排隊(duì)模型的參數(shù) 在排隊(duì)系統(tǒng)的分析計(jì)算中，要用到下面一些概念和符號(hào)：n Pn（t）在時(shí)刻t系統(tǒng)中恰好有n個(gè)顧客的概率。n N（t）在時(shí)刻t服務(wù)系統(tǒng)中的顧客數(shù)。n 穩(wěn)定狀態(tài)當(dāng)一個(gè)排隊(duì)服務(wù)系統(tǒng)開(kāi)始運(yùn)轉(zhuǎn)時(shí)，系統(tǒng)狀態(tài)很大程度上取決于系統(tǒng)的初始狀態(tài)和運(yùn)轉(zhuǎn)經(jīng)歷的時(shí)間，但過(guò)去一段時(shí)間后，系統(tǒng)的狀態(tài)將獨(dú)立于初始狀態(tài)及經(jīng)歷的時(shí)間，這時(shí)稱系統(tǒng)處于穩(wěn)定狀態(tài)。在穩(wěn)定狀態(tài)下，

11、系統(tǒng)處于某一狀態(tài)的概率是一個(gè)常數(shù)。所以Pn（t）可寫為Pn。由于對(duì)系統(tǒng)的瞬時(shí)狀態(tài)分析比較困難，所以排隊(duì)論中主要研究系統(tǒng)處于穩(wěn)定狀態(tài)的工作情況。n n當(dāng)系統(tǒng)有n個(gè)顧客時(shí)，新來(lái)顧客的平均到達(dá)率（單位時(shí)間到達(dá)的顧客數(shù)），則1/ n表示相鄰兩個(gè)顧客到達(dá)的平均間隔時(shí)間。如60分鐘內(nèi)到達(dá)30個(gè)顧客，則平均到達(dá)率n=3060=1/2（人/分鐘），平均間隔時(shí)間為1/ n =2（分鐘），即平均每隔2分鐘來(lái)1人。n n當(dāng)系統(tǒng)有n個(gè)顧客時(shí)，整個(gè)系統(tǒng)的服務(wù)率（單位時(shí)間服務(wù)完的顧客數(shù)），則1/ n表示對(duì)每個(gè)顧客的平均服務(wù)時(shí)間。如60分鐘內(nèi)服務(wù)完3個(gè)顧客，則平均服務(wù)率n=360=0.05（人/分鐘），對(duì)每個(gè)顧客的平均服務(wù)時(shí)間為1/ n=20（分鐘），即平均每20分鐘服務(wù)