排隊(duì)論及其應(yīng)用

1、排隊(duì)系統(tǒng)的符號表述描述符號：/ 各符號的意義： 表示顧客相繼到達(dá)間隔時間分布，常用下列符號： M表示到達(dá)的過程為泊松過程或負(fù)指數(shù)分布； D表示定長輸入； EK表示K階愛爾朗分布； G表示一般相互獨(dú)立的隨機(jī)分布。表示服務(wù)時間分布，所用符號與表示顧客到達(dá)間隔時間分布相同。表示服務(wù)臺(員)個數(shù)：“1”表示單個服務(wù)臺，“s”(s>1)表示多個服務(wù)臺。 表示系統(tǒng)中顧客容量限額，或稱等待空間容量。如系統(tǒng)有K個等待位子，則，0<K<，當(dāng)K=0時，說明系統(tǒng)不允許等待，即為損失制。K=時為等待制系統(tǒng)，此時一般省略不寫。K為有限整數(shù)時，表示為混合制系統(tǒng)。表示顧客源限額，分有限與無限兩種，表示顧客

2、源無限，一般也可省略不寫。表示服務(wù)規(guī)則，常用下列符號FCFS：表示先到先服務(wù)的排隊(duì)規(guī)則；LCFS：表示后到先服務(wù)的排隊(duì)規(guī)則；PR：表示優(yōu)先權(quán)服務(wù)的排隊(duì)規(guī)則。二、排隊(duì)系統(tǒng)的主要數(shù)量指標(biāo) 描述一個排隊(duì)系統(tǒng)運(yùn)行狀況的主要數(shù)量指標(biāo)有： 1隊(duì)長和排隊(duì)長(隊(duì)列長) 隊(duì)長是指系統(tǒng)中的顧客數(shù)(排隊(duì)等待的顧客數(shù)與正在接受服務(wù)的顧客數(shù)之和)；排隊(duì)長是指系統(tǒng)中正在排隊(duì)等待服務(wù)的顧客數(shù)。隊(duì)長和排隊(duì)長一般都是隨機(jī)變量。 2等待時間和逗留時間 從顧客到達(dá)時刻起到他開始接受服務(wù)止這段時間稱為等待時間。等待時間是個隨機(jī)變量。從顧客到達(dá)時刻起到他接受服務(wù)完成止這段時間稱為逗留時間，也是隨機(jī)變量。 3. 忙期和閑期 忙期是指從顧

3、客到達(dá)空閑著的服務(wù)機(jī)構(gòu)起，到服務(wù)機(jī)構(gòu)再次成為空閑止的這段時間，即服務(wù)機(jī)構(gòu)連續(xù)忙的時間。這是個隨機(jī)變量，是服務(wù)員最為關(guān)心的指標(biāo)，因?yàn)樗P(guān)系到服務(wù)員的服務(wù)強(qiáng)度。與忙期相對的是閑期,即服務(wù)機(jī)構(gòu)連續(xù)保持空閑的時間。在排隊(duì)系統(tǒng)中，忙期和閑期總是交替出現(xiàn)的。4數(shù)量指標(biāo)的常用記號 (1)主要數(shù)量指標(biāo)L平均隊(duì)長，即穩(wěn)態(tài)系統(tǒng)任一時刻的所有顧客數(shù) 的期望值；Lq平均等待隊(duì)長，即穩(wěn)態(tài)系統(tǒng)任一時刻等待服務(wù)的顧客數(shù)的期望值；W平均逗留時間，即(在任意時刻)進(jìn)入穩(wěn)態(tài)系統(tǒng)的顧客逗留時間的期望值；Wq平均等待時間，即(在任意時刻)進(jìn)入穩(wěn)態(tài)系統(tǒng)的顧客等待時間的期望值。(2)其他常用數(shù)量指標(biāo) s系統(tǒng)中并聯(lián)服務(wù)臺的數(shù)目； 平均到達(dá)

4、率；1平均到達(dá)間隔； 平均服務(wù)率；1/平均服務(wù)時間；N穩(wěn)態(tài)系統(tǒng)任一時刻的狀態(tài)（即系統(tǒng)中所有顧客數(shù)）；U任一顧客在穩(wěn)態(tài)系統(tǒng)中的逗留時間；Q任一顧客在穩(wěn)態(tài)系統(tǒng)中的等待時間；服務(wù)強(qiáng)度，即每個服務(wù)臺單位時間內(nèi)的平均服務(wù)時間，般有=(s)，這是衡量排隊(duì)系統(tǒng)繁忙程度的重要尺度，當(dāng)趨近于0時，表明對期望服務(wù)的數(shù)量來說，服務(wù)能力相對地說是很大的。這時，等待時間一定很短，服務(wù)臺有大量的空閑時間；如服務(wù)強(qiáng)度趨近于1，那么服務(wù)臺空閑時間較少而顧客等待時間較多。我們一般都假定平均服務(wù)率大于平均到達(dá)率，即/<1,否則排隊(duì)的人數(shù)會越來越多，以后總是保持這個假設(shè)而不再聲明。李特爾公式 在系統(tǒng)達(dá)到穩(wěn)態(tài)時，假定平均到達(dá)率

