排隊論簡要知識排隊論簡要知識排隊論簡要知識排隊論的根本概念

排隊系統描述根本概念M/M/1模型M/M/S模型人有了知識，就會具備各種分析能力，明辨是非的能力。排隊論的根本概念

排隊系統描述根本概念M/M/1模型M/M/S模型第一節排隊系統描述顧客－－－要求效勞的對象統稱為“顧客〞效勞臺－－－把提供效勞的人或機構稱為“效勞臺〞或“效勞員〞

各種形式的排隊系統

各種形式的排隊系統各種形式的排隊系統各種形式的排隊系統各種形式的排隊系統隨機效勞系統排隊論所要研究解決的問題

面對擁擠現象，人們通常的做法是增加效勞設施，但是增加的數量越多，人力、物力的支出就越大，甚至會出現空閑浪費，如果效勞設施太少，顧客排隊等待的時間就會很長，這樣對顧客會帶來不良影響。如何做到既保證一定的效勞質量指標，又使效勞設施費用經濟合理，恰當地解決顧客排隊時間與效勞設施費用大小這對矛盾，就是隨機效勞系統理論——排隊論所要研究解決的問題。第一節根本概念；

一、排隊系統的描述二、排隊系統的主要數量指標一、排隊系統的描述

(一)系統特征和根本排隊過程(二)排隊系統的根本組成局部〔三)排隊系統的描述符號(一)系統特征和根本排隊過程相似的特征及數學抽象：(1)請求效勞的人或者物——顧客；(2)有為顧客效勞的人或者物，即效勞員或效勞臺；(3)顧客到達系統的時刻是隨機的，為每一位顧客提供效勞的時間是隨機的，因而整個排隊系統的狀態也是隨機的。(一)系統特征和根本排隊過程

根本排隊過程可以用圖6—6表示。從圖6—6可知，每個顧客由顧客源按一定方式到達效勞系統，首先參加隊列排隊等待承受效勞，然后效勞臺按一定規則從隊列中選擇顧客進展效勞，獲得效勞的顧客立即離開。(二)排隊系統的根本組成局部

排隊系統由3個局部組成1、輸入過程2、效勞規則3、效勞臺1．輸入過程

這是指要求效勞的顧客是按怎樣的規律到達排隊系統的過程，有時也把它稱為顧客流。一般可以從3個方面來描述—個輸入過程。(1)顧客總體數，又稱顧客源、輸入源。這是指顧客的來源。顧客源可以是有限的，也可以是無限的。(2)顧客到達方式。這是描述顧客是怎樣來到系統的，是單個到達，還是成批到達。(3)顧客流的概率分布，或稱相繼顧客到達的時間間隔的分布。這是求解排隊系統有關運行指標問題時，首先需要確定的指標。顧客流的概率分布一般有定長分布、二項分布、泊松流(最簡單流)、愛爾朗分布等假設干種。2．效勞規則

這是指效勞臺從隊列中選取顧客進展效勞的順序。一般可以分為損失制、等待制和混合制等3大類。(1)損失制。這是指如果顧客到達排隊系統時，所有效勞臺都被先到的顧客占用，則他們就自動離開系統永不再來。2．效勞規則(2)等待制這是指當顧客來到系統時，所有效勞臺都不空，顧客參加排隊行列等待效勞。等待制中，效勞臺在選擇顧客進展效勞時常有如下四種規則：1)先到先效勞。按顧客到達的先后順序對顧客進展效勞。2)后到先效勞。3)隨機效勞。即當效勞臺空閑時，不按照排隊序列而隨意指定某個顧客承受效勞。4)優先權效勞。2．效勞規則(3)混合制這是等待制與損失制相結合的一種效勞規則，一般是指允許排隊，但又不允許隊列無限長下去。具體說來，大致有三種：1)隊長有限。當排隊等待效勞的顧客人數超過規定數量時，后來的顧客就自動離去，另求效勞，即系統的等待空間是有限的。2)等待時間有限。即顧客在系統中的等待時間不超過某一給定的長度T，當等待時間超過T時，顧客將自動離去，并不再回來。3)逗留時間(等待時間與效勞時間之和)有限。3．效勞臺

(1)效勞臺數量及構成形式。從數量上說，效勞臺有單效勞臺和多效勞臺之分。從構成形式上看，效勞臺有：①單隊—－單效勞臺式；②單隊-－多效勞臺并聯式;③多隊—－多效勞臺并聯式；④單隊—－多效勞臺串聯式；⑤單隊—－多效勞臺并串聯混合式，以及多隊多效勞臺并串聯混合式等等。(2)效勞方式。這是指在某一時刻承受效勞的顧客數，它有單個效勞和成批效勞兩種。(3)效勞時間的分布。在多數情況下，對每一個顧客的效勞時間是一隨機變量?！踩?排隊系統的符號表述

