浅谈排队论
排隊(duì)論起源于 1909 年丹麥電話工程師 A. K．愛(ài)爾朗的工作，他對(duì)電話通話擁擠問(wèn) 題進(jìn)行了研究。1917 年，愛(ài)爾朗發(fā)表了他的著名的文章—“自動(dòng)電話交換中的概率理 論的幾個(gè)問(wèn)題的解決”。排隊(duì)論已廣泛應(yīng)用于解決軍事、運(yùn)輸、維修、生產(chǎn)、服務(wù)、庫(kù) 存、醫(yī)療衛(wèi)生、教育、水利灌溉之類的排隊(duì)系統(tǒng)的問(wèn)題，顯示了強(qiáng)大的生命力。
排隊(duì)是在日常生活中經(jīng)常遇到的現(xiàn)象，如顧客到商店購(gòu)買物品、病人到醫(yī)院看病常 常要排隊(duì)。此時(shí)要求服務(wù)的數(shù)量超過(guò)服務(wù)機(jī)構(gòu)（服務(wù)臺(tái)、服務(wù)員等）的容量。也就是說(shuō)， 到達(dá)的顧客不能立即得到服務(wù)，因而出現(xiàn)了排隊(duì)現(xiàn)象。這種現(xiàn)象不僅在個(gè)人日常生活中 出現(xiàn)，電話局的占線問(wèn)題，車站、碼頭等交通樞紐的車船堵塞和疏導(dǎo)，故障機(jī)器的停機(jī) 待修，水庫(kù)的存貯調(diào)節(jié)等都是有形或無(wú)形的排隊(duì)現(xiàn)象。由于顧客到達(dá)和服務(wù)時(shí)間的隨機(jī) 性。可以說(shuō)排隊(duì)現(xiàn)象幾乎是不可避免的。
排隊(duì)論是研究排隊(duì)系統(tǒng)（又稱隨機(jī)服務(wù)系統(tǒng)）的數(shù)學(xué)理論與方法。 它的研究目的是要回答如何改進(jìn)服務(wù)機(jī)構(gòu)或組織被服務(wù)的對(duì)象，使得某種指標(biāo)達(dá)到最優(yōu)的問(wèn)題。比如一個(gè)港口應(yīng)該有多少個(gè)碼頭，一個(gè)工廠應(yīng)該有多少維修人員等。
01 排隊(duì)論背景與發(fā)展介紹
排隊(duì)論最早起源于對(duì)電話通訊排隊(duì)接線的研究，早在1909年，丹麥數(shù)學(xué)家A. K. Erlang 發(fā)表了The Theory of Probabilities and Telephone Conversations 初步產(chǎn)開了對(duì)由于隨機(jī)需求的出現(xiàn)而產(chǎn)生非穩(wěn)態(tài)隊(duì)列的現(xiàn)象的研究。
在他后期的工作中，他發(fā)現(xiàn)了幾個(gè)重要結(jié)論: 自動(dòng)電話通訊系統(tǒng)可以以兩種基本概率模型模擬:
Erlang亦提出隊(duì)列穩(wěn)態(tài)平衡的概念與排隊(duì)系統(tǒng)的初步優(yōu)化辦法。Erlang 之后，多名學(xué)者將其工作做進(jìn)一步的衍生拓展：Thornton Fry: Probabilities and Its Engineering Uses, Felix Pollaczek 進(jìn)一步整理了泊松輸入，廣義輸出的單/多服務(wù)流模型，同時(shí)俄羅斯數(shù)學(xué)家Kolmogorov, Khintchine也涉足該領(lǐng)域。
排隊(duì)論本源自對(duì)實(shí)際現(xiàn)象的研究，而后接近半個(gè)世紀(jì)，排隊(duì)論主要為理論模型發(fā)展，(生滅理論，嵌入馬爾可夫模型) 。直到二戰(zhàn)以后，學(xué)者開始為該理論賦予應(yīng)用價(jià)值，大量研究開始導(dǎo)向如何精確求解先前學(xué)者留下的復(fù)雜數(shù)學(xué)模型，并直接應(yīng)用于現(xiàn)實(shí)的管理決策中。主要如復(fù)雜排隊(duì)模型，排隊(duì)網(wǎng)絡(luò)的近似解與數(shù)值模擬辦法等。近現(xiàn)代排隊(duì)論主要為管理決策軟件的開發(fā)提供理論與模擬支持。
排隊(duì)論（Queuing Theory）也稱隨機(jī)服務(wù)系統(tǒng)理論，就是為解決上述問(wèn)題而發(fā)展 的一門學(xué)科。它研究的內(nèi)容有下列三部分：
（i）性態(tài)問(wèn)題，即研究各種排隊(duì)系統(tǒng)的概率規(guī)律性，主要是研究隊(duì)長(zhǎng)分布、等待時(shí)間分布和忙期分布等，包括了瞬態(tài)和穩(wěn)態(tài)兩種情形。
（ii）最優(yōu)化問(wèn)題，又分靜態(tài)最優(yōu)和動(dòng)態(tài)最優(yōu)，前者指最優(yōu)設(shè)計(jì)。后者指現(xiàn)有排隊(duì)系統(tǒng)的最優(yōu)運(yùn)營(yíng)。
（iii）排隊(duì)系統(tǒng)的統(tǒng)計(jì)推斷，即判斷一個(gè)給定的排隊(duì)系統(tǒng)符合于哪種模型，以便根據(jù)排隊(duì)理論進(jìn)行分析研究。
這里將介紹排隊(duì)論的一些基本知識(shí)，分析幾個(gè)常見(jiàn)的排隊(duì)模型。
02 排隊(duì)機(jī)制與基本模型辦法
2.0 排隊(duì)模型
2.0.1 過(guò)程的一般表示
下圖是排隊(duì)論的一般模型。
圖中虛線所包含的部分為排隊(duì)系統(tǒng)。各個(gè)顧客從顧客源出發(fā)，隨機(jī)地來(lái)到服務(wù)機(jī)構(gòu)，按 一定的排隊(duì)規(guī)則等待服務(wù)，直到按一定的服務(wù)規(guī)則接受完服務(wù)后離開排隊(duì)系統(tǒng)。
凡要求服務(wù)的對(duì)象統(tǒng)稱為顧客，為顧客服務(wù)的人或物稱為服務(wù)員，由顧客和服務(wù)員組成服務(wù)系統(tǒng)。對(duì)于一個(gè)服務(wù)系統(tǒng)來(lái)說(shuō)，如果服務(wù)機(jī)構(gòu)過(guò)小，以致不能滿足要求服務(wù)的 眾多顧客的需要，那么就會(huì)產(chǎn)生擁擠現(xiàn)象而使服務(wù)質(zhì)量降低。 因此，顧客總希望服務(wù) 機(jī)構(gòu)越大越好，但是，如果服務(wù)機(jī)構(gòu)過(guò)大，人力和物力方面的開支也就相應(yīng)增加，從而 會(huì)造成浪費(fèi)，因此研究排隊(duì)模型的目的就是要在顧客需要和服務(wù)機(jī)構(gòu)的規(guī)模之間進(jìn)行權(quán)衡決策，使其達(dá)到合理的平衡。
2.0.2 排隊(duì)系統(tǒng)的組成和特征
一般的排隊(duì)過(guò)程都由輸入過(guò)程、排隊(duì)規(guī)則、服務(wù)過(guò)程三部分組成，現(xiàn)分述如下：
2.0.2.1 輸入過(guò)程
輸入過(guò)程是指顧客到來(lái)時(shí)間的規(guī)律性，可能有下列不同情況：
（i）顧客的組成可能是有限的，也可能是無(wú)限的。
（ii）顧客到達(dá)的方式可能是一個(gè)—個(gè)的，也可能是成批的。
（iii）顧客到達(dá)可以是相互獨(dú)立的，即以前的到達(dá)情況對(duì)以后的到達(dá)沒(méi)有影響； 否則是相關(guān)的。
（iv）輸入過(guò)程可以是平穩(wěn)的，即相繼到達(dá)的間隔時(shí)間分布及其數(shù)學(xué)期望、方差等數(shù)字特征都與時(shí)間無(wú)關(guān)，否則是非平穩(wěn)的。
2.0.2.2 排隊(duì)規(guī)則
排隊(duì)規(guī)則指到達(dá)排隊(duì)系統(tǒng)的顧客按怎樣的規(guī)則排隊(duì)等待，可分為損失制，等待制和混合制三種。
（i）損失制（消失制）。當(dāng)顧客到達(dá)時(shí)，所有的服務(wù)臺(tái)均被占用，顧客隨即離去。
（ii）等待制。當(dāng)顧客到達(dá)時(shí)，所有的服務(wù)臺(tái)均被占用，顧客就排隊(duì)等待，直到接 受完服務(wù)才離去。
例如出故障的機(jī)器排隊(duì)等待維修就是這種情況。
（iii）混合制。介于損失制和等待制之間的是混合制，即既有等待又有損失。有隊(duì)列長(zhǎng)度有限和排隊(duì)等待時(shí)間有限兩種情況，在限度以內(nèi)就排隊(duì)等待，超過(guò)一定限度就 離去。
排隊(duì)方式還分為單列、多列和循環(huán)隊(duì)列。
2.0.2.2.3 服務(wù)過(guò)程
（i）服務(wù)機(jī)構(gòu)。
主要有以下幾種類型：單服務(wù)臺(tái)；多服務(wù)臺(tái)并聯(lián)（每個(gè)服務(wù)臺(tái)同 時(shí)為不同顧客服務(wù)）；多服務(wù)臺(tái)串聯(lián)（多服務(wù)臺(tái)依次為同一顧客服務(wù)）；混合型。
（ii）服務(wù)規(guī)則。
按為顧客服務(wù)的次序采用以下幾種規(guī)則：
①先到先服務(wù)，這是通常的情形。
②后到先服務(wù)，如情報(bào)系統(tǒng)中，最后到的情報(bào)信息往往最有價(jià)值，因而常被優(yōu)先處 理。
③隨機(jī)服務(wù)，服務(wù)臺(tái)從等待的顧客中隨機(jī)地取其一進(jìn)行服務(wù)，而不管到達(dá)的先后。
④優(yōu)先服務(wù)，如醫(yī)療系統(tǒng)對(duì)病情嚴(yán)重的病人給予優(yōu)先治療。
2.1 基本排隊(duì)機(jī)制
在絕大多數(shù)情況下，以下6個(gè)基礎(chǔ)屬性可以較完善地描述一個(gè)排隊(duì)等待現(xiàn)象。
(1)顧客的抵達(dá)分布情況
顧客可以指實(shí)體的顧客，如銀行排隊(duì)等待的客人，亦可代指等待安排維修的機(jī)器;
抵達(dá)分布情況是指如何用概率模型模擬相鄰顧客抵達(dá)服務(wù)臺(tái)的時(shí)間間隔
(2) 服務(wù)臺(tái)的服務(wù)情況
銀行窗口服務(wù)不同業(yè)務(wù)的時(shí)間分布，生產(chǎn)線中每道工序所用時(shí)間的時(shí)間分布等。
(3) 排隊(duì)原則
(4) 系統(tǒng)容納量
(5) 服務(wù)臺(tái)數(shù)量
(6) 服務(wù)流程數(shù)量
2.1.1 顧客的抵達(dá)分布情況
在大部分隊(duì)列中，顧客的抵達(dá)都是隨機(jī)現(xiàn)象(非隨機(jī)現(xiàn)象如完美平衡的生產(chǎn)流水線)。因此需要用一個(gè)概率模型模擬各個(gè)相鄰顧客的抵達(dá)時(shí)間間隔。常見(jiàn)模型如指數(shù)分布。
關(guān)于為何指數(shù)分布與泊松過(guò)程能較好地模擬隨機(jī)現(xiàn)象，參見(jiàn)本節(jié)2.3。
同時(shí)一些特殊的客戶表現(xiàn)亦需要參考，比如:如果一個(gè)客戶遇到較長(zhǎng)隊(duì)列，他可能會(huì)拒絕加入(balked)；現(xiàn)有隊(duì)列的客戶由于排隊(duì)時(shí)間過(guò)長(zhǎng)而離開(impatience, reneged). 當(dāng)出現(xiàn)多條服務(wù)流時(shí)，顧客會(huì)在不同隊(duì)列之間流動(dòng)，導(dǎo)致從理論上講的絕對(duì)完美等長(zhǎng)多服務(wù)流(jockey)。
最后，如果顧客抵達(dá)時(shí)間的概率分布不隨時(shí)間而變化，稱之為穩(wěn)態(tài)抵達(dá)分布(stationary), 反之非穩(wěn)態(tài)(non-stationary)。
2.1.2 服務(wù)臺(tái)的服務(wù)情況
亦稱之為服務(wù)機(jī)構(gòu)。不同服務(wù)臺(tái)的服務(wù)時(shí)間亦需要用一個(gè)概率模型來(lái)表示。比如醫(yī)院急診室每個(gè)醫(yī)生診療時(shí)間的時(shí)間分布，維修車間對(duì)每臺(tái)等待維修的機(jī)器的處理時(shí)間分布等。
以下幾個(gè)特殊現(xiàn)象亦需特殊考慮: 服務(wù)時(shí)間的長(zhǎng)短與隊(duì)列的長(zhǎng)短有關(guān)，這個(gè)很好理解，當(dāng)一個(gè)柜員看到顧客較多時(shí)，自然會(huì)加快業(yè)務(wù)處理速度 (state-dependent). 同樣，服務(wù)時(shí)間亦可隨時(shí)間變化而變化(維修工逐漸積累經(jīng)驗(yàn)),出現(xiàn)stationary 和 non-stationary。
2.1.3 排隊(duì)原則
先到先服務(wù), first come first service ( FCFS).
后到先服務(wù)原則(LCFS). 比如從倉(cāng)庫(kù)里取貨，后到的貨物由于堆在最外圍，往往先被取走。
隨機(jī)服務(wù)原則，比如車牌號(hào)搖號(hào)，不隨從任何先來(lái)后到的原則……
優(yōu)先排隊(duì)原則: 如果軍人抵達(dá)的話，可以直接排到隊(duì)列首位(priority discipline)。
2.1.4 系統(tǒng)容納量，服務(wù)臺(tái)數(shù)量，服務(wù)流程數(shù)量
這三兄弟相對(duì)好理解, 系統(tǒng)容納量: 火車站排隊(duì)大廳最多容納一千人隊(duì)列，服務(wù)臺(tái)數(shù)量: 某銀行總行有12個(gè)窗口，而郊區(qū)支行只有4個(gè)，服務(wù)流程數(shù)(會(huì)形成復(fù)雜排隊(duì)網(wǎng)絡(luò)): 體檢項(xiàng)目順序依次一個(gè)有10項(xiàng)，某產(chǎn)線共有24道工序，為消除排隊(duì)需要平衡產(chǎn)線。
圖1. 某多服務(wù)臺(tái)，多服務(wù)流程隊(duì)列網(wǎng)絡(luò)
2.2 常見(jiàn)術(shù)語(yǔ)與Notation
排隊(duì)模型用六個(gè)符號(hào)表示，在符號(hào)之間用斜線隔開，即 X /Y / Z / A/ B /C 。
第一 個(gè)符號(hào) X 表示顧客到達(dá)流或顧客到達(dá)間隔時(shí)間的分布；
第二個(gè)符號(hào)Y 表示服務(wù)時(shí)間的分布；
第三個(gè)符號(hào) Z 表示服務(wù)臺(tái)數(shù)目；
第四個(gè)符號(hào) A 是系統(tǒng)容量限制；
第五個(gè)符號(hào) B 是 顧客源數(shù)目；
第六個(gè)符號(hào)C 是服務(wù)規(guī)則，
如先到先服務(wù) FCFS，后到先服務(wù) LCFS 等。并約定，如略去后三項(xiàng)，即指 X /Y / Z / ∞ / ∞ / FCFS的情形。
我們只討論先到先服務(wù) FCFS 的情形，所以略去第六項(xiàng)。
對(duì)于常見(jiàn)的大部分模型，我們均假設(shè)顧客抵達(dá)時(shí)間的分布，服務(wù)臺(tái)服務(wù)時(shí)間的分布為獨(dú)立同分布(independent and identically distributed), 通用隊(duì)列模型表達(dá)式如下:
表示顧客到達(dá)間隔時(shí)間和服務(wù)時(shí)間的分布的約定符號(hào)為：
M — 指數(shù)分布（ M 是 Markov 的字頭，因?yàn)橹笖?shù)分布具有無(wú)記憶性，即 Markov 性）；
D — 確定型（Deterministic）；
EkE_kEk? — k 階愛(ài)爾朗(Erlang)分布；
G — 一般（general）服務(wù)時(shí)間的分布；
GI — 一般相互獨(dú)立（General Independent）的時(shí)間間隔的分布。
例如， M / M /1表示相繼到達(dá)間隔時(shí)間為指數(shù)分布、服務(wù)時(shí)間為指數(shù)分布、單服 務(wù)臺(tái)、等待制系統(tǒng)。
D / M / c 表示確定的到達(dá)時(shí)間、服務(wù)時(shí)間為指數(shù)分布、 c 個(gè)平行 服務(wù)臺(tái)（但顧客是一隊(duì)）的模型。
表1：通用隊(duì)列模型表達(dá)式符號(hào)匯總
值得注意的是，我們會(huì)常常省去后兩個(gè)位置，默認(rèn)為系統(tǒng)無(wú)容納上限，先到先服務(wù)原則。如非常經(jīng)典又基礎(chǔ)的 M/M/1 及 M/M/S 模型 (顧客抵達(dá)與服務(wù)時(shí)間均為指數(shù)分布，一個(gè)或多個(gè)服務(wù)臺(tái)).
Utilization Factor(暫譯為占用率)，是一個(gè)排隊(duì)系統(tǒng)顧客抵達(dá)速率與總共多個(gè)平行服務(wù)速率的比值。很好理解，這個(gè)值如果大于1的話，隊(duì)列會(huì)無(wú)限變長(zhǎng)，而這個(gè)值小于1的話，隊(duì)列系統(tǒng)會(huì)從一開始的過(guò)渡狀態(tài) (transient condition) 逐漸趨于穩(wěn)態(tài) (steady-state condition) 關(guān)于這個(gè)狀態(tài)的過(guò)渡與轉(zhuǎn)換的討論，不在本文章討論之中，筆者在此呈現(xiàn)的各種有趣結(jié)論，均以穩(wěn)態(tài)隊(duì)列為對(duì)象:
2.3 排隊(duì)系統(tǒng)的運(yùn)行指標(biāo)
為了研究排隊(duì)系統(tǒng)運(yùn)行的效率，估計(jì)其服務(wù)質(zhì)量，確定系統(tǒng)的最優(yōu)參數(shù)，評(píng)價(jià)系統(tǒng) 的結(jié)構(gòu)是否合理并研究其改進(jìn)的措施，必須確定用以判斷系統(tǒng)運(yùn)行優(yōu)劣的基本數(shù)量指標(biāo)，這些數(shù)量指標(biāo)通常是：
(i) 平均隊(duì)長(zhǎng)：指系統(tǒng)內(nèi)顧客數(shù)（包括正被服務(wù)的顧客與排隊(duì)等待服務(wù)的顧客）的數(shù)學(xué)期望，記作 Ls 。
(ii) 平均排隊(duì)長(zhǎng):指系統(tǒng)內(nèi)等待服務(wù)的顧客數(shù)的數(shù)學(xué)期望，記作 Lq 。
(iii) 平均逗留時(shí)間：顧客在系統(tǒng)內(nèi)逗留時(shí)間（包括排隊(duì)等待的時(shí)間和接受服務(wù)的 時(shí)間）的數(shù)學(xué)期望，記作Ws 。
(iv) 平均等待時(shí)間：指一個(gè)顧客在排隊(duì)系統(tǒng)中排隊(duì)等待時(shí)間的數(shù)學(xué)期望，記作 Wq 。
(v) 平均忙期：指服務(wù)機(jī)構(gòu)連續(xù)繁忙時(shí)間（顧客到達(dá)空閑服務(wù)機(jī)構(gòu)起，到服務(wù)機(jī)構(gòu)再次空閑止的時(shí)間）長(zhǎng)度的數(shù)學(xué)期望，記為Tb 。
還有由于顧客被拒絕而使企業(yè)受到損失的損失率以及以后經(jīng)常遇到的服務(wù)強(qiáng)度等， 這些都是很重要的指標(biāo)。
計(jì)算這些指標(biāo)的基礎(chǔ)是表達(dá)系統(tǒng)狀態(tài)的概率。所謂系統(tǒng)的狀態(tài)即指系統(tǒng)中顧客數(shù)， 如果系統(tǒng)中有n 個(gè)顧客就說(shuō)系統(tǒng)的狀態(tài)是n ，它的可能值是
2.4 輸入過(guò)程與服務(wù)時(shí)間的分布
排隊(duì)系統(tǒng)中的事件流包括顧客到達(dá)流和服務(wù)時(shí)間流。由于顧客到達(dá)的間隔時(shí)間和服 務(wù)時(shí)間不可能是負(fù)值，因此，它的分布是非負(fù)隨機(jī)變量的分布。最常用的分布有泊松分布、確定型分布，指數(shù)分布和愛(ài)爾朗分布。
2.4.1 泊松流與指數(shù)分布
在上述條件下，我們研究顧客到達(dá)數(shù)n 的概率分布。
對(duì)于泊松流, λ\lambdaλ 表示單位時(shí)間平均到達(dá)的顧客數(shù),所以 1λ\frac{1}{\lambda }λ1? 就表示相繼顧客到達(dá)平均 間隔時(shí)間，而這正和 ET 的意義相符。 對(duì)一顧客的服務(wù)時(shí)間也就是在忙期相繼離開系統(tǒng)的兩顧客的間隔時(shí)間，有時(shí)也服從 指數(shù)分布。這時(shí)設(shè)它的分布函數(shù)和密度函數(shù)分別是
2.4.2 常用的幾種概率分布及其產(chǎn)生
2.4.2.1 常用的連續(xù)型概率分布
我們只給出這些分布的參數(shù)、記號(hào)和通常的應(yīng)用范圍，更詳細(xì)的內(nèi)容參看專門的概 率論書籍。
（i）均勻分布
區(qū)間 (a,b) 內(nèi)的均勻分布記作U(a,b) 。服從U(0,1) 分布的隨機(jī)變量又稱為隨機(jī) 數(shù)，它是產(chǎn)生其它隨機(jī)變量的基礎(chǔ)。如若 X 為U(0,1) 分布，則Y = a + (b ? a)X 服從 U(a,b) 。
（ii）正態(tài)分布
正態(tài)分布還可以作為二項(xiàng)分布一定條件下的近似。
（iii）指數(shù)分布
（iv）Gamma 分布、愛(ài)爾朗分布
Gamma 分布又稱愛(ài)爾朗分布。
Gamma 分布是雙參數(shù)α,β 的非對(duì)稱分布，記作G(α,β ) ，期望是αβ 。α = 1時(shí)蛻 化為指數(shù)分布。 n 個(gè)相互獨(dú)立、同分布（參數(shù) λ ）的指數(shù)分布之和是 Gamma 分布 （α = n, β = λ) 。Gamma 分布可用于服務(wù)時(shí)間，零件壽命等。
（v）Weibull 分布
Weibull 分布是雙參數(shù)α,β 的非對(duì)稱分布，記作W(α, β ) 。α = 1時(shí)蛻化為指數(shù)分 布。作為設(shè)備、零件的壽命分布在可靠性分析中有著非常廣泛的應(yīng)用。
（vi）Beta 分布
Beta 分布是區(qū)間(0,1) 內(nèi)的雙參數(shù)、非均勻分布，記作 B(α, β ) 。
2.4.2.2 常用的離散型概率分布
（i）離散均勻分布
（ii）Bernoulli 分布（兩點(diǎn)分布）
Bernoulli 分布是 x = 1,0 處取值的概率分別是 p 和1? p 的兩點(diǎn)分布，記作 Bern( p) 。用于基本的離散模型。
（iii）泊松（Poisson）分布
泊松分布與指數(shù)分布有密切的關(guān)系。當(dāng)顧客平均到達(dá)率為常數(shù) λ 的到達(dá)間隔服從 指數(shù)分布時(shí)，單位時(shí)間內(nèi)到達(dá)的顧客數(shù) K 服從泊松分布，即單位時(shí)間內(nèi)到達(dá) k 位顧客 的概率為
記作 Poisson(λ) 。泊松分布在排隊(duì)服務(wù)、產(chǎn)品檢驗(yàn)、生物與醫(yī)學(xué)統(tǒng)計(jì)、天文、物理等 領(lǐng)域都有廣泛應(yīng)用。
（iv）二項(xiàng)分布
在獨(dú)立進(jìn)行的每次試驗(yàn)中，某事件發(fā)生的概率為 p ，則 n 次試驗(yàn)中該事件發(fā)生的 次數(shù) K 服從二項(xiàng)分布，即發(fā)生k 次的概率為
記作 B(n, p) 。二項(xiàng)分布是n 個(gè)獨(dú)立的 Bernoulli 分布之和。它在產(chǎn)品檢驗(yàn)、保險(xiǎn)、生 物和醫(yī)學(xué)統(tǒng)計(jì)等領(lǐng)域有著廣泛的應(yīng)用。
當(dāng)n,k 很大時(shí)， B(n, p) 近似于正態(tài)分布 N(np,np(1? p)) ；
當(dāng)n 很大、 p 很小， 且np 約為常數(shù)λ 時(shí)， B(n, p) 近似于 Poisson(λ)。
2.4 關(guān)于泊松輸入源的一些討論
本節(jié)我們討論一個(gè)問(wèn)題: 為什么泊松過(guò)程/指數(shù)分布能成為基礎(chǔ)的模擬顧客的隨機(jī)到達(dá)與服務(wù)的完成時(shí)間分布？
2.4.0 補(bǔ)充知識(shí)
a. 常見(jiàn)離散概率分布
-
二項(xiàng)分布 X～B(n,p)
-
泊松分布 X～Poisson(λ)
λ表示單位時(shí)間（面積或體積等）該事件平均發(fā)生次數(shù)（到達(dá)率），則p(x=k)表示單位時(shí)間（面積或體積等）該事件發(fā)生k次的概率
-
負(fù)二項(xiàng)分布 X～NB(r,p)
-
幾何分布 X～Ge§
-
超幾何分布 X～HyG(N,M,n)
b. 常見(jiàn)連續(xù)概率分布
-
均勻分布 X～U(a,b)
-
指數(shù)分布 X～Exp(λ)
-
Erlang分布
愛(ài)爾郎分布與指數(shù)分布一樣多用來(lái)表示獨(dú)立隨機(jī)事件發(fā)生的時(shí)間間隔。相比于指數(shù)分布，愛(ài)爾郎分布更適用于多個(gè)串行過(guò)程，或無(wú)記憶性假設(shè)不顯著的情況下。除非退化為指數(shù)分布，愛(ài)爾郎分布不具有無(wú)記憶性，一次對(duì)其分析相對(duì)困難。一般通過(guò)將愛(ài)爾郎過(guò)程分解為多個(gè)指數(shù)過(guò)程的技巧來(lái)對(duì)愛(ài)爾郎分布進(jìn)行分析。
-
一維正態(tài)分布 X～N(μ,σ2)
-
多維正態(tài)分布 X～N(μ,Σ)
c. 概率論常用分布期望與方差總結(jié)
d. 泊松分布、二項(xiàng)分布、愛(ài)爾朗分布的推導(dǎo)與關(guān)系
①二項(xiàng)分布：
重復(fù)n次伯努利實(shí)驗(yàn)，且每次實(shí)驗(yàn)只有兩種相互對(duì)立結(jié)果，每次實(shí)驗(yàn)相互獨(dú)立，這樣的實(shí)驗(yàn)叫做n重伯努利實(shí)驗(yàn)，得到事件發(fā)生的次數(shù)的分布叫二項(xiàng)分布。
概率分布：
數(shù)字特征：將n重伯努利實(shí)驗(yàn)分解為n個(gè)二項(xiàng)分布易得，期望為np，方差為np(1-p)。
伯努利試驗(yàn)（Bernoulli experiment）是在同樣的條件下重復(fù)地、相互獨(dú)立地進(jìn)行的一種隨機(jī)試驗(yàn)，其特點(diǎn)是該隨機(jī)試驗(yàn)只有兩種可能結(jié)果：發(fā)生或者不發(fā)生。我們假設(shè)該項(xiàng)試驗(yàn)獨(dú)立重復(fù)地進(jìn)行了n次，那么就稱這一系列重復(fù)獨(dú)立的隨機(jī)試驗(yàn)為n重伯努利試驗(yàn)，或稱為伯努利概型。單個(gè)伯努利試驗(yàn)是沒(méi)有多大意義的，然而，當(dāng)我們反復(fù)進(jìn)行伯努利試驗(yàn)，去觀察這些試驗(yàn)有多少是成功的，多少是失敗的，事情就變得有意義了，這些累計(jì)記錄包含了很多潛在的非常有用的信息。
②二項(xiàng)分布到泊松分布
考慮對(duì)于一段時(shí)間（或面積、體積），即單位時(shí)間，將其分為n段（n->∞），因?yàn)槊慷螌?duì)應(yīng)時(shí)間級(jí)短，那么p也應(yīng)該接近0,。那么此時(shí)事件發(fā)生的次數(shù)就服從泊松分布，而原二項(xiàng)分布的期望，即np, 就是事件的平均發(fā)生次數(shù)，即λ=np。
注：第二行到第三行，因?yàn)閚趨于無(wú)窮大，那么n(n-1)…(n-k+1)=n^k
③泊松分布到指數(shù)分布：
如果下次事件發(fā)生間隔為t，那么等同于t時(shí)間內(nèi)事件發(fā)生次數(shù)為0，即從泊松分布推導(dǎo)到指數(shù)分布：
④指數(shù)分布與愛(ài)爾郎分布：
⑤指數(shù)分布無(wú)后效性的推導(dǎo)：
無(wú)后效性（馬爾科夫性）：
當(dāng)一個(gè)隨機(jī)過(guò)程在給定現(xiàn)在狀態(tài)及所有過(guò)去狀態(tài)情況下，其未來(lái)狀態(tài)的條件概率分布僅依賴于當(dāng)前狀態(tài)，即在現(xiàn)在狀態(tài)時(shí)，他與過(guò)去狀態(tài)是條件獨(dú)立的，即該過(guò)程是馬爾科夫過(guò)程，即具有馬爾科夫性質(zhì)。
e. 應(yīng)用與舉例
①泊松分布
在實(shí)際事例中，當(dāng)一個(gè)事件以固定的平均速率出現(xiàn)時(shí)隨機(jī)且獨(dú)立地出現(xiàn)時(shí)，那么這個(gè)時(shí)間在單位時(shí)間（面積或體積等）內(nèi)出現(xiàn)的次數(shù)或個(gè)數(shù)近似服從泊松分布。
如：
某醫(yī)院平均每小時(shí)出生3個(gè)嬰兒；（單位時(shí)間）
某公司平均每小時(shí)接到3.5個(gè)電話；（單位時(shí)間）
采用0.05J/m2紫外線照射大腸桿菌時(shí)，每個(gè)基因組平均產(chǎn)生3個(gè)嘧啶二體。（單位基因組）
②指數(shù)分布
指數(shù)分布表示兩次事件（服從泊松分布）發(fā)生間隔為t的概率。
可用來(lái)表示：
嬰兒出生的時(shí)間間隔；
服從泊松分布的服務(wù)的時(shí)間間隔；
③指數(shù)分布的無(wú)記憶性：
如果一個(gè)隨機(jī)變量服從指數(shù)分布，那么對(duì)于s,t>0，有P(T>t+s|T>t)=P(T>s)。
例如：若果某原件壽命為T，已知使用了t小時(shí)，那么它總共使用了s+t小時(shí)和其從開始起來(lái)使用s小時(shí)概率相同。
2.4.1 指數(shù)分布
下面我們討論指數(shù)分布的性質(zhì)與其在基礎(chǔ)排隊(duì)模型中的作用。
a. 單調(diào)性
b. 無(wú)記憶性
c. 幾個(gè)獨(dú)立的指數(shù)分布變量的最小者亦為指數(shù)分布
d. 泊松過(guò)程與指數(shù)分布
e. 不受聚合/離散的影響
03 常見(jiàn)模型 M/M/1 及 M/M/S
M/M/1 模型簡(jiǎn)單介紹
- 到達(dá)時(shí)間是泊松過(guò)程（Poisson process）；
- 服務(wù)時(shí)間是指數(shù)分布（exponentially distributed）；
- 只有一部服務(wù)器（server）
- 隊(duì)列長(zhǎng)度無(wú)限制
- 可加入隊(duì)列的人數(shù)為無(wú)限
這種模型是一種出生-死亡過(guò)程，此隨機(jī)過(guò)程中的每一個(gè)狀態(tài)代表模型中人數(shù)的數(shù)目。因?yàn)槟Ｐ偷年?duì)列長(zhǎng)度無(wú)限且參與人數(shù)亦無(wú)限，故此狀態(tài)數(shù)目亦為無(wú)限。例如狀態(tài)0表示模型閑置、狀態(tài)1表示模型有一人在接受服務(wù)、狀態(tài)2表示模型有二人（一人正接受服務(wù)、一人在等候），如此類推。 此模型中，出生率（即加入隊(duì)列的速率）λ在各狀態(tài)中均相同，死亡率（即完成服務(wù)離開隊(duì)列的速率）μ亦在各狀態(tài)中相同（除了狀態(tài)0，因其不可能有人離開隊(duì)列）。故此，在任何狀態(tài)下，只有兩種事情可能發(fā)生：
有人加入隊(duì)列。如果模型在狀態(tài)k，它會(huì)以速率λ進(jìn)入狀態(tài)k + 1
有人離開隊(duì)列。如果模型在狀態(tài)k（k不等于0），它會(huì)以速率μ進(jìn)入狀態(tài)k ? 1
由此可見(jiàn)，模型的隱定條件為λ < μ。如果死亡率小于出生率，則隊(duì)列中的平均人數(shù)為無(wú)限大，故此這種系統(tǒng)沒(méi)有平衡點(diǎn)。
對(duì)于M ／M ／1 模型有如下公式
μ: 單位時(shí)間服務(wù)的顧客數(shù)，平均( 期望) 服務(wù)率；
λ: 單位時(shí)間前來(lái)的顧客數(shù)。
Ls ：隊(duì)長(zhǎng) ，系統(tǒng)中的顧客數(shù)（n）期望值
Lq：排隊(duì)長(zhǎng) ，系統(tǒng)中排隊(duì)等待服務(wù)的顧客數(shù); 期望值記為L(zhǎng)q
Ws：逗留時(shí)間:—— 指一個(gè)顧客在系統(tǒng)中的全部停留時(shí)間 為 期望值，記為 Ws
Wq: 等待時(shí)間: —— 指一個(gè)顧客在系統(tǒng)中的排隊(duì)等待時(shí)間為 期望值，記為 Wq
Ws=Wq + E[ 服務(wù)時(shí)間]
s : 服務(wù)臺(tái)數(shù)目
服務(wù)強(qiáng)度：ρ = λ/sμ
M/M/1 模型例子
某醫(yī)院急診室同時(shí)只能診治一個(gè)病人，診治時(shí)間服從指數(shù)分布，每個(gè)病人平均需要 15 分鐘。病人按泊松分布到達(dá)，平均每小時(shí)到達(dá)3 3 人。試對(duì)此排隊(duì)隊(duì)系統(tǒng)進(jìn)行分析。
解： 對(duì)此排隊(duì)隊(duì)系統(tǒng)分析如下：
代碼：
結(jié)果
排隊(duì)等待的平均人數(shù)為 2.25人 系統(tǒng)內(nèi)的平均人數(shù)為 3.00人 平均逗留時(shí)間為60.00分鐘 平均等待時(shí)間為45.00分種3.1 為什么選擇這兩個(gè)模型
很簡(jiǎn)單，這兩個(gè)模型假設(shè)顧客抵達(dá)與服務(wù)時(shí)間為指數(shù)分布，時(shí)間流程為泊松過(guò)程，任何復(fù)雜隊(duì)列模型都是由他們衍生出來(lái)的…….由于篇幅受限，本文往后都會(huì)集中在這兩個(gè)基礎(chǔ)模型上。關(guān)于更多衍生參考模型，請(qǐng)參閱文末reference list.
3.2 生滅過(guò)程
The Birth-and-Death Process. 為了得出M/M/1 及 M/M/S的一般公式，筆者認(rèn)為有必要簡(jiǎn)單推導(dǎo)下…… 該模型為連續(xù)時(shí)間馬爾可夫過(guò)程(continuous time Markov chain)，要介紹全很困難，這里就給一個(gè)簡(jiǎn)易推導(dǎo)。
取決于兩個(gè)時(shí)間的長(zhǎng)短。
另，上述過(guò)程可有下圖來(lái)表示.
在穩(wěn)態(tài)隊(duì)列的情況下: 任何系統(tǒng)狀態(tài)的進(jìn)出速率應(yīng)該相當(dāng)。舉一個(gè)例子，系統(tǒng)在狀態(tài)0的情況下: 從狀態(tài)0轉(zhuǎn)移到狀態(tài)1(沒(méi)有顧客到一個(gè)顧客)時(shí)，離開與進(jìn)入相等:
通過(guò)迭代法計(jì)算(步驟省去，直接給結(jié)論):
以上為生滅原理下隊(duì)列模型的通用結(jié)論。
3.3 M/M/1 模型與 M/M/S 模型
3.3.1 M/M/1 模型
3.3.1.1 M/M/1/k 模型
3.3.2 M/M/S 模型
04 案例分析
這里我們給出一個(gè)小case study:
已知某生產(chǎn)線在執(zhí)行某項(xiàng)特殊高危高精度工藝時(shí)，有10臺(tái)機(jī)器共同運(yùn)作。由于人員配置緊張，該產(chǎn)線只安排的8名工人同時(shí)操作8臺(tái)機(jī)器，另外兩臺(tái)設(shè)備隨時(shí)standby為替補(bǔ)更改工裝/加工設(shè)備，工廠這樣安排的目的是為了保持滿負(fù)荷運(yùn)作。目前該工廠只安排了1名工人更改工裝與加工設(shè)備。
已知該工藝流設(shè)備平均每20天需要下線更改工裝，而更改工裝工人平均需2天的時(shí)間完成設(shè)備的重新設(shè)置。由于隊(duì)列等待現(xiàn)象，產(chǎn)線經(jīng)常出現(xiàn)不滿8臺(tái)生產(chǎn)的情況。目前管理層正在考率是否要再雇傭一名工人執(zhí)行機(jī)器下線操作。已知每個(gè)線下工人公司給的酬薪大約是每天280RMB，而每天由于產(chǎn)線未滿負(fù)荷運(yùn)作而產(chǎn)生的利潤(rùn)損失為每臺(tái)額外下線機(jī)器400RMB。你作為工業(yè)工程師被指派study這個(gè)問(wèn)題，請(qǐng)問(wèn)你會(huì)對(duì)管理層作出怎樣的決策推薦以求公司利潤(rùn)最大化？
首先我們用數(shù)學(xué)語(yǔ)言翻譯下上述條件:
所以我們可以計(jì)算出下表：
所以，通過(guò)排隊(duì)論模型分析，盡管公司添加工人的話產(chǎn)線能夠保持最大化利用，但是此時(shí)的運(yùn)營(yíng)成本大于只雇傭一名工人的情況，我們向管理層推薦的決策為不要雇傭第二個(gè)工人。
05 插一句話
5.1 文章總結(jié)
本文初步介紹了排隊(duì)論的理論發(fā)展歷史背景。并簡(jiǎn)單回顧了泊松過(guò)程與指數(shù)分布在廣義一般化排隊(duì)模型中的應(yīng)用必要性。又詳細(xì)地基于連續(xù)時(shí)間狀態(tài)馬爾可夫過(guò)程歸納出了M/M/1與M/M/S模型幾個(gè)基本結(jié)論并配以一個(gè)工業(yè)界地實(shí)際應(yīng)用案例分析。讀者應(yīng)該可以大致初步掌握排隊(duì)論的應(yīng)用范圍與方法。其他衍生模型，如非指數(shù)分布，混線，排隊(duì)網(wǎng)絡(luò)，隊(duì)列數(shù)量限制等，篇幅受限，不再贅述，感興趣地讀者可以翻閱文末的參考資料。
參考文獻(xiàn)
1.J.D.C. Little, “A Proof for the Queueing Formula: L=W”, Operations Research, 9(3):383-387, 1961.
2.“Introduction to Operation Research”, 7th edition, Hillier & Lieberman, McGraw-Hill.
3.“Elements of Queueing Theory, Palm Martingale Calculus and Stochastic Recurrences”, 2nd edition, Francois Baccelli, Pierre Bremaud, Springer.
4.“Fundamentals of Queueing Theory”, 4th edition, Donald Gross, John F. Shortle, James M. Thompson, Carl M. Harris, Wiley.
5.“Introduction to Probability Models”, 11th edition, Sheldon M. Ross.
6.“Stochastic Modelling and Optimization”, University of Toronto, Viliam Makis.
7.“Probability and Statistics for Engineers and Scientists”, 9th edition, Ronald E. Walpole, Raymond H. Myers, Sharon L. Myers, Keying Ye.
https://zhuanlan.zhihu.com/p/99131787
http://xiang-chen.github.io/2015/06/11/%E5%B8%B8%E8%A7%81%E6%A6%82%E7%8E%87%E5%88%86%E5%B8%83%E7%9A%84%E5%88%86%E5%B8%83%E5%87%BD%E6%95%B0-%E6%9C%9F%E6%9C%9B-%E6%96%B9%E5%B7%AE/
https://www.jianshu.com/p/c05bafb52877
https://blog.csdn.net/zyx_bx/article/details/115219706
https://blog.csdn.net/qq_39481214/article/details/82185050
https://blog.csdn.net/qq_29831163/article/details/89735320
總結(jié)
- 上一篇： 冰河木马学习之监听服务端失败
- 下一篇： 外行假装内行，我也来谈谈SAP BAPI