5、為常數(shù)，平均服務(wù)時間為常數(shù)1/，則有下面的李特爾公式： L= W Lq= Wq W= Wq +1/ L= Lq +/排隊(duì)系統(tǒng)運(yùn)行情況的分析 排隊(duì)系統(tǒng)運(yùn)行情況的分析，就是在給定輸入與服務(wù)條件下，通過求解系統(tǒng)狀態(tài)為n(有n個顧客)的概率Pn，再進(jìn)行計算其主要的運(yùn)行指標(biāo)： 系統(tǒng)中顧客數(shù)(隊(duì)長)的期望值L； 排隊(duì)等待的顧客數(shù)(排隊(duì)長)的期望值Lq； 顧客在系統(tǒng)中全部時間(逗留時間)的期望值W； 顧客排隊(duì)等待時間的期望值Wq。第三節(jié) MM1模型模型的條件是：1、輸入過程顧客源是無限的，顧客到達(dá)完全是隨機(jī)的，單個到來，到達(dá)過程服從普阿松分布，且是平穩(wěn)的；2、排隊(duì)規(guī)則單隊(duì)，且隊(duì)長沒有限制，先到先服務(wù)；3、服

6、務(wù)機(jī)構(gòu)單服務(wù)臺，服務(wù)時間的長短是隨機(jī)的，服從相同的指數(shù)分布 。第四節(jié)      M / M / S 模型l 此模型與M/M/1模型不同之處在于有S個服務(wù)臺，各服務(wù)臺的工作相互獨(dú)立，服務(wù)率相等，如果顧客到達(dá)時，S個服務(wù)臺都忙著，則排成一隊(duì)等待，先到先服務(wù)的單隊(duì)模型。l 整個系統(tǒng)的平均服務(wù)率為s，*/s，（*<1）為該系統(tǒng)的服務(wù)強(qiáng)度。幾個連續(xù)型分布定長l 定長分布（記為D）若顧客到達(dá)間隔時間（或服務(wù)時間）為一常量a，此時稱輸入（服務(wù)）分布為定長分布，用T表示此時間，則P(T=a) = 1用分布函數(shù)表示有F(t) = P(T£t) =

7、 0 t<a 1 t³al 概率特征：方差為0l 主要應(yīng)用： 周期性到達(dá)事件 定長服務(wù)系統(tǒng)（例如ATM網(wǎng)絡(luò)）幾個連續(xù)型分布負(fù)指數(shù)幾個連續(xù)型分布負(fù)指數(shù)l 無記憶性 P(T>t+x| T>t) = P(T>x)l 定理1.1負(fù)指數(shù)分布具有無記憶性.即設(shè)T是隨機(jī)變量,服從負(fù)指數(shù)分布,參數(shù)為l >0,設(shè)t,x>0,則P(T>t +x| T>t) = P(T>x) = e-lxl 定理1.2設(shè)隨機(jī)變量T是非負(fù)的連續(xù)型變量，它的分布具有無記憶性，則T服從負(fù)指數(shù)分布l 連續(xù)型隨機(jī)變量分布中，只有負(fù)指數(shù)分布具有無記憶特性幾個連續(xù)型分布愛爾蘭l 定

8、理1.3 愛爾蘭分布和負(fù)指數(shù)分布的關(guān)系 設(shè)T1,T2,Tk,是獨(dú)立同負(fù)指數(shù)分布的隨機(jī)變量，參數(shù)為l，則 T =T1+T2+Tk,服從 k 階愛爾蘭分布l 主要應(yīng)用 描述多級服務(wù)系統(tǒng) 描述平滑（規(guī)則）隨機(jī)事件流 幾個離散型分布l 離散時間的排隊(duì)理論在計算機(jī)通訊中有著廣泛的應(yīng)用。因?yàn)闄C(jī)械動作是間斷的，用離散理論可以得到更精確的結(jié)果。l 排隊(duì)論中常用的最重要的離散分布是幾何分布和負(fù)二項(xiàng)分布，實(shí)際上可以把它們看作是負(fù)指數(shù)分布、愛爾蘭分布離散化而得到的分布，因此它們也應(yīng)具有負(fù)指數(shù)分布、愛爾蘭分布的類似性質(zhì)。 幾個離散型分布幾何l 幾何分布可以用來描述某一顧客的到達(dá)間隔或服務(wù)持續(xù)時間 每單位時間執(zhí)行一次貝

9、努力試驗(yàn)，“失敗”則繼續(xù)，成功則完成 首次“成功”之前需要持續(xù)的時間就可以看成是相應(yīng)的到達(dá)間隔或服務(wù)持續(xù)時間幾個離散型分布幾何l 定理1.4幾何分布具有無記憶性，即P(T>n+m | T>n)=P(T>m)或P( T=n+m | T>n )=P( T=m )l 定理1.5在離散型分布中，幾何分布是唯一具有無記憶性的分布 幾個離散型分布負(fù)二項(xiàng)l 定理1.5負(fù)二項(xiàng)分布與幾何分布的關(guān)系設(shè)T1，T2，Tk是獨(dú)立同幾何分布的離散型隨機(jī)變量，則T=T1+T2+Tk服從負(fù)二項(xiàng)分布 （參數(shù)為k）二項(xiàng)分布二項(xiàng)分布即重復(fù)n次獨(dú)立的伯努利試驗(yàn)。在每次試驗(yàn)中只有兩種可能的結(jié)果，而且兩種結(jié)果發(fā)生

