第十四章排隊(duì)論的基本知識(shí)ppt課件

1、運(yùn)籌學(xué)排隊(duì)論研究的內(nèi)容排隊(duì)論研究的內(nèi)容性態(tài)問題性態(tài)問題: 排隊(duì)系統(tǒng)的概率規(guī)律排隊(duì)系統(tǒng)的概率規(guī)律, 如隊(duì)長(zhǎng)分如隊(duì)長(zhǎng)分布布, 等待時(shí)間分布等等待時(shí)間分布等.最優(yōu)化問題最優(yōu)化問題: 排隊(duì)系統(tǒng)的最優(yōu)設(shè)計(jì)排隊(duì)系統(tǒng)的最優(yōu)設(shè)計(jì).統(tǒng)計(jì)推斷統(tǒng)計(jì)推斷: 判定排隊(duì)系統(tǒng)的類型判定排隊(duì)系統(tǒng)的類型.顧客源顧客源排隊(duì)系統(tǒng)排隊(duì)系統(tǒng)排隊(duì)結(jié)構(gòu)排隊(duì)結(jié)構(gòu)效勞效勞機(jī)構(gòu)機(jī)構(gòu)排隊(duì)規(guī)則服務(wù)規(guī)則服務(wù)規(guī)則接受服務(wù)接受服務(wù)后離去后離去服務(wù)臺(tái)服務(wù)臺(tái)(a) (a) 一個(gè)隊(duì)列、單服務(wù)臺(tái)階段）一個(gè)隊(duì)列、單服務(wù)臺(tái)階段）服務(wù)臺(tái)服務(wù)臺(tái)1服務(wù)臺(tái)服務(wù)臺(tái)2(b) (b) 一個(gè)隊(duì)列、一個(gè)隊(duì)列、s s個(gè)服務(wù)階段個(gè)服務(wù)階段服務(wù)臺(tái)服務(wù)臺(tái)1服務(wù)臺(tái)服務(wù)臺(tái)2(c) (c) 一個(gè)隊(duì)

2、列、一個(gè)隊(duì)列、s s個(gè)服務(wù)臺(tái)個(gè)服務(wù)臺(tái) 一個(gè)服務(wù)階段一個(gè)服務(wù)階段服務(wù)臺(tái)服務(wù)臺(tái)3服務(wù)臺(tái)服務(wù)臺(tái)4服務(wù)臺(tái)服務(wù)臺(tái)1服務(wù)臺(tái)服務(wù)臺(tái)2(d) s(d) s個(gè)隊(duì)列、個(gè)隊(duì)列、s s個(gè)服務(wù)階段個(gè)服務(wù)階段服務(wù)臺(tái)服務(wù)臺(tái)3服務(wù)臺(tái)服務(wù)臺(tái)4服務(wù)臺(tái)服務(wù)臺(tái)1服務(wù)臺(tái)服務(wù)臺(tái)2: 124: 243: 3214(e)(e)混合型混合型服務(wù)臺(tái)服務(wù)臺(tái)(f) (f) 一個(gè)隊(duì)列一個(gè)隊(duì)列服務(wù)臺(tái)服務(wù)臺(tái)(g) s(g) s個(gè)隊(duì)列個(gè)隊(duì)列運(yùn)籌學(xué)F1. 輸入過程輸入過程F顧客總體顧客總體:有限有限,無限無限.F顧客到達(dá)方式顧客到達(dá)方式:單個(gè)單個(gè),成批成批.F顧客到達(dá)間隔時(shí)間顧客到達(dá)間隔時(shí)間: 確定的、確定的、 隨機(jī)的隨機(jī)的.F顧客到達(dá)的獨(dú)立性顧客到達(dá)的獨(dú)立

3、性: 獨(dú)立獨(dú)立,不獨(dú)立不獨(dú)立. F輸入過程的平穩(wěn)性輸入過程的平穩(wěn)性: 與時(shí)間無關(guān)與時(shí)間無關(guān)(平穩(wěn)的平穩(wěn)的), 與時(shí)間有關(guān)與時(shí)間有關(guān)(非平穩(wěn)的非平穩(wěn)的).運(yùn)籌學(xué)顧客到達(dá)時(shí)間間隔的分布顧客到達(dá)時(shí)間間隔的分布:nT：第：第n n個(gè)顧客到達(dá)的時(shí)刻；個(gè)顧客到達(dá)的時(shí)刻；設(shè)設(shè)nTTT100：第：第n n個(gè)顧客與第個(gè)顧客與第n-1n-1個(gè)顧客到達(dá)的時(shí)間間隔；個(gè)顧客到達(dá)的時(shí)間間隔；nX, 2 , 1,1nTTXnnn令令1T2TnT1nT1nT0TnX運(yùn)籌學(xué)顧客到達(dá)時(shí)間間隔的分布顧客到達(dá)時(shí)間間隔的分布:假定假定 是獨(dú)立同分布，分布函數(shù)為是獨(dú)立同分布，分布函數(shù)為 ，排隊(duì)論中常用的有兩種：排隊(duì)論中常用的有兩種：nX

