吉林大學遠程教育 運籌學課件8.1

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

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

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

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

5、樣才能做到既保證一定的服務質量指標，又使服務設施費用經(jīng)濟合理，恰當?shù)亟鉀Q顧客排隊時間與服務設施費用大小這對矛盾，就是研究隨機服務系統(tǒng)的理論排隊論所要研究解決的問題。 排隊論的理論起源于對電話服務系統(tǒng)的研究。從1909年開始，丹麥的電話工程師愛爾朗（A.K.Eelang）等人在這方面進行了長期的工作，取得了最早的成果。以后排隊論陸續(xù)應用于陸空交通、機器管理、水庫設計和可靠性理論等方面。六十年代，隨著電子計算機蓬勃發(fā)展的需要，又應用于計算機網(wǎng)絡的最優(yōu)設計。在接近九十年的歷史中，排隊論無論在理論或應用上都有了飛速進展。由于在電子計算機上進行數(shù)字模擬技術的發(fā)展，排隊論已成為解決工程設計和管理問題的有力

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

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

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

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

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

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