10、與否互相對立，并且相互獨(dú)立，與其它各次試驗(yàn)結(jié)果無關(guān)，事件發(fā)生與否的概率在每一次獨(dú)立試驗(yàn)中都保持不變，則這一系列試驗(yàn)總稱為n重伯努利實(shí)驗(yàn)，當(dāng)試驗(yàn)次數(shù)為1時，二項(xiàng)分布就是伯努利分布。2概念二項(xiàng)分布（Binomial Distribution），即重復(fù)n次的伯努利試驗(yàn)（Bernoulli Experiment），用表示隨機(jī)試驗(yàn)的結(jié)果。 二項(xiàng)分布公式如果事件發(fā)生的概率是P,則不發(fā)生的概率q=1-p，N次獨(dú)立重復(fù)試驗(yàn)中發(fā)生K次的概率是應(yīng)用條件1各觀察單位只能具有相互對立的一種結(jié)果，如陽性或陰性，生存或死亡等，屬于兩分類資料。2已知發(fā)生某一結(jié)果（陽性）的概率為，其對立結(jié)果的概率為1-，實(shí)際工作中要求是從大

11、量觀察中獲得比較穩(wěn)定的數(shù)值。二項(xiàng)分布公式3n次試驗(yàn)在相同條件下進(jìn)行，且各個觀察單位的觀察結(jié)果相互獨(dú)立，即每個觀察單位的觀察結(jié)果不會影響到其他觀察單位的結(jié)果。如要求疾病無傳染性、無家族性等。泊松分布1命名原因泊松分布實(shí)例泊松分布（Poisson distribution），臺譯卜瓦松分布，是一種統(tǒng)計與概率學(xué)里常見到的離散機(jī)率分布（discrete probability distribution）。泊松分布是以1819 世紀(jì)的法國數(shù)學(xué)家西莫恩·德尼·泊松（Siméon-Denis Poisson）命名的，他在1838年時發(fā)表。但是這個分布卻在更早些時候由貝努里家族的

12、一個人描述過。就像當(dāng)代科學(xué)史專家斯蒂芬·施蒂格勒（Stephen Stigler）所說的誤稱定律（the Law of Misonomy），數(shù)學(xué)中根本沒有以其發(fā)明者命名的東西。2分布特點(diǎn)泊松分布的概率函數(shù)為：泊松分布的參數(shù)是單位時間(或單位面積)內(nèi)隨機(jī)事件的平均發(fā)生率。 泊松分布適合于描述單位時間內(nèi)隨機(jī)事件發(fā)生的次數(shù)。泊松分布的期望和方差均為 特征函數(shù)為 3關(guān)系泊松分布與二項(xiàng)分布泊松分布當(dāng)二項(xiàng)分布的n很大而p很小時，泊松分布可作為二項(xiàng)分布的近似，其中為np。通常當(dāng)n10,p0.1時，就可以用泊松公式近似得計算。事實(shí)上，泊松分布正是由二項(xiàng)分布推導(dǎo)而來的，具體推導(dǎo)過程參見本詞條相關(guān)部分。

13、4應(yīng)用場景在實(shí)際事例中，當(dāng)一個隨機(jī)事件，例如某電話交換臺收到的呼叫、來到某公共汽車站的乘客、某放射性物質(zhì)發(fā)射出的粒子、顯微鏡下某區(qū)域中的白血球等等，以固定的平均瞬時速率（或稱密度）隨機(jī)且獨(dú)立地出現(xiàn)時，那么這個事件在單位時間（面積或體積）內(nèi)出現(xiàn)的次數(shù)或個數(shù)就近似地服從泊松分布P()。因此,泊松分布在管理科學(xué)、運(yùn)籌學(xué)以及自然科學(xué)的某些問題中都占有重要的地位。5應(yīng)用示例泊松分布適合于描述單位時間（或空間）內(nèi)隨機(jī)事件發(fā)生的次數(shù)。如某一服務(wù)設(shè)施在一定時間內(nèi)到達(dá)的人數(shù)，電話交換機(jī)接到呼叫的次數(shù)，汽車站臺的候客人數(shù)，機(jī)器出現(xiàn)的故障數(shù)，自然災(zāi)害發(fā)生的次數(shù)，一塊產(chǎn)品上的缺陷數(shù)，顯微鏡下單位分區(qū)內(nèi)的細(xì)菌分布數(shù)等等。1 觀察事物平均發(fā)生m次的條件下，實(shí)際發(fā)生x次的概率P（x）可用下式表示：稱為泊松分布。例如采用0.05J/紫外線照射大腸桿菌時，每個基因組（4×106核苷酸對）平均產(chǎn)生3個嘧啶二體。實(shí)際上每個基因