當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

排队论模型（一）：基本概念、输入过程与服务时间的常用概率分布

發布時間：2024/8/1 编程问答 32 豆豆

生活随笔收集整理的這篇文章主要介紹了排队论模型（一）：基本概念、输入过程与服务时间的常用概率分布小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

排隊論模型（一）：基本概念、輸入過程與服務時間的常用概率分布

排隊論模型（二）：生滅過程、 M / M /s 等待制排隊模型、多服務臺模型

排隊論模型（三）：M / M / s/ s 損失制排隊模型

排隊論模型（四）：M / M / s 混合制排隊模型

排隊論模型（五）：有限源排隊模型、服務率或到達率依賴狀態的排隊模型

排隊論模型（六）：非生滅過程排隊模型、愛爾朗（Erlang）排隊模型

排隊論模型（七）：排隊系統的優化

排隊論模型（八）：Matlab 生成隨機數、排隊模型的計算機模擬

排隊論起源于 1909 年丹麥電話工程師 A. K．愛爾朗的工作，他對電話通話擁擠問題進行了研究。1917 年，愛爾朗發表了他的著名的文章—“自動電話交換中的概率理論的幾個問題的解決”。排隊論已廣泛應用于解決軍事、運輸、維修、生產、服務、庫存、醫療衛生、教育、水利灌溉之類的排隊系統的問題，顯示了強大的生命力。

排隊是在日常生活中經常遇到的現象，如顧客到商店購買物品、病人到醫院看病常常要排隊。此時要求服務的數量超過服務機構（服務臺、服務員等）的容量。也就是說，到達的顧客不能立即得到服務，因而出現了排隊現象。這種現象不僅在個人日常生活中出現，電話局的占線問題，車站、碼頭等交通樞紐的車船堵塞和疏導，故障機器的停機待修，水庫的存貯調節等都是有形或無形的排隊現象。由于顧客到達和服務時間的隨機性。可以說排隊現象幾乎是不可避免的。

1.1 ?排隊過程的一般表示

2 排隊系統的組成和特征?

2.1 輸入過程? ? ? ? ? ? ? ? ? ?2.2 排隊規則

2.3 服務過程? ? ? ? ? ? ? ??（i）服務機構。? ? ? ? ? ? ??（ii）服務規則。

3 排隊模型的符號表示? ? ? ? ? ? ? ? ?4 排隊系統的運行指標

3 輸入過程與服務時間的分布?

3.1 泊松流與指數分布? ?

3.2 常用的幾種概率分布及其產生

（i）均勻分布? ? ? ? ? ? ? ? ? ? ? ? ??（ii）正態分布? ? ? ? ? ? ?? ? ? ? ? ? ? ? ??（iii）指數分布

（iv）Gamma 分布、愛爾朗分布? ? ? ? ? ?（v）Weibull 分布? ? ? ? ? ? ??（vi）Beta 分布

（i）離散均勻分布? ? ? ? ? ? ? ? ??（ii）Bernoulli 分布（兩點分布）

（iii）泊松（Poisson）分布? ? ? ? ? ? ? ? ? ??（iv）二項分布

排隊論（Queuing Theory）也稱隨機服務系統理論，就是為解決上述問題而發展的一門學科。它研究的內容有下列三部分：

（i）性態問題，即研究各種排隊系統的概率規律性，主要是研究隊長分布、等待時間分布和忙期分布等，包括了瞬態和穩態兩種情形。

（ii）最優化問題，又分靜態最優和動態最優，前者指最優設計。后者指現有排隊系統的最優運營。

（iii）排隊系統的統計推斷，即判斷一個給定的排隊系統符合于哪種模型，以便根據排隊理論進行分析研究。

這里將介紹排隊論的一些基本知識，分析幾個常見的排隊模型。

1.1 ?排隊過程的一般表示

下圖是排隊論的一般模型。

圖中虛線所包含的部分為排隊系統。各個顧客從顧客源出發，隨機地來到服務機構，按一定的排隊規則等待服務，直到按一定的服務規則接受完服務后離開排隊系統。

