【正文】 運 籌 帷 幄 之 中 決 勝 千 里 之 外 運 籌 學(xué) 課 件 排 隊 論 Queueing Theory 一般的排隊過程為：顧客由顧客源出發(fā)，到達服務(wù)機構(gòu)（服務(wù)臺、服務(wù)員）前，按排隊規(guī)則排隊等待接受服務(wù)，服務(wù)機構(gòu)按服務(wù)規(guī)則給顧客服務(wù)，顧客接受完服務(wù)后就離開。排隊過程的一般 過程 可用下圖表示。我們所說的排隊系統(tǒng)是指圖中虛線所包括的部分 。 顧客源 排隊 服務(wù)機構(gòu)顧客到來排隊規(guī)則 服務(wù)規(guī)則顧客離去 在現(xiàn)實生活中的排隊現(xiàn)象是多種多樣的，對上面所說的 “ 顧客 ” 和 “ 服務(wù)員 ” 要作廣泛的理解。它們可以是人，也可以是某種物質(zhì)或設(shè)備。排隊可以是有形的，也可以是無形的。 基本概念 排隊過程的一般表示 排隊系統(tǒng)的組成和特征 盡管排隊系統(tǒng)是多種多樣的，但從決定排隊系統(tǒng)進程的因素來看，它有三個基本的組成部分，這就是 輸入過程、 排隊規(guī)則 及 服務(wù)機構(gòu) 。 1)輸入過程：描述顧客來源以及顧客到達排隊系統(tǒng)的規(guī)律。包括： 顧客源中顧客的數(shù)量是有限還是無限； 顧客到達的方式是單個到達還是成批到達； 顧客相繼到達的間隔時間分布是確定型的還是隨機型的，分布參數(shù)是什么，是否獨立，是否平穩(wěn)。 2)排隊規(guī)則： 描述顧客排隊等待的隊列和接受服務(wù)的次序。包括： 即時制還是等待制； 等待制下隊列的 情況（ 是單列還是多列，顧客能不能中途退出，多列時各列間的顧客能不能相互轉(zhuǎn)移）； 等待制下顧客接受服務(wù)的次序（先到先服務(wù)，后到先服務(wù)，隨機服務(wù)，有優(yōu)先權(quán)的服務(wù)）。 3)服務(wù)機構(gòu)：描述服務(wù)臺 (員 )的機構(gòu)形式和工作情況。包括： 服務(wù)臺（員）的數(shù)目和排列情況； 服務(wù)臺（員）的服務(wù)方式； 服務(wù)時間是確定型的還是隨機型的，分布參數(shù)是什么，是否獨立，是否平穩(wěn)。 排隊模型的分類 1953年提出了一個分類方法，按照系統(tǒng)的三個最主要的、影響最大的三個特征要素進行分類，它們是：顧客相繼到達的間隔時間分布、服務(wù)時間的分布、并列的服務(wù)臺個數(shù)。按照這三個特征要素分類的排隊系統(tǒng)，用符號（稱為 Kendall記號）表示為 X/Y/Z 其中 X處填寫顧客相繼到達的間隔時間分布， Y處填寫服務(wù)時間的分布， Z處填寫并列的服務(wù)臺個數(shù)。 例如 M/M/1， 表示顧客相繼到達的間隔時間為負指數(shù)分布、服務(wù)時間為負指數(shù)分布、單服務(wù)臺的模型。 后來，在 1971年關(guān)于排隊論符號標準化的會議上決定，將 Kendall符號擴充為： X/Y/Z/A/B/C 其中前三項意義不變 。 A處填寫系統(tǒng)容量限制 。 B處填寫顧客源中的顧客數(shù)目 。 C處填寫服務(wù)規(guī)則（如先到先服務(wù) FCFS， 后到先服務(wù) LCFS）。 約定，如略去后三項，即指 X/Y/Z/∞/∞/FCFS 的情形。 后面我們只討論先到先服務(wù) FCFS的情形，所以略去第六項 。 排隊系統(tǒng)的求解 對于一個排隊系統(tǒng)，運行狀況的好壞既涉及到顧客的利益，又涉及到服務(wù)機構(gòu)的利益，還有社會效果好壞的問題。為了研究排隊系統(tǒng)運行的效率、估計服務(wù)質(zhì)量、研究設(shè)計改進措施，必須確定一些基本指標，用以判斷系統(tǒng)運行狀況的優(yōu)劣。下面介紹幾種常用的指標。 1)隊長：把系統(tǒng)中的顧客數(shù)稱為 隊長 ，它的期望值記作 Ls。 而把系統(tǒng)中排隊等待服務(wù)的顧客數(shù)稱為 排隊長（隊列長） ，它的期望值記作 Lq。 顯然 有 隊長＝排隊長＋正被服務(wù)的顧客數(shù)。 2)逗留時間： 一個 顧客從到達排隊系統(tǒng)到服務(wù)完畢離去的總停留時間稱為 逗留時間 ，它的期望值記作Ws。 一個 顧客在系統(tǒng)中排隊等待的時間稱為 等待時間 ，它的期望值記作 Wq。 顯然 有 逗留時間＝等待時間＋服務(wù)時間。 3)瞬態(tài)和穩(wěn)態(tài) 把系統(tǒng)中的顧客數(shù)稱為系統(tǒng)的 狀態(tài) 。 考慮在 t時刻系統(tǒng)的狀態(tài)為 n的概率，它是隨時刻 t而變化的，用Pn(t)表示，稱為系統(tǒng)的 瞬態(tài) 。求瞬態(tài)解是很不容易的，一般即使求出也很難利用，因此我們常用它的極限 lim Pn(t)＝ Pn t→∞ 稱為 穩(wěn)態(tài)或稱統(tǒng)計平衡狀態(tài)的解 。 統(tǒng)計平穩(wěn)條件下的記號 ?n = 系統(tǒng)有 n個顧客時的平均到達率（單位時間平均到達的顧客人數(shù)即是平均到達率） ?n = 系統(tǒng)有 n個顧客時的平均離開率 ? = 對任何 n都是常數(shù)的平均到達率 . ? = 對任何 n都是常數(shù)的平均 離開 率 . 1/? = 期望到達間隔時間 1/? = 期望服務(wù)時間 ? = 服務(wù)強度， 或稱使用因子 , ?/(s?) 統(tǒng)計平穩(wěn)條件下的記號 qLqW平均隊長 平均等待隊長 平均等待時間 平均逗留時間 sLsWLs, Ws, Lq, Wq滿足 ?1?? qs WWss WL ??qq WL ??公式 Little ? ? ? ? ???? qs LL 將前兩式帶入后式得????0 nns nPL又因為??????1)( snnq PsnL所以，只需要求出 Pn即可。 幾個主要概率分布 一、 POISSON分布 設(shè) N(t)表示在時間區(qū)間 [t0,t0+t)內(nèi)到達的顧客數(shù)，是隨機變量。當 N(t)滿足下列三個條件時，我們說顧客的到達符合Poisson分布。這三個條件是： (1)平穩(wěn)性 在時間區(qū)間 [t0,t0+t)內(nèi)到達的顧客數(shù) N(t)， 只與區(qū)間長度 t有關(guān)而與時間起點 t0無關(guān)。 (2)無后效性 在時間區(qū)間 [t0,t0+t)內(nèi)到達的顧客數(shù) N(t)，與 t0以前到達的顧客數(shù)獨立。 (3)普通性 在充分短的時間區(qū)間 Δ t內(nèi)，到達兩個或兩個以上顧客的概率極小，可以忽略不計，即 ∞ ∑ Pn(Δ t)＝ o(Δ t) n=2 在上述三個條件下可以推出 (λ t)n Pn(t)＝ ——— eλ t n=0,1,2,…… n! 其中 λ 表示單位時間平均到達的顧客數(shù)， 即 為到達率。 不難算出， N(t)的數(shù)學(xué)期望和方差分別是： E[N(t)]＝ λ t Var[N(t)]＝ λ t 二、負指數(shù)分布 隨機變量 T的概率密度若是 λ eλ t t≥0 fT(t)＝ 0 t?0 則稱 T服從負指數(shù)分布，它的分布函數(shù)是 1eλ t t≥0 FT(t)＝ 0 t?0 T的數(shù)學(xué)期望和方差分別為： E[T]＝ 1/λ ， Var(T)＝ 1/λ 2 負指數(shù)分布具有下列性質(zhì)： (1)無記憶性或馬爾柯夫性，即 P{Tt+s / Ts}＝ P{Tt} (2)當顧