運(yùn)籌學(xué)大學(xué)課件第十四章排隊(duì)論的基本知識(shí)文檔

排隊(duì)論的基本知識(shí)1.1

排隊(duì)模型1.2排隊(duì)系統(tǒng)的組成和特征排隊(duì)論排隊(duì)論研究的內(nèi)容性態(tài)問題:排隊(duì)系統(tǒng)的概率規(guī)律,如隊(duì)長分布,等待時(shí)間分布等.最優(yōu)化問題:排隊(duì)系統(tǒng)的最優(yōu)設(shè)計(jì).統(tǒng)計(jì)推斷:判定排隊(duì)系統(tǒng)的類型.顧客源一、排隊(duì)模型排隊(duì)系統(tǒng)排隊(duì)結(jié)構(gòu)服務(wù)機(jī)構(gòu)排隊(duì)規(guī)則服務(wù)規(guī)則接受服務(wù)后離去——排隊(duì)系統(tǒng)的的一般表示服務(wù)機(jī)構(gòu)服務(wù)臺(tái)(a)一個(gè)隊(duì)列、單服務(wù)臺(tái)（階段）服務(wù)臺(tái)1服務(wù)臺(tái)2服務(wù)機(jī)構(gòu)(b)一個(gè)隊(duì)列、s個(gè)服務(wù)階段服務(wù)臺(tái)1服務(wù)臺(tái)2服務(wù)機(jī)構(gòu)(c)一個(gè)隊(duì)列、s個(gè)服務(wù)臺(tái)一個(gè)服務(wù)階段服務(wù)臺(tái)3服務(wù)臺(tái)4服務(wù)臺(tái)1服務(wù)臺(tái)2服務(wù)機(jī)構(gòu)(d)s個(gè)隊(duì)列、s個(gè)服務(wù)階段服務(wù)臺(tái)3服務(wù)臺(tái)4服務(wù)臺(tái)1服務(wù)臺(tái)2:1–2–4:2–4–3:3–2–1–4服務(wù)機(jī)構(gòu)(e)混合型排隊(duì)結(jié)構(gòu)服務(wù)臺(tái)(f)一個(gè)隊(duì)列服務(wù)臺(tái)(g)s個(gè)隊(duì)列

1.輸入過程顧客總體:有限,無限.顧客到達(dá)方式:單個(gè),成批.顧客到達(dá)間隔時(shí)間:確定的、隨機(jī)的.顧客到達(dá)的獨(dú)立性:獨(dú)立,不獨(dú)立.輸入過程的平穩(wěn)性:與時(shí)間無關(guān)(平穩(wěn)的),與時(shí)間有關(guān)(非平穩(wěn)的).二、排隊(duì)系統(tǒng)的組成和特征顧客到達(dá)時(shí)間間隔的分布:：第n個(gè)顧客到達(dá)的時(shí)刻；設(shè)：第n個(gè)顧客與第n-1個(gè)顧客到達(dá)的時(shí)間間隔；令顧客到達(dá)時(shí)間間隔的分布:假定是獨(dú)立同分布，分布函數(shù)為，排隊(duì)論中常用的有兩種：（2）最簡流（即Poisson流）（M）：

顧客到達(dá)時(shí)間間隔為獨(dú)立的，服從負(fù)指數(shù)分布，其密度函數(shù)為（1）定長分布（D）：顧客到達(dá)時(shí)間間隔為確定的。因?yàn)樨?fù)指數(shù)分布具有無后效性（即Markov性）

2.排隊(duì)及排隊(duì)規(guī)則即時(shí)制(損失制)等待制先到先服務(wù):FCFS后到先服務(wù):LCFS隨機(jī)服務(wù)優(yōu)先權(quán)服務(wù)：PS隊(duì)容量:有限,無限;有形,無形.隊(duì)列數(shù)目:單列,多列.

3.服務(wù)機(jī)構(gòu)服務(wù)員數(shù)量:無,單個(gè),多個(gè).隊(duì)列與服務(wù)臺(tái)的組合服務(wù)方式:單個(gè)顧客,成批顧客.服務(wù)時(shí)間:確定的,隨機(jī)的.服務(wù)時(shí)間和到達(dá)間隔時(shí)間至少一個(gè)是隨機(jī)的.服務(wù)時(shí)間分布是平穩(wěn)的.服務(wù)時(shí)間分布:

設(shè)某服務(wù)臺(tái)的服務(wù)時(shí)間為v，其密度函數(shù)為b（t），常見的分布有：（1）定長分布（D）：每個(gè)顧客接受服務(wù)的時(shí)間是一個(gè)確定的常數(shù)。（2）負(fù)指數(shù)分布（M）：每個(gè)顧客接受服務(wù)時(shí)間相互獨(dú)立，具有相互的負(fù)指數(shù)分布：

其中，為一常數(shù)。μ--單位時(shí)間平均服務(wù)完成的顧客數(shù)1/μ--每個(gè)顧客的平均服務(wù)時(shí)間服務(wù)時(shí)間分布:（3）k階愛爾朗（Erlang）分布：每個(gè)顧客接受服務(wù)時(shí)間服從k階愛爾朗分布，其密度函數(shù)為：

符號(hào)表示:X/Y/ZX–顧客到達(dá)間隔時(shí)間分布Y--服務(wù)時(shí)間分布Z--服務(wù)臺(tái)個(gè)數(shù)X,Y可以是:M--負(fù)指數(shù)分布D--確定型Ek--k階Erlang分布GI--一般相互獨(dú)立的到達(dá)時(shí)間間隔分布G--一般(General)時(shí)間分布三、排隊(duì)系統(tǒng)的分類

擴(kuò)展符號(hào)表示:X/Y/Z/A/B/CA--系統(tǒng)容量B--顧客源中顧客的數(shù)量C--服務(wù)規(guī)則:FCFS,LCFS,等等.若省略后三項(xiàng)，即是指下面的情形：

X/Y/Z///FCFS例：M/M/s/K表示？

已知:顧客到達(dá)間隔時(shí)間分布,服務(wù)時(shí)間分布.求:隊(duì)長:Ls--系統(tǒng)中的顧客數(shù).排隊(duì)長(隊(duì)列長):Lq--隊(duì)列中的顧客數(shù).

Ls=

Lq+正在接受服務(wù)的顧客數(shù)逗留時(shí)間:WS--顧客在系