1、隨機(jī)運籌學(xué)，第6部分排隊論，1?；靖拍睿?。排隊論研究內(nèi)容排隊論是日常生活中常見的現(xiàn)象，如顧客去商店購物、病人去醫(yī)院看病、電信局的繁忙問題、車站、碼頭等交通樞紐的交通堵塞和改道、待修故障機(jī)器停機(jī)、水庫蓄水和水量調(diào)節(jié)等。排隊現(xiàn)象的根源是由于服務(wù)人員數(shù)量超過服務(wù)機(jī)構(gòu)數(shù)量，客戶無法立即獲得服務(wù)。如果增加了服務(wù)設(shè)備，就必須增加投資或閑置浪費；如果服務(wù)設(shè)備太少，排隊現(xiàn)象會很嚴(yán)重，給顧客和社會帶來不良影響。因此，管理者應(yīng)該考慮成本和收益之間的平衡。排隊論，又稱隨機(jī)服務(wù)系統(tǒng)理論，主要包括以下三個部分：1 .行為問題研究各種排隊系統(tǒng)的概率規(guī)律，主要研究排隊長度分布、等待時間分布和繁忙時段分布，包括瞬態(tài)和穩(wěn)態(tài)

2、情況。2.優(yōu)化問題主要包括靜態(tài)優(yōu)化和動態(tài)優(yōu)化，而靜態(tài)優(yōu)化是指優(yōu)化設(shè)計，動態(tài)優(yōu)化是指現(xiàn)有排隊系統(tǒng)的優(yōu)化運行。3.排隊系統(tǒng)的統(tǒng)計推斷決定了一個給定的排隊系統(tǒng)符合哪個模型，從而可以根據(jù)排隊論進(jìn)行分析和研究。第二，排隊過程通常意味著每個顧客從顧客來源(整體)開始，在到達(dá)服務(wù)機(jī)構(gòu)(服務(wù)臺、服務(wù)員)之前排隊等候接受服務(wù)，并在服務(wù)完成后離開。排隊結(jié)構(gòu)指的是隊列的數(shù)量和排列，而排隊規(guī)則和服務(wù)規(guī)則描述的是顧客在排隊系統(tǒng)中接受服務(wù)的規(guī)則和順序。顧客來源，排隊結(jié)構(gòu)，服務(wù)機(jī)制，排隊規(guī)則，服務(wù)規(guī)則，顧客到達(dá)，離開，排隊系統(tǒng)，排隊系統(tǒng)的組成和特點一般的排隊系統(tǒng)有三個基本組成部分：(1)輸入過程；(2)排隊規(guī)則；(3)服務(wù)

3、組織。1、輸入流程輸入是指顧客到達(dá)排隊系統(tǒng)。輸入有以下幾種情況：(1)客戶的客戶總數(shù)稱為客戶來源，它可以是有限的，也可以是無限的。例如，流入水庫的上游河水可以被認(rèn)為是無限的，工廠中只有有限的機(jī)器需要關(guān)閉進(jìn)行維修。(2)顧客可以一個接一個或分批到達(dá)。例如，在餐館就餐時，有一個客人到達(dá)，一批客人被邀請參加宴會。(3)顧客陸續(xù)到達(dá)的時間間隔可以是確定性的，也可以是隨機(jī)的。例如，在自動裝配線上裝配的每個部件都必須在一定的時間間隔內(nèi)到達(dá)裝配點，普通公共汽車、班輪和航班的到達(dá)也是一定的。一般來說，去商店購物的顧客、去醫(yī)院的病人和通過十字路口的車輛的到來是隨機(jī)的。對于隨機(jī)情況，我們應(yīng)該知道每單位時間到達(dá)的顧

4、客數(shù)量或連續(xù)到達(dá)的間隔時間的概率分布。(4)顧客到達(dá)的相關(guān)性，顧客的到達(dá)可以是獨立的或相關(guān)的。例如，工廠中短時間間隔內(nèi)機(jī)器停機(jī)的概率受已維修或修理的機(jī)器數(shù)量的影響。(5)輸入過程可以是平穩(wěn)的(時間上是均勻的)，這意味著描述連續(xù)到達(dá)的時間分布和參數(shù)(如期望值、方差等)。)與時間無關(guān)。否則，它被稱為不穩(wěn)定，這是很難用數(shù)學(xué)方法處理的。2.排隊規(guī)則(1)顧客到達(dá)的即時系統(tǒng)和等待系統(tǒng)。當(dāng)顧客到達(dá)時，所有服務(wù)臺都被占用，然后離開，這就是所謂的即時系統(tǒng)(掛失系統(tǒng))；當(dāng)顧客到達(dá)時，所有的服務(wù)臺都被占用了，排隊等候被稱為等候系統(tǒng)。例如，普通本地電話的呼叫屬于即時系統(tǒng)；登記市外長途電話的呼叫屬于等候系統(tǒng)。輪候制度

