排隊論及其應用

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

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

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

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

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

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

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

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

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

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

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

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

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