4、)(tAnX（2 2最簡(jiǎn)流即最簡(jiǎn)流即PoissonPoisson流）（流）（M M）：）： 顧客到達(dá)時(shí)間間隔顧客到達(dá)時(shí)間間隔 為獨(dú)立的，為獨(dú)立的， 服從負(fù)指數(shù)分布，其密度函數(shù)為服從負(fù)指數(shù)分布，其密度函數(shù)為（1 1定長(zhǎng)分布定長(zhǎng)分布D D）：顧客到達(dá)時(shí)間間隔為確定的。）：顧客到達(dá)時(shí)間間隔為確定的。000)(ttetat因?yàn)樨?fù)指數(shù)分布因?yàn)樨?fù)指數(shù)分布具有無后效性具有無后效性（即（即Markov性）性）運(yùn)籌學(xué)F2. 排隊(duì)及排隊(duì)規(guī)則排隊(duì)及排隊(duì)規(guī)則F即時(shí)制即時(shí)制(損失制損失制)F等待制等待制F先到先服務(wù)先到先服務(wù): FCFSF后到先服務(wù)后到先服務(wù): LCFSF隨機(jī)服務(wù)隨機(jī)服務(wù)F優(yōu)先權(quán)服務(wù)：優(yōu)先權(quán)服務(wù)：PSF

5、隊(duì)容量隊(duì)容量: 有限有限, 無限無限; 有形有形, 無形無形.F隊(duì)列數(shù)目隊(duì)列數(shù)目: 單列單列, 多列多列.運(yùn)籌學(xué)F3. 服務(wù)機(jī)構(gòu)服務(wù)機(jī)構(gòu)F服務(wù)員數(shù)量服務(wù)員數(shù)量: 無無, 單個(gè)單個(gè), 多個(gè)多個(gè).F隊(duì)列與服務(wù)臺(tái)的組合隊(duì)列與服務(wù)臺(tái)的組合F服務(wù)方式服務(wù)方式: 單個(gè)顧客單個(gè)顧客, 成批顧客成批顧客.F服務(wù)時(shí)間服務(wù)時(shí)間: 確定的確定的, 隨機(jī)的隨機(jī)的. 服務(wù)時(shí)間和到服務(wù)時(shí)間和到達(dá)間隔時(shí)間至少一個(gè)是隨機(jī)的達(dá)間隔時(shí)間至少一個(gè)是隨機(jī)的.F服務(wù)時(shí)間分布是平穩(wěn)的服務(wù)時(shí)間分布是平穩(wěn)的.運(yùn)籌學(xué)服務(wù)時(shí)間分布服務(wù)時(shí)間分布: 設(shè)某服務(wù)臺(tái)的服務(wù)時(shí)間為v，其密度函數(shù)為bt），常見的分布有：（1 1定長(zhǎng)分布定長(zhǎng)分布D D）：每個(gè)顧

6、客接受服務(wù)的時(shí)間）：每個(gè)顧客接受服務(wù)的時(shí)間 是一個(gè)確定的常數(shù)。是一個(gè)確定的常數(shù)。（2 2負(fù)指數(shù)分布負(fù)指數(shù)分布M M）：每個(gè)顧客接受服務(wù)時(shí)間）：每個(gè)顧客接受服務(wù)時(shí)間 相互獨(dú)立，具有相互的負(fù)指數(shù)分布：相互獨(dú)立，具有相互的負(fù)指數(shù)分布： 其中其中 ，為一常數(shù)。，為一常數(shù)。000)(ttetbt0- - 單位時(shí)間平均服務(wù)完成的顧客數(shù)單位時(shí)間平均服務(wù)完成的顧客數(shù)1/ - 1/ - 每個(gè)顧客的平均服務(wù)時(shí)間每個(gè)顧客的平均服務(wù)時(shí)間運(yùn)籌學(xué)服務(wù)時(shí)間分布服務(wù)時(shí)間分布:（3 3k k階愛爾朗階愛爾朗ErlangErlang分布：每個(gè)顧客接受服務(wù)分布：每個(gè)顧客接受服務(wù) 時(shí)間服從時(shí)間服從k k階愛爾朗分布，其密度函數(shù)為：階

7、愛爾朗分布，其密度函數(shù)為：tkkektkktb)!1()()(1運(yùn)籌學(xué)符號(hào)表示符號(hào)表示: X/Y/ZX 顧客到達(dá)間隔時(shí)間分布顧客到達(dá)間隔時(shí)間分布Y - 服務(wù)時(shí)間分布服務(wù)時(shí)間分布Z - 服務(wù)臺(tái)個(gè)數(shù)服務(wù)臺(tái)個(gè)數(shù)X, Y 可以是可以是:M - 負(fù)指數(shù)分布負(fù)指數(shù)分布D - 確定型確定型Ek - k階階Erlang分布分布GI - 一般相互獨(dú)立的到達(dá)時(shí)間間隔分布一般相互獨(dú)立的到達(dá)時(shí)間間隔分布G - 一般一般(General)時(shí)間分布時(shí)間分布運(yùn)籌學(xué)擴(kuò)展符號(hào)表示擴(kuò)展符號(hào)表示: X/Y/Z/A/B/CA - 系統(tǒng)容量系統(tǒng)容量B - 顧客源中顧客的數(shù)量顧客源中顧客的數(shù)量C - 服務(wù)規(guī)則服務(wù)規(guī)則: FCFS, LCFS, 等等等等.若省略后三項(xiàng)，即是指下面的情形：若省略后三項(xiàng)，即是指下面的情形： X/Y/Z/ / /FCFS 例：M/M/s/K表示？運(yùn)籌學(xué)知知: 顧客到達(dá)間隔時(shí)間分布顧客到達(dá)間隔時(shí)間分布, 服務(wù)時(shí)間分布服務(wù)時(shí)間分布. 求求:隊(duì)長(zhǎng)隊(duì)長(zhǎng): Ls - 系統(tǒng)中的顧客數(shù)系統(tǒng)中的顧客數(shù). 排隊(duì)長(zhǎng)排隊(duì)長(zhǎng)(隊(duì)列長(zhǎng)隊(duì)列長(zhǎng)): Lq - 隊(duì)列中的顧客數(shù)隊(duì)列中的顧客數(shù). Ls = Lq + 正在接受服務(wù)的顧客數(shù)正在接受服務(wù)的