5、的幾項規(guī)則是：先到先得服務(wù)是按到達(dá)的先后次序接受的，這是最常見的情況。先到先得。例如，乘電梯的顧客是第一個出來的；倉庫中儲存的厚鋼板；最終到達(dá)的有價值的信息處理。隨機(jī)服務(wù)是指服務(wù)員隨機(jī)選擇一個等待服務(wù)的顧客，而不考慮到達(dá)的順序。例如，電話交換機(jī)連接一部呼叫電話。優(yōu)先服務(wù)例如，醫(yī)院將優(yōu)先治療重病患者。(2)從占用空間的角度來看，隊列可以安排在特定的位置或抽象的位置。例如，在特定的場所有售票處和候車室；在采樣點，有一個電話打給電話交換機(jī)。(3)從隊列數(shù)量的角度來看，它可以是單列或多列。在多列的情況下，每列中的一些客戶可以相互轉(zhuǎn)移，而其他客戶則不能(例如，被繩子或欄桿隔開)。一些排隊的顧客由于等待時

6、間長而中途退出，而另一些人卻不能退出(例如高速公路上的汽車流)，必須堅持得到服務(wù)。3.根據(jù)組織形式和工作條件，服務(wù)組織有以下幾種情況：(1)服務(wù)組織可能沒有服務(wù)員或有一個或多個服務(wù)員(服務(wù)臺、通道、窗口等)。)。例如，在開架書店中，顧客選擇書籍時沒有服務(wù)員，但付款時可能不止一個服務(wù)員。(2)在多個服務(wù)臺的情況下，它們可以平行排列(并排)、前后排列(串聯(lián))或混合排列。例如，單一團(tuán)隊-單一服務(wù)臺的情況；多個團(tuán)隊-多個服務(wù)臺(并排)；單個團(tuán)隊-多個服務(wù)臺(并排)；多個服務(wù)臺(串聯(lián))；多個服務(wù)臺(混合)。(3)服務(wù)模式可以針對單個客戶，也可以針對一組客戶。例如，公共汽車分批為在站臺等候的顧客服務(wù)。(4

7、)確定和隨機(jī)服務(wù)時間。自動洗車設(shè)備的清洗(服務(wù))時間是確定的，但在大多數(shù)情況下，服務(wù)時間是隨機(jī)的。對于隨機(jī)服務(wù)時間，我們需要知道它的概率分布。(5)服務(wù)時間的分配。人們總是假設(shè)服務(wù)時間是穩(wěn)定的，即分布參數(shù)如期望值、平方和差值不受時間的影響。第四，排隊模型的分類1953年肯德爾提出了排隊模型的分類方法，它有三個最有影響的特征：(1)連續(xù)顧客之間的間隔時間分布；(2)服務(wù)時間的分配；(3)服務(wù)臺數(shù)量。對于并行多服務(wù)器的情況，用肯德爾符號表示：X/Y/Z，其中X表示連續(xù)到達(dá)間隔時間的分布；y代表服務(wù)時間的分布；z表示平行服務(wù)臺的數(shù)量。x和y的類型是：m(負(fù))指數(shù)分布；確定型；Ek k階的Erlang

8、分布；一般獨立的時間間隔分布；g .一般服務(wù)時間的分配。例如，M/M/1意味著連續(xù)到達(dá)之間的間隔時間是(負(fù))指數(shù)分布，服務(wù)時間是(負(fù))指數(shù)分布；單一服務(wù)臺模式；D/M/c代表一個有確定到達(dá)間隔的模型，(負(fù))指數(shù)分布的服務(wù)時間和c平行服務(wù)臺(但客戶是一個團(tuán)隊)。1971年，肯德爾符號將X/Y/Z擴(kuò)展為X/Y/Z/A/B/C。其中，前三個含義保持不變，后三個含義為：A代表系統(tǒng)容量限制；b代表客戶來源的數(shù)量m；代表服務(wù)規(guī)則，如先到先得(FCFS)和后到先得(LCFS)。還商定，如果省略最后三項，則指的是X/Y/Z/FCFS的情況。5.解決排隊問題解決排隊問題的目的是研究排隊系統(tǒng)的效率，估計服務(wù)質(zhì)量，

