運籌學(xué)——7.約束極值問題.ppt

1 第十二章排隊論 2 一 排隊系統(tǒng)的一般表示 例1各個顧客由顧客源出發(fā) 到達服務(wù)機構(gòu)前排隊等候服務(wù) 服務(wù)完了后就離開 排隊結(jié)構(gòu)指隊列的數(shù)目和排列方式 排隊規(guī)則和服務(wù)規(guī)則是說明顧客在排隊系統(tǒng)中按怎樣的規(guī)則 次序接受服務(wù)的 排隊規(guī)則 排隊系統(tǒng) 第一節(jié)基本概念 3 現(xiàn)實生活中的排隊系統(tǒng) 4 二 排隊系統(tǒng)的組成和特征 輸入即指顧客到達排隊系統(tǒng) 可能有以下不同情況 1 輸入過程 5 2 排隊規(guī)則 顧客在排隊系統(tǒng)中按怎樣的規(guī)則 次序接受服務(wù)的 1 顧客到達時 所有服務(wù)臺被占用 6 3 服務(wù)機構(gòu) 2 多服務(wù)臺時 單隊 單服務(wù)臺 多隊 多服務(wù)臺 并列 單隊 多服務(wù)臺 并列 7 5 服務(wù)時間的分布我們總假定是平穩(wěn)的 即分布的期望值 方差等參數(shù)都不受時間的影響 多服務(wù)臺 串列 多服務(wù)臺混合 8 三 排隊模型的分類 1 1953年 D G Kendall提出第一種分類方法 X Y Z X處填寫表示相繼到達間隔時間的分布 Y處填寫表示服務(wù)時間的分布 Z處填寫并列的服務(wù)臺的數(shù)目 表示相繼到達間隔時間和服務(wù)時間的各種分布的符號 M 負指數(shù)分布 D 確定型 Ek k階愛爾朗分布 GI 一般相互獨立的時間間隔的分布 G 一般服務(wù)時間的分布 9 2 1971年關(guān)于排隊論符號的標準化會議上決定 將Kendall符號擴展成為 X Y Z A B C 前三項意義不變 而 A處填寫系統(tǒng)容量限制N B處填寫顧客源數(shù)m C處填寫服務(wù)規(guī)則 約定 10 四 排隊系統(tǒng)的參數(shù) 1 隊長 Ls 指在系統(tǒng)中的顧客數(shù) 2 排隊長 Lq 指系統(tǒng)中排隊等候服務(wù)的顧客數(shù) 3 逗留時間 Ws 指一個顧客在系統(tǒng)中的停留時間 4 等待時間 Wq 指一個顧客在系統(tǒng)中排隊等待的時間 Ls Lq 正被服務(wù)的顧客數(shù) Ws Wq 服務(wù)時間 5 忙期 指從顧客到達空閑服務(wù)機構(gòu)起到服務(wù)機構(gòu)再次空閑止這段時間長度 即服務(wù)機構(gòu)連續(xù)繁忙的時間長度 6 系統(tǒng)的狀態(tài)概率 Pn t 指系統(tǒng)中的顧客數(shù)為n的概率 7 穩(wěn)定狀態(tài) limPn t Pn 11 一 經(jīng)驗分布 例2某服務(wù)機構(gòu)單服務(wù)臺 先到先服務(wù) 對41顧客記錄到達時刻 和服務(wù)時間s 單位 分鐘 如下表 表中第1號顧客到達時刻為0 全部服務(wù)時間為127 分鐘 第二節(jié)時間分布 12 13 到達間隔分布表 服務(wù)時間分布表 平均間隔時間 142 40 3 55 分鐘 人 平均到達率 41 142 0 28 人 分鐘 平均服務(wù)率 41 127 0 32 人 分鐘 平均服務(wù)時間 127 41 3 12 分鐘 人 14 二 Passion分布 設(shè)N t 表示在時間 0 t 內(nèi)到達顧客數(shù) 令Pn t1 t2 表示在時間區(qū)間 t1 t2 t2 t1 內(nèi)有n 0 個顧客到達的概率 即 Pn t1 t2 P N t2 N t1 n t2 t1 n 0 Passion分布的三條件 1 無后效性 不相重疊的時間區(qū)間內(nèi)顧客到達數(shù)相互獨立 15 Pn t t Pn t 1 t o t Pn 1 t t o t 在上述條件下 研究顧客到達數(shù)n的概率分布 16 Pn t t Pn t 1 t Pn 1 t t o t Pn t t Pn t t Pn t Pn 1 t o t t 令 t 0 P0 t e t Pn t t ne t n t 0 n 0 1 2 17 三 負指數(shù)分布 18 一 M M 1模型 1 假設(shè) 第三節(jié)單服務(wù)臺負指數(shù)分布排隊系統(tǒng)的分析 19 2 Pn的計算 O表示發(fā)生 1個 表示沒有發(fā)生 Pn t t Pn t 1 t 1 t Pn 1 t 1 t t Pn 1 t t 1 t Pn t t t 20 整理得 Pn t t Pn t 1 t t Pn 1 t t Pn 1 t t o t Pn t t Pn t t Pn 1 t Pn 1 t Pn t 1 t 0 dPn t dt Pn 1 t Pn 1 t Pn t 考慮P0 t 的情況 P0 t t P0 t 1 t P1 t 1 t t t 0 dP0 t dt P0 t P1 t 2 由dPn t dt 0得到 21 由式 3 得 通過求解可得 單位時間內(nèi)到達的平均顧客數(shù) 單位時間內(nèi)服務(wù)的平均顧客數(shù) 服務(wù)強度 參數(shù)意義 22 3 M M 1參數(shù)計算 1 系統(tǒng)中平均顧客數(shù) Ls 記 23 2 隊列中等待的平均顧客數(shù) Lq 3 顧客逗留時間 Ws 4 隊列中顧客等待時間 Wq 24 它們的相互關(guān)系如下 25 例3100個工作小時內(nèi)每小時來就診的病人數(shù)n出現(xiàn)次數(shù)如下 100個完成手術(shù)的病例所用時間v 小時 出現(xiàn)的次數(shù)如下 26 解 27 假定系統(tǒng)最大容量為N 單服務(wù)臺情形排隊等待的顧客最多為N 1 下面只考慮穩(wěn)態(tài)情形 二 M M 1 N 模型 解得 28 根據(jù)上式我們可以推導(dǎo)出系統(tǒng)的各項指標 有效到達率 e 1 PN 可以驗證 1 P0 e 4 顧客等待時間 3 顧客逗留時間 1 隊長 2 隊列長 29 例4單人理發(fā)館有六個椅子接待客人 當(dāng)6個椅子都坐滿時 后來的顧客不進店就離開 顧客平均到達率為3人 小時 理發(fā)需時平均15分鐘 則 N 7為系統(tǒng)中最大的顧客數(shù) 3人 小時 4人 小時 1 求某顧客一到達就能理發(fā)的概率 2 求需要等待的顧客數(shù)的期望值 30 3 求有效到達率 4 求一顧客在理發(fā)館內(nèi)逗留的時間 5 在可能到達的顧客中有百分之幾不等待就離開 人 小時 31 機器故障問題 設(shè)共有m臺機器 機器故障停機表示到達 待修機器形成隊列 修理工是服務(wù)員 顧客總體雖然只有m個 但每個顧客服務(wù)后仍回到總體 仍然可以到來 三 顧客源為有限的情形 M M 1 m 32 根據(jù)上式我們可以推導(dǎo)出系統(tǒng)的各項指標 在機器故障問題中Ls就是平均故障臺數(shù) 而 33 例5某車間有5臺機器 每臺機器的連續(xù)運轉(zhuǎn)時間服從負指數(shù)分布 平均連續(xù)運轉(zhuǎn)時間15分鐘 有一個修理工 每次修理時間服從負指數(shù)分布 平均每次12分鐘 求 1 修理工空閑的概率 2 五臺機器都出故障的概率 3 出故障的平均臺數(shù) 4 等待修理的臺數(shù) 5 平均停工時間 6 平均等待時間 7 評價這些結(jié)果 34 解 7 機器停工時間過長 修理工幾乎沒有空閑時間 應(yīng)當(dāng)提高服務(wù)率減少修理時間或增加修理工人 35 一 M M c 第四節(jié)多服務(wù)臺指數(shù)分布排隊系統(tǒng)的分析 36 用遞推法解上述差分方程 可求得狀態(tài)概率 根據(jù)上式我們可以推導(dǎo)出系統(tǒng)的各項指標 37 例6某售票所有三個窗口 顧客到達服從Passion過程 平均到達率每分鐘 0 9 人 服務(wù) 售票 時間服從負指數(shù)分布 平均服務(wù)率每分鐘 0 4 人 0 9 38 代入公式得 1 整個售票所空閑的概率 2 平均隊長 3 平均等待時間和逗留時間 4 顧客到達后必須等待 即系統(tǒng)中顧客數(shù)已有3人 的概率 39 M M c型系統(tǒng)和c個M M 1系統(tǒng)的比較 上例中 排隊方式不變 但顧客到達后在每個窗口前各排一隊 且進入隊列后堅持不換 這就形成3個隊列 如下圖二每個隊列平均到達率為 0 9 3 0 3 每分鐘 這樣原來的系統(tǒng)就變成3個M M 1型的子系統(tǒng) 40 現(xiàn)按M M 1型解決這個問題 并與上表比較 從表中各指標的對比可以看出單隊比三隊有顯著的優(yōu)越性 41 系統(tǒng)的狀態(tài)概率和運行指標如下 二 M M c N 42 三 M M c m 2 平均故障臺數(shù) 有效到達率 43 1 等待修理的機器平均數(shù) 2 需要修理的機器平均數(shù) 3 有效損壞數(shù) 4 等待修理時間 5 停工時間 例7設(shè)有兩個修理工人 負責(zé)5臺機器的正常運行 每臺機器平均損壞的概率為每運轉(zhuǎn)一小時1次 兩個工人能以相同的平均修復(fù)率4 次 小時 修好機器 求 44 1 Lq P3 2P4 3P5 0 118 3 e 1 5 1 094 3 906 4 Wq 0 118 3 906 0 03小時 5 Ws 1 094 3 906 0 28小時 45 服務(wù)時間是任意分布的情形 一 M G 1 服務(wù)時間T的分布是一般的其它的條件和標準的M M 1型相同 為了達到穩(wěn)態(tài) 1這一條件是必要的 其中 E T 第五節(jié)一般服務(wù)時間M G 1模型 46 例8有一售票口 已知顧客按平均為2分30秒的時間間隔的負指數(shù)分布到達 顧客在售票口前服務(wù)時間平均為2分鐘 1 若服務(wù)時間也服從負指數(shù)分布 求顧客為購票所需的平均逗留時間和等待時間 2 若經(jīng)過調(diào)查 顧客在售票口前至少要占用1分鐘 且認為服從服務(wù)時間服從負指數(shù)分布是不恰當(dāng)?shù)?而應(yīng)服從以下概率密度分布 47 2 令y為服務(wù)時間 那么Y 1 X X服從均值為1的負指數(shù)分布 于是 48 二 M D 1 服務(wù)時間是確定的常數(shù) 例如在一條裝配線上完成一件工作的時間應(yīng)是常數(shù) 自動的汽車的沖洗臺 沖洗一臺汽車的時間也是常數(shù) 這時 例9某實驗室有一臺自動檢驗機器性能的儀器 要求檢驗機器的顧客按Passion分布到達 每小時平均4個顧客 檢驗每臺機器所需時間為6分鐘 求 1 在檢驗室內(nèi)機器臺數(shù)Ls 期望值 2 等候檢驗的機器臺數(shù)Lq 3 每臺機器在室內(nèi)消耗 逗留 時間Ws 4 每臺機器平均等待檢驗的時間Wq 49 注 在一般服務(wù)時間分布的Lq和Wq中以定長服務(wù)時間的為最小 這符合我們通常的理解 服務(wù)時間越有規(guī)律 等候的時間就越短 50 三 M Ek 1模型 51 對于M Ek 1模型 除服務(wù)時間外 其它條件與標準的M M 1型相同 52 例10某單人裁縫店做西服 每套需經(jīng)過4個不同的工序 4個工序完成后才開始另一套 每一套工序的時間服從負指數(shù)分布 期望值為2小時 顧客到來服從Passion分布 平均訂貨率為5 5套 周 設(shè)一周6天 每天8小時 以顧客為等到做好一套西服期望時間有多少 解顧客到達 5 5套 周 設(shè) 為平均服務(wù)率 單位時間完成的套數(shù) 1 為平