描述符號：①/②/③/④/⑤/⑥

各符號的意義：①——表示顧客相繼到達間隔時間分布，常用以下符號：M——表示到達的過程為泊松過程或負指數分布；D——表示定長輸入；EK——表示K階愛爾朗分布；G——表示一般相互獨立的隨機分布。

各符號的意義:

②——表示效勞時間分布，所用符號與表示顧客到達間隔時間分布一樣。③——表示效勞臺(員)個數：“1〞表示單個效勞臺，“s〞(s>1)表示多個效勞臺。④——表示系統中顧客容量限額，或稱等待空間容量。如系統有K個等待位子，則，0<K<∞，當K=0時，說明系統不允許等待，即為損失制。K=∞時為等待制系統，此時一般∞省略不寫。K為有限整數時，表示為混合制系統。各符號的意義：⑤——表示顧客源限額，分有限與無限兩種，∞表示顧客源無限，一般∞也可省略不寫。⑥——表示效勞規則，常用以下符號FCFS：表示先到先效勞的排隊規則；LCFS：表示后到先效勞的排隊規則；PR：表示優先權效勞的排隊規則。各符號的意義：例如，某排隊問題為M／M／S／∞／∞/FCFS，則表示顧客到達間隔時間為負指數分布(泊松流)；效勞時間為負指數分布；有s(s>1)個效勞臺；系統等待空間容量無限(等待制)；顧客源無限，采用先到先效勞規則。某些情況下，排隊問題僅用上述表達形式中的前3個符號。例如，某排隊問題為M／M／S，如不特別說明則均理解為系統等待空間容量無限；顧客源無限，先到先效勞，單個效勞的等待制系統。二，排隊系統的主要數量指標

描述一個排隊系統運行狀況的主要數量指標有：1．隊長和排隊長(隊列長)隊長是指系統中的顧客數(排隊等待的顧客數與正在承受效勞的顧客數之和)；排隊長是指系統中正在排隊等待效勞的顧客數。隊長和排隊長一般都是隨機變量。二、排隊系統的主要數量指標

2．等待時間和逗留時間從顧客到達時刻起到他開場承受效勞止這段時間稱為等待時間。等待時間是個隨機變量。從顧客到達時刻起到他承受效勞完成止這段時間稱為逗留時間，也是隨機變量。3.忙期和閑期忙期是指從顧客到達空閑著的效勞機構起，到效勞機構再次成為空閑止的這段時間，即效勞機構連續忙的時間。這是個隨機變量，是效勞員最為關心的指標，因為它關系到效勞員的效勞強度。與忙期相對的是閑期,即效勞機構連續保持空閑的時間。在排隊系統中，忙期和閑期總是交替出現的。二、排隊系統的主要數量指標

4．數量指標的常用記號(1)主要數量指標L——平均隊長，即穩態系統任一時刻的所有顧客數的期望值；Lq——平均等待隊長，即穩態系統任一時刻等待效勞的顧客數的期望值；W——平均逗留時間，即(在任意時刻)進入穩態系統的顧客逗留時間的期望值；Wq——平均等待時間，即(在任意時刻)進入穩態系統的顧客等待時間的期望值。

4．數量指標的常用記號

(2)其他常用數量指標s——系統中并聯效勞臺的數目；λ——平均到達率；1／λ——平均到達間隔；μ——平均效勞率；1/μ——平均效勞時間；N――穩態系統任一時刻的狀態〔即系統中所有顧客數〕；U――任一顧客在穩態系統中的逗留時間；Q――任一顧客在穩態系統中的等待時間；(2)其他常用數量指標

(2)其他常用數量指標ρ——效勞強度，即每個效勞臺單位時間內的平均效勞時間，—般有ρ=λ／(sμ)，這是衡量排隊系統繁忙程度的重要尺度，當ρ趨近于0時，說明對期望效勞的數量來說，效勞能力相對地說是很大的。這時，等待時間一定很短，效勞臺有大量的空閑時間；如效勞強度ρ趨近于1，則效勞臺空閑時間較少而顧客等待時間較多。我們一般都假定平均效勞率μ大于平均到達率λ，即λ/μ<1,否則排隊的人數會越來越多，以后總是保持這個假設而不再聲明。李特爾公式