9、確定系統(tǒng)參數(shù)的最優(yōu)值，確定系統(tǒng)結(jié)構(gòu)是否合理，研究設(shè)計改進(jìn)措施。在排隊問題中，顧客到達(dá)時間和服務(wù)時間的分布需要由實際的測量數(shù)據(jù)來確定，當(dāng)問題被提出時，其他因素也被給出。排隊系統(tǒng)運行的基本量化指標(biāo)如下：1 .隊列領(lǐng)導(dǎo)和隊列領(lǐng)導(dǎo)是指系統(tǒng)中的客戶數(shù)量，其期望值記錄為最小二乘；排隊長度(Queue length)是指系統(tǒng)中排隊等待服務(wù)的顧客數(shù)量，其期望值記錄為LQ；系統(tǒng)中的客戶數(shù)量=隊列中等待服務(wù)的客戶數(shù)量。一般來說，團(tuán)隊領(lǐng)導(dǎo)(或隊列長度)越大，服務(wù)率就越低，而顧客最討厭的就是隊列中的成龍。2.停留時間和等待時間停留時間是指客戶在系統(tǒng)中的停留時間，其期望值記錄為WS；等待時間是指客戶在系統(tǒng)中排隊等待的時

10、間，其期望值記錄為WQ；停留時間=等待時間，服務(wù)時間3，忙期，忙期，是指從顧客到達(dá)空閑的服務(wù)機(jī)構(gòu)到服務(wù)機(jī)構(gòu)再次空閑的時間長度，即服務(wù)機(jī)構(gòu)持續(xù)的忙時間，與服務(wù)員的工作強(qiáng)度有關(guān)。繁忙期和在繁忙期內(nèi)完成服務(wù)的平均客戶數(shù)量都是衡量服務(wù)組織效率的指標(biāo)。4.系統(tǒng)狀態(tài)系統(tǒng)狀態(tài)是指系統(tǒng)中的客戶數(shù)量。如果系統(tǒng)中有N個客戶，則表示系統(tǒng)狀態(tài)為N，其可能值為：(1)當(dāng)隊長沒有限制時，n=0，1，2、(2)當(dāng)隊長有限制時，n=0，1，2、(3)即時系統(tǒng)，當(dāng)服務(wù)臺數(shù)量為c時，n=0，1。在后一種情況下，狀態(tài)n表示正在工作(忙碌)的服務(wù)臺數(shù)量。在時間t，系統(tǒng)狀態(tài)為n的概率由Pn(t)和計算狀態(tài)概率Pn(t)的方法表示。首先

11、，要建立的包含Pn(t)的關(guān)系式一般是微分差分方程(關(guān)于t的微分方程和關(guān)于n的差分方程)。方程的解是一個瞬態(tài)解。找到一個暫時的解決方案并不容易，即使找到了，也很難使用它。因此，經(jīng)常使用它的極限limt Pn(t)=Pn，這被稱為穩(wěn)態(tài)或統(tǒng)計平衡解。穩(wěn)態(tài)的物理意義是系統(tǒng)運行無限長時間后，初始(t=0)出發(fā)狀態(tài)的概率分布(Pn(0)，n0)的影響將消失，系統(tǒng)的狀態(tài)概率分布不再隨時間變化。t、Pn(t)、穩(wěn)態(tài)、瞬態(tài)、2。到達(dá)間隔和服務(wù)時間的分布。首先，用經(jīng)驗分布解決排隊問題，首先要根據(jù)原始數(shù)據(jù)對顧客到達(dá)間隔和服務(wù)時間間隔進(jìn)行經(jīng)驗分布，然后根據(jù)統(tǒng)計方法確定哪種理論分布，并估計其參數(shù)值。例1:1979年大

12、連港大港區(qū)500噸以上船舶到達(dá)的日記錄(不包括定期到達(dá)的船舶)如下。平均到達(dá)率=總到達(dá)次數(shù)/總天數(shù)=1271/365=3.48(船舶/天)。示例2服務(wù)組織是一個單一的服務(wù)臺，它以先到先得的方式提供服務(wù)。它記錄了41個客戶的到達(dá)時間和服務(wù)時間，總服務(wù)時間為127分鐘。2.泊松流3。指數(shù)分布。二郎分布3。指數(shù)分布的單服務(wù)器排隊系統(tǒng)分析。單服務(wù)器排隊系統(tǒng)的輸入過程服從泊松分布，服務(wù)時間服從指數(shù)分布。1.標(biāo)準(zhǔn)M/M/1模型(M/M/1/)標(biāo)準(zhǔn)M/M/1模型是指滿足以下條件的排隊系統(tǒng)：(1)輸入過程中的顧客來源是無限的，顧客是單獨來的，相互獨立。一定時間內(nèi)的到達(dá)次數(shù)服從泊松分布，到達(dá)過程是穩(wěn)定的。(2)

