【文章內(nèi)容簡介】 heory) ，又稱 隨機(jī)服務(wù)系統(tǒng)理論(Random Service System Theory),是一門研究擁擠現(xiàn)象(排隊、等待 )的科學(xué)。具體地說，它是在研究各種排隊系統(tǒng)概率規(guī)律性的基礎(chǔ)上，解決相應(yīng)排隊系統(tǒng)的 最優(yōu)設(shè)計 和 最優(yōu)控制 問題。是運籌學(xué)的一個重要分支。 ? 排隊論是 1909年由丹麥工程師愛爾朗 ()在研究電話系統(tǒng)時創(chuàng)立的。 第 20頁 西南科技大學(xué)制造科學(xué)與工程學(xué)院工業(yè)工程與設(shè)計系 石宇強(qiáng) 運籌學(xué) 167。 基本概念 排隊的兩大特征： ? 顧客 —— 要求服務(wù)的對象。 ? 服務(wù)員 —— 提供服務(wù)的服務(wù)者（也稱服務(wù)機(jī)構(gòu)）。 ? 顧客、服務(wù)員的含義是廣義的。 第 21頁 西南科技大學(xué)制造科學(xué)與工程學(xué)院工業(yè)工程與設(shè)計系 石宇強(qiáng) 運籌學(xué) 排隊的不一定是人，也可以是物 。如生產(chǎn)線上的原材料，半成品等待加工；因故障而停止運行的機(jī)器設(shè)備在等待修理；碼頭上的船只等待裝貨或卸貨；要下降的飛機(jī)因跑道不空而在空中盤旋等。 進(jìn)行服務(wù)的也不一定是人 ，可以是跑道，自動售貨機(jī)，公共汽車等 。 第 22頁 西南科技大學(xué)制造科學(xué)與工程學(xué)院工業(yè)工程與設(shè)計系 石宇強(qiáng) 運籌學(xué) 167。 基本概念 有形排隊現(xiàn)象： 進(jìn)餐館就餐，到圖書館借書車站等車，去醫(yī)院看病，售票處售票，到工具房領(lǐng)物品等現(xiàn)象。 無形排隊現(xiàn)象： 如幾個旅客同時打電話訂車票；如果有一人正在通話，其他人只得在各自的電話機(jī)前等待，他們分散在不同的地方，形成一個無形的隊列在等待通電話。 第 23頁 西南科技大學(xué)制造科學(xué)與工程學(xué)院工業(yè)工程與設(shè)計系 石宇強(qiáng) 運籌學(xué) 排隊系統(tǒng)類型： 服務(wù)臺 顧客到達(dá) 服務(wù)完成后離開 單服務(wù)臺排隊系統(tǒng) 第 24頁 西南科技大學(xué)制造科學(xué)與工程學(xué)院工業(yè)工程與設(shè)計系 石宇強(qiáng) 運籌學(xué) 排隊系統(tǒng)類型： 服務(wù)臺 2 顧客到達(dá) 服務(wù)完成后離開 S個服務(wù)臺，一個隊列的排隊系統(tǒng) 服務(wù)臺 s 服務(wù)臺 1 第 25頁 西南科技大學(xué)制造科學(xué)與工程學(xué)院工業(yè)工程與設(shè)計系 石宇強(qiáng) 運籌學(xué) 排隊系統(tǒng)類型： 服務(wù)臺 2 顧客到達(dá) 服務(wù)完成后離開 S個服務(wù)臺， S個隊列的排隊系統(tǒng) 服務(wù)臺 s 服務(wù)臺 1 服務(wù)完成后離開 服務(wù)完成后離開 第 26頁 西南科技大學(xué)制造科學(xué)與工程學(xué)院工業(yè)工程與設(shè)計系 石宇強(qiáng) 運籌學(xué) 排隊系統(tǒng)類型： 服務(wù)臺 1 顧客到達(dá) 離開 多服務(wù)臺串聯(lián)排隊系統(tǒng) 服務(wù)臺 s 第 27頁 西南科技大學(xué)制造科學(xué)與工程學(xué)院工業(yè)工程與設(shè)計系 石宇強(qiáng) 運籌學(xué) 排隊系統(tǒng)類型： 服務(wù)機(jī)構(gòu) 聚 散 隨機(jī)聚散服務(wù)系統(tǒng) （輸入） （輸出） 第 28頁 西南科技大學(xué)制造科學(xué)與工程學(xué)院工業(yè)工程與設(shè)計系 石宇強(qiáng) 運籌學(xué) 隨機(jī)性 ——顧客到達(dá)情況 與 顧客接受服務(wù)的時間 是隨機(jī)的。 一般來說，排隊論所研究的排隊系統(tǒng)中， 顧客相繼到達(dá)時間間隔和 服務(wù)時間 這兩個量中至少有一個是隨機(jī)的，因此，排隊論又稱隨機(jī)服務(wù)理論。 第 29頁 西南科技大學(xué)制造科學(xué)與工程學(xué)院工業(yè)工程與設(shè)計系 石宇強(qiáng) 運籌學(xué) 基本組成 輸入來源 隊 列 服務(wù)機(jī)構(gòu) 排隊系統(tǒng) 顧客 服務(wù)完離開 排隊系統(tǒng)的三個基本組成部分 . ?輸入過程 (顧客按照怎樣的規(guī)律到達(dá) )。 ?排隊規(guī)則 (顧客按照一定規(guī)則排隊等待服務(wù) )。 ?服務(wù)機(jī)構(gòu) (服務(wù)機(jī)構(gòu)的設(shè)置 ,服務(wù)臺的數(shù)量 ,服務(wù)的方式 ,服務(wù)時間分布等 ) 第 30頁 西南科技大學(xué)制造科學(xué)與工程學(xué)院工業(yè)工程與設(shè)計系 石宇強(qiáng) 運籌學(xué) ?輸入過程 ? 顧客總體（顧客源）數(shù) ：可能是有限，也可能是無限。 河流上游流入水庫的水量可認(rèn)為是無限的；車間內(nèi)停機(jī)待修的機(jī)器顯然是有限的。 ? 到達(dá)方式 ：是單個到達(dá)還是成批到達(dá)。庫存問題中，若把進(jìn)來的貨看成顧客，則為成批到達(dá)的例子。 第 31頁 西南科技大學(xué)制造科學(xué)與工程學(xué)院工業(yè)工程與設(shè)計系 石宇強(qiáng) 運籌學(xué) ?顧客（單個或成批） 相繼到達(dá)的時間間隔分布 ：這是刻劃輸入過程的最重要內(nèi)容。令 T0=0， Tn表示第 n顧客到達(dá)的時刻，則有 T0?T1 ? T2… .. ? Tn ? …… 記 Xn= Tn –Tn1 n=1,2,… ,則 Xn是第 n顧客與第 n1顧客到達(dá)的時間間隔。 一般假定 {Xn}是獨立同分布，并記分布函數(shù)為 A(t)。 ?輸入過程 第 32頁 西南科技大學(xué)制造科學(xué)與工程學(xué)院工業(yè)工程與設(shè)計系 石宇強(qiáng) 運籌學(xué) {Xn}的分布 A(t)常見的有： o 定常分布（ D） ：顧客相繼到達(dá)的時間間隔為確定的。如產(chǎn)品通過傳送帶進(jìn)入包裝箱就是定常分布。 o 最簡流（或稱 Poisson)（ M） ：顧客相繼到達(dá)的時間間隔 {Xn}為獨立的，同為負(fù)指數(shù)分布，其密度函數(shù)為： a(t)= ?e ?t t?0 0 t 0 第 33頁 西南科技大學(xué)制造科學(xué)與工程學(xué)院工業(yè)工程與設(shè)計系 石宇強(qiáng) 運籌學(xué) ?排隊及排隊規(guī)則 ?排隊 o 有限排隊 ——排隊系統(tǒng)中顧客數(shù)是有限的。 o 無限排隊 ——顧客數(shù)是無限，隊列可以排到無限長（ 等待制排隊系統(tǒng) ）。 第 34頁 西南科技大學(xué)制造科學(xué)與工程學(xué)院工業(yè)工程與設(shè)計系 石宇強(qiáng) 運籌學(xué) 有限排隊還可以分成： ? 損失制排隊系統(tǒng) ：排隊空間為零的系統(tǒng)，即不允許排隊。（顧客到達(dá)時，服務(wù)臺占滿，顧客自動離開，不再回來）（電話系統(tǒng)） ? 混合制排隊系統(tǒng) ：是等待制與損失制結(jié)合，即允許排隊，但不允許隊列無限長。 第 35頁 西南科技大學(xué)制造科學(xué)與工程學(xué)院工業(yè)工程與設(shè)計系 石宇強(qiáng) 運籌學(xué) 混合制排隊系統(tǒng) ： ? 隊長有限 。即系統(tǒng)等待空間是有限的。例：最多只能容納 K個顧客在系統(tǒng)中，當(dāng)新顧客到達(dá)時，若系統(tǒng)中的顧客數(shù)（又稱為隊長）小于 K，則可進(jìn)入系統(tǒng)排隊或接受服務(wù)；否則，便離開系統(tǒng)，并不再回來。如水庫的庫容是有限的，旅館的床位是有限的。 第 36頁 西南科技大學(xué)制造科學(xué)與工程學(xué)院工業(yè)工程與設(shè)計系 石宇強(qiáng) 運籌學(xué) 混合制排隊系統(tǒng)： ? 等待時間有限 。即顧客在系統(tǒng)中等待時間不超過某一給定的長度 T，當(dāng)?shù)却龝r間超過 T時，顧客將自動離開，不再回來。如易損失的電子元件的庫存問題，超過一定存儲時間的元器件被自動認(rèn)為失效。 第 37頁 西南科技大學(xué)制造科學(xué)與工程學(xué)院工業(yè)工程與設(shè)計系 石宇強(qiáng) 運籌學(xué) 混合制排隊系統(tǒng)： ? 逗留時間 （等待時間與服務(wù)時間之和）有限。例：用高射炮射擊飛機(jī)，當(dāng)敵機(jī)飛越射擊有效區(qū)域的時間為 t時，若這個時間內(nèi)未被擊落，也就不可能再被擊落了。 第 38頁 西南科技大學(xué)制造科學(xué)與工程學(xué)院工業(yè)工程與設(shè)計系 石宇強(qiáng) 運籌學(xué) 損失制和等待制可看成是混合制的特殊情形，如記 s為系統(tǒng)中服務(wù)臺個數(shù)，則當(dāng) k=s時，混合制即為損失制；當(dāng) k=?時，即成為等待制。 第 39頁 西南科技大學(xué)制造科學(xué)與工程學(xué)院工業(yè)工程與設(shè)計系 石宇強(qiáng) 運籌學(xué) ?排隊規(guī)則 當(dāng)顧客到達(dá)時，若所有服務(wù)臺都被占有且又允許排隊，則該顧客將進(jìn)入隊列等待。服務(wù)臺對顧客進(jìn)行服務(wù)所遵循的規(guī)則通常有： o 先來先服務(wù)（ FCFS） 第 40頁 西南科技大學(xué)制造科學(xué)與工程學(xué)院工業(yè)工程與設(shè)計系 石宇強(qiáng) 運籌學(xué) o 后來先服務(wù)（ LCFS） 。在許多庫存系統(tǒng)中就會出現(xiàn)這種情況，如鋼板存入倉庫后，需要時總是從