凡要求服務的對象統稱為顧客，為顧客服務的人或物稱為服務員，由顧客和服務員組成服務系統。對于一個服務系統來說，如果服務機構過小，以致不能滿足要求服務的眾多顧客的需要，那么就會產生擁擠現象而使服務質量降低。因此，顧客總希望服務機構越大越好，但是，如果服務機構過大，人力和物力方面的開支也就相應增加，從而會造成浪費，因此研究排隊模型的目的就是要在顧客需要和服務機構的規模之間進行權衡決策，使其達到合理的平衡。

2 排隊系統的組成和特征

一般的排隊過程都由輸入過程、排隊規則、服務過程三部分組成，現分述如下：

2.1 輸入過程

輸入過程是指顧客到來時間的規律性，可能有下列不同情況：

（i）顧客的組成可能是有限的，也可能是無限的。

（ii）顧客到達的方式可能是一個—個的，也可能是成批的。

（iii）顧客到達可以是相互獨立的，即以前的到達情況對以后的到達沒有影響；否則是相關的。

（iv）輸入過程可以是平穩的，即相繼到達的間隔時間分布及其數學期望、方差等數字特征都與時間無關，否則是非平穩的。

2.2 排隊規則

排隊規則指到達排隊系統的顧客按怎樣的規則排隊等待，可分為損失制，等待制和混合制三種。

（i）損失制（消失制）。當顧客到達時，所有的服務臺均被占用，顧客隨即離去。

（ii）等待制。當顧客到達時，所有的服務臺均被占用，顧客就排隊等待，直到接受完服務才離去。

? ? ? ? ? ? 例如出故障的機器排隊等待維修就是這種情況。

（iii）混合制。介于損失制和等待制之間的是混合制，即既有等待又有損失。有隊列長度有限和排隊等待時間有限兩種情況，在限度以內就排隊等待，超過一定限度就離去。

排隊方式還分為單列、多列和循環隊列。

2.3 服務過程

（i）服務機構。

主要有以下幾種類型：單服務臺；多服務臺并聯（每個服務臺同時為不同顧客服務）；多服務臺串聯（多服務臺依次為同一顧客服務）；混合型。

（ii）服務規則。

按為顧客服務的次序采用以下幾種規則：

①先到先服務，這是通常的情形。

②后到先服務，如情報系統中，最后到的情報信息往往最有價值，因而常被優先處理。

③隨機服務，服務臺從等待的顧客中隨機地取其一進行服務，而不管到達的先后。

④優先服務，如醫療系統對病情嚴重的病人給予優先治療。

3 排隊模型的符號表示

排隊模型用六個符號表示，在符號之間用斜線隔開，即 X /Y / Z / A/ B /C 。

第一個符號 X 表示顧客到達流或顧客到達間隔時間的分布；

第二個符號Y 表示服務時間的分布； ? ? ? ? ??第三個符號 Z 表示服務臺數目；

第四個符號 A 是系統容量限制； ? ? ? ?第五個符號 B 是 顧客源數目； ? ? ? 第六個符號C 是服務規則，

如先到先服務 FCFS，后到先服務 LCFS 等。并約定，如略去后三項，即指 X /Y / Z / ∞ / ∞ / FCFS的情形。

我們只討論先到先服務 FCFS 的情形，所以略去第六項。

表示顧客到達間隔時間和服務時間的分布的約定符號為：

M — ?指數分布（ M 是 Markov 的字頭，因為指數分布具有無記憶性，即 Markov 性）；

D — 確定型（Deterministic）；

?? — k 階愛爾朗(Erlang)分布；

G — ? ? 一般（general）服務時間的分布；

GI — ?一般相互獨立（General Independent）的時間間隔的分布。

例如， M / M /1表示相繼到達間隔時間為指數分布、服務時間為指數分布、單服務臺、等待制系統。

D / M / c 表示確定的到達時間、服務時間為指數分布、 c 個平行服務臺（但顧客是一隊）的模型。

4 排隊系統的運行指標

為了研究排隊系統運行的效率，估計其服務質量，確定系統的最優參數，評價系統的結構是否合理并研究其改進的措施，必須確定用以判斷系統運行優劣的基本數量指標，這些數量指標通常是：

(i)平均隊長：指系統內顧客數（包括正被服務的顧客與排隊等待服務的顧客）的數學期望，記作 Ls 。