13、排隊規(guī)則單一，對隊長沒有限制，服務(wù)先到先得。(3)服務(wù)機(jī)構(gòu)只有一個服務(wù)臺，每個客戶的服務(wù)時間是獨立的，服從相同的指數(shù)分布。另外，假設(shè)到達(dá)間隔時間和服務(wù)時間彼此獨立。例1根據(jù)病人就診和手術(shù)完成的時間記錄，醫(yī)院手術(shù)室隨機(jī)抽取100個工作小時，每小時就診病人數(shù)n出現(xiàn)。另外隨機(jī)選擇100個病例，所用時間為v(小時)。其中，數(shù)據(jù)如下：不同第二，當(dāng)系統(tǒng)容量有限(M/M/1/N/)時，如果系統(tǒng)的最大容量是N，對于單個服務(wù)臺的情況，排隊等候的客戶的最大數(shù)量是N-1。當(dāng)客戶在某個時間到達(dá)時，如果系統(tǒng)中已經(jīng)有n個客戶，則拒絕該客戶進(jìn)入系統(tǒng)。當(dāng)N=1時，即時情況；當(dāng)n時，容量是無限的。接待處，排隊，顧客，被拒，排隊

14、系統(tǒng)，例2在一家理發(fā)店里有6把椅子，用來接待排隊理發(fā)的人。當(dāng)六把椅子都坐滿時，后來顧客沒有進(jìn)入商店就離開了。顧客的平均到達(dá)率是3人/小時，理發(fā)平均需要15分鐘。那么N=7是系統(tǒng)中客戶的最大數(shù)量，=3人/小時，=4人/小時。尋求：(1)顧客一到達(dá)就能理發(fā)的概率；(2)等待的顧客數(shù)量的期望值；(3)有效到達(dá)率；(4)顧客在理發(fā)店停留的預(yù)期時間；(5)在可能的顧客中不等待就離開的概率。3.當(dāng)客戶來源有限(M/M/1/m)時，假設(shè)有M臺機(jī)器(總客戶)，機(jī)器因故障而停止，表示“到達(dá)”，待維修的機(jī)器排成一列，修理工是服務(wù)員。如果同一臺機(jī)器發(fā)生故障(到達(dá))并得到修理(服務(wù)結(jié)束后)，它仍然可以發(fā)生故障并重新啟

15、動。M/M/1/m模型中的第四項是寫的，這意味著系統(tǒng)的容量沒有限制，但實際上它永遠(yuǎn)不會超過M，所以它與寫m/m/1/m/m有相同的含義。同樣，M打字員共用一臺打字機(jī)，M會計分析師共用一臺計算機(jī)終端。服務(wù)臺指數(shù)分布排隊系統(tǒng)分析，I .標(biāo)準(zhǔn)M/M/c模型(M/M/c/)標(biāo)準(zhǔn)M/M/c模型和標(biāo)準(zhǔn)M/M/1模型的各種特性同時，規(guī)定每個服務(wù)臺的工作相互獨立，平均服務(wù)率相同。例1售票處有三個窗口，顧客的到達(dá)服從泊松過程，平均每分鐘到達(dá)率為0.9(人)，服務(wù)(售票)時間服從指數(shù)分布，平均每分鐘服務(wù)率為0.4人?，F(xiàn)在，顧客到達(dá)后被排成一行，依次從免費窗口購票。這是一個M/M/c模型系統(tǒng)，其中c=3，/=2.25，=2.25/31。第二，當(dāng)系統(tǒng)容量有限時(M/M/c/N/)，讓系統(tǒng)的最大容量限制為N(c)。當(dāng)系統(tǒng)中的客戶數(shù)達(dá)到N(即隊列中的客戶數(shù)達(dá)到N-c)時，再來的客戶將被拒絕，其他條件與標(biāo)準(zhǔn)的M/M/c類型相同。例2:當(dāng)一個酒店要建在一個景點時，顧客的到達(dá)是泊松流，平均每天有()6個人，顧客的平