在系統到達穩態時，假定平均到達率為常數λ，平均效勞時間為常數1/μ，則有下面的李特爾公式：L=λWLq=λWqW=Wq+1/μL=Lq+λ/μ排隊系統運行情況的分析

排隊系統運行情況的分析，就是在給定輸人與效勞條件下，通過求解系統狀態為n(有n個顧客)的概率Pn，再進展計算其主要的運行指標：①系統中顧客數(隊長)的期望值L；②排隊等待的顧客數(排隊長)的期望值Lq；③顧客在系統中全部時間(逗留時間)的期望值W；④顧客排隊等待時間的期望值Wq。第二節M／N／1模型

模型的條件是：1、輸入過程――顧客源是無限的，顧客到達完全是隨機的，單個到來，到達過程服從普阿松分布，且是平穩的；2、排隊規則――單隊，且隊長沒有限制，先到先效勞；3、效勞機構――單效勞臺，效勞時間的長短是隨機的，服從一樣的指數分布。對于M／ M／1模型有如下公式：

例1某醫院急診室同時只能診治一個病人，診治時間服從指數分布，每個病人平均需要15分鐘。病人按泊松分布到達，平均每小時到達3人。試對此排隊隊系統進展分析。解對此排隊隊系統分析如下：〔1〕先確定參數值：這是單效勞臺系統，有：

故效勞強度為：〔2〕計算穩態概率：

這就是急診室空閑的概率，也是病人不必等待立即就能就診的概率。

而病人需要等待的概率則為：

這也是急診室繁忙的概率。

〔2〕計算系統主要工作指標。

急診室內外的病人平均數：

急診室外排隊等待的病人平均數：

病人在急診室內外平均逗留時間：

病人平均等候時間：

〔4〕為使病人平均逗留時間不超過半小時，則平均效勞時間應減少多少？

由于

代入λ=3，解得μ≥5，平均效勞時間為：

15－12＝3min

即平均效勞時間至少應減少3min

(5)假設醫院希望候診的病人90%以上都能有座位,則候診室至少應安置多少座位

設應該安置χ個座位,加上急診室的一個座位,共有χ+1個。要使90%以上的候診病人有座位，相當于使“來診的病人數不多于χ+1個〞的概率不少于90%，即

兩邊取對數

〔x＋2〕lgρ≤lg0.1

因ρ<1，故

所以ⅹ≥6

即候診室至少應安置6個座位。

第三節

M/M/S模型

此模型與M/M/1模型不同之處在于有S個效勞臺，各效勞臺的工作相互獨立，效勞率相等，如果顧客到達時，S個效勞臺都忙著，則排成一隊等待，先到先效勞的單隊模型。整個系統的平均效勞率為sμ，ρ*＝λ/sμ，〔ρ*<1〕為該系統的效勞強度。1、狀態概率2、主要運行指標

3、系統狀態N≥S的概率例2承接例1，假設醫院增強急診室的效勞能力，使其同時能診治兩個病人，且平均效勞率一樣，試分析該系統工作情況，并且，例1、例2的結果進展比較。

解這相當于增加了一個效勞臺，故有：S=2,λ=3人/h，μ=4人/h病人必須等候的概率,即系統狀態N≥2的概率：

表6－1兩個系統的比較指標S=1系統S=2系統P（Q>0）0.750．20Lq2.25人0．12人L3人0．87人W60min17．4minWq45min2．4min例3某醫院掛號室有三個窗口，就診者的到達服從泊松分布，平均到達率為每分鐘人，掛號員效勞時間服從指數分布，平均效勞率每分鐘04人，現假設就診者到達后排成一隊，依次向空閑的窗口掛號，顯然系統的容量和顧客源是不限的，屬于M/M/1型的排隊效勞模型。求：該系統的運行指標

解

如果在例3中，就診者到達后在每個掛號窗口各自排成一隊，即排成3隊，且進入隊列后不離開，各列間也互不串換，這就形成3個隊列，而例3中的其它條件不變。假設每個隊列平均到達率相等且為：

λ1＝λ2＝λ3＝0.9/3＝0.3〔人/分鐘〕

這樣，原來的M/M/3系統就變成了3個M/M/1型的子系統。

現按M/M/1型計算主要運行指標，并與上面的例子進展比照分析，結果見表6－2

表6－2兩個模型的比較指標（1）M/M/3型（2）M/M/1型掛號間空閑的概率0.07480.25（各子系統）就診者必須等待的概率P(N>3)=0.570.75平均隊