(ii)平均排隊長:指系統內等待服務的顧客數的數學期望，記作 Lq 。

(iii)平均逗留時間：顧客在系統內逗留時間（包括排隊等待的時間和接受服務的時間）的數學期望，記作Ws 。

（iv）平均等待時間：指一個顧客在排隊系統中排隊等待時間的數學期望，記作 Wq 。

（v）平均忙期：指服務機構連續繁忙時間（顧客到達空閑服務機構起，到服務機構再次空閑止的時間）長度的數學期望，記為Tb 。

還有由于顧客被拒絕而使企業受到損失的損失率以及以后經常遇到的服務強度等，這些都是很重要的指標。

計算這些指標的基礎是表達系統狀態的概率。所謂系統的狀態即指系統中顧客數，如果系統中有n 個顧客就說系統的狀態是n ，它的可能值是

3 輸入過程與服務時間的分布

排隊系統中的事件流包括顧客到達流和服務時間流。由于顧客到達的間隔時間和服務時間不可能是負值，因此，它的分布是非負隨機變量的分布。最常用的分布有泊松分布、確定型分布，指數分布和愛爾朗分布。

3.1 泊松流與指數分布

在上述條件下，我們研究顧客到達數n 的概率分布。

對于泊松流, λ 表示單位時間平均到達的顧客數,所以 ?就表示相繼顧客到達平均間隔時間，而這正和 ET 的意義相符。對一顧客的服務時間也就是在忙期相繼離開系統的兩顧客的間隔時間，有時也服從指數分布。這時設它的分布函數和密度函數分別是

3.2 常用的幾種概率分布及其產生

3.2.1 常用的連續型概率分布

我們只給出這些分布的參數、記號和通常的應用范圍，更詳細的內容參看專門的概率論書籍。

（i）均勻分布

區間 (a,b) 內的均勻分布記作U(a,b) 。服從U(0,1) 分布的隨機變量又稱為隨機數，它是產生其它隨機變量的基礎。如若 X 為U(0,1) 分布，則Y = a + (b ? a)X 服從 U(a,b) 。

（ii）正態分布

?正態分布還可以作為二項分布一定條件下的近似。

?（iii）指數分布

（iv）Gamma 分布、愛爾朗分布

Gamma 分布又稱愛爾朗分布。

Gamma 分布是雙參數α,β 的非對稱分布，記作G(α,β ) ，期望是αβ 。α = 1時蛻化為指數分布。 n 個相互獨立、同分布（參數 λ ）的指數分布之和是 Gamma 分布（α = n, β = λ) 。Gamma 分布可用于服務時間，零件壽命等。

（v）Weibull 分布

? ? ? Weibull 分布是雙參數α,β 的非對稱分布，記作W(α, β ) 。α = 1時蛻化為指數分布。作為設備、零件的壽命分布在可靠性分析中有著非常廣泛的應用。

（vi）Beta 分布

Beta 分布是區間(0,1) 內的雙參數、非均勻分布，記作 B(α, β ) 。

2.2.2 常用的離散型概率分布

（i）離散均勻分布

（ii）Bernoulli 分布（兩點分布）

Bernoulli 分布是 x = 1,0 處取值的概率分別是 p 和1? p 的兩點分布，記作 Bern( p) 。用于基本的離散模型。

（iii）泊松（Poisson）分布

泊松分布與指數分布有密切的關系。當顧客平均到達率為常數 λ 的到達間隔服從指數分布時，單位時間內到達的顧客數 K 服從泊松分布，即單位時間內到達 k 位顧客的概率為

記作 Poisson(λ) 。泊松分布在排隊服務、產品檢驗、生物與醫學統計、天文、物理等領域都有廣泛應用。

（iv）二項分布

在獨立進行的每次試驗中，某事件發生的概率為 p ，則 n 次試驗中該事件發生的次數 K 服從二項分布，即發生k 次的概率為

記作 B(n, p) 。二項分布是n 個獨立的 Bernoulli 分布之和。它在產品檢驗、保險、生物和醫學統計等領域有著廣泛的應用。

當n,k 很大時， B(n, p) 近似于正態分布 N(np,np(1? p)) ；

當n 很大、 p 很小，且np 約為常數λ 時， B(n, p) 近似于 Poisson(λ)。
?