排隊(duì)論的應(yīng)用

1、排隊(duì)論的應(yīng)用食堂排隊(duì)問(wèn)題劉文驍摘要本文通過(guò)運(yùn)籌學(xué)中排隊(duì)論的方法，為食堂排隊(duì)問(wèn)題建立模型，研究學(xué)生排隊(duì)就餐時(shí)間節(jié)約的影響因素，通過(guò)簡(jiǎn)單計(jì)算，得出影響最大因素。排隊(duì)論是通過(guò)研究各種服務(wù)系統(tǒng)的排隊(duì)現(xiàn)象，解決服務(wù)系統(tǒng)最優(yōu)設(shè)計(jì)和最優(yōu)化控制的一門(mén)科學(xué)。本文將根據(jù)食堂排隊(duì)狀況建立數(shù)學(xué)模型，運(yùn)用排隊(duì)論的觀點(diǎn)進(jìn)行分析，找出可以減少排隊(duì)時(shí)間的最大影響因素。關(guān)鍵詞排隊(duì)論；M/M/s模型；食堂排隊(duì)引言在學(xué)校里，常?？梢钥吹竭@樣的情況：下課后，許多同學(xué)正想跑到食堂買(mǎi)飯，小小的買(mǎi)飯窗口前沒(méi)過(guò)幾分鐘便排成了長(zhǎng)長(zhǎng)的隊(duì)伍，本來(lái)空蕩蕩的食堂立即變得擁擠不堪。饑腸轆轆的學(xué)生門(mén)見(jiàn)到這種長(zhǎng)蛇陣，怎能不怨聲載道。減少排隊(duì)等待時(shí)間，是學(xué)生

2、們十分關(guān)心的問(wèn)題。.多服務(wù)臺(tái)排隊(duì)系統(tǒng)的數(shù)學(xué)模型排隊(duì)論及M/M/s模型排隊(duì)論是研究排隊(duì)系統(tǒng)（又稱(chēng)為隨即服務(wù)系統(tǒng)）的數(shù)學(xué)理論和方法，是運(yùn)籌學(xué)的一個(gè)重要分支。在日常生活中，人們會(huì)遇到各種各樣的排隊(duì)問(wèn)題。排隊(duì)問(wèn)題的表現(xiàn)形式往往是擁擠現(xiàn)象。排隊(duì)系統(tǒng)的一般形式符號(hào)為：X/Y/Z/A/B/C。其中：X表示顧客相繼到達(dá)時(shí)間間隔的分布;Y表示服務(wù)時(shí)間的分布；Z表示服務(wù)臺(tái)的個(gè)數(shù)；A表示系統(tǒng)的容量，即可容納的最多顧客數(shù)；B表示顧客源的數(shù)目；C表示服務(wù)規(guī)則。排隊(duì)論的基本問(wèn)題是研究一些數(shù)量指標(biāo)在瞬時(shí)或平穩(wěn)狀態(tài)下的概率分布及其數(shù)字特征，了解系統(tǒng)運(yùn)行的基本特征；系統(tǒng)數(shù)量指標(biāo)的統(tǒng)計(jì)推斷和系統(tǒng)的優(yōu)化問(wèn)題等。當(dāng)系統(tǒng)運(yùn)行一定時(shí)間達(dá)

3、到平穩(wěn)后，對(duì)任一狀態(tài)n來(lái)說(shuō)，單位時(shí)間內(nèi)進(jìn)入該狀態(tài)的平均次數(shù)和單位時(shí)間內(nèi)離開(kāi)該狀態(tài)的平均次數(shù)應(yīng)相等，即系統(tǒng)在統(tǒng)計(jì)平衡下“流上流出據(jù)此，可得任一狀態(tài)下的平衡方程如下：°：眄出=入網(wǎng)4網(wǎng)+"必=(4必:4必十問(wèn)死一(4+外)小"一八n:4TpM+凡通m=(4+mJp.由上述平衡方程，可求的:平衡狀態(tài)的分布為：Pn=CnP0,n=1,2,(1)其中：Cn1nx,n=1,2,.nn41QO有概率分布的要求：ZPn=1,有:n=fi1一Cnp0=1,n=0Po=1-(3)'Cnn-0注意：(3)式只有當(dāng)級(jí)數(shù)qQ£Cn收斂時(shí)才有意義，即當(dāng)n=o00CCn0&#

4、176;時(shí)才能由上n工述公式得到平穩(wěn)狀態(tài)的概率分布M/M/s等待制多服務(wù)臺(tái)模型設(shè)顧客單個(gè)到達(dá)，相繼到達(dá)的時(shí)間問(wèn)隔服從參數(shù)為九的指數(shù)分布，系統(tǒng)中具有S個(gè)服務(wù)員，每個(gè)服務(wù)臺(tái)的服務(wù)時(shí)間相互獨(dú)立，且服從參數(shù)為N的指數(shù)分布。當(dāng)顧客到達(dá)時(shí)，若有空閑的服務(wù)臺(tái)則可以馬上接受服務(wù)，否則便排成一個(gè)隊(duì)列等待，等待空間為無(wú)限。(n=0,1,2,)為卜面討論這個(gè)排隊(duì)系統(tǒng)的平穩(wěn)分布：即p=pN=n系統(tǒng)達(dá)到平穩(wěn)狀態(tài)后隊(duì)長(zhǎng)N的概率分布,注意到對(duì)個(gè)數(shù)為S的多服務(wù)臺(tái)系統(tǒng),有:，-n=九,n=0,1,2,，和士=則當(dāng)P<1時(shí)，由(1)式，式,n!1nP0Pnns式,n=1,2,sn=0,1,2,n=s,s1,仔：(4)ss1

5、n_ss!sP0n-s其中：P0Ai=0i!)n!(n-P)公式(4)和公式(5)給出了在平和條件下系統(tǒng)中顧客數(shù)為n的概率，當(dāng)n之s時(shí),即系統(tǒng)中顧客數(shù)大于或等于服務(wù)臺(tái)的個(gè)數(shù)，這時(shí)來(lái)的顧客必須等待，因此即:二；scs,：="Pn=P0(6)n3s!1-：飛(6)式成為Erlang等待公式，它給出了顧客到達(dá)系統(tǒng)是需要等待的概率。對(duì)多服務(wù)臺(tái)等待制排隊(duì)系統(tǒng)，由已得到的平穩(wěn)分布可得平均排隊(duì)長(zhǎng)Lq為：QOLq=，n-Spn=n1P0:ss!QO'、n-s：；n-SP0Psd仁門(mén)n）P0Psps;n-乙ss2s!dPswsa（1-Ps）記系統(tǒng)中正在接受服務(wù)的顧客的平均數(shù)為s,顯然s也是正在

6、忙的服務(wù)臺(tái)的平均數(shù)，故：_w/。ftp*p'S=二叩出十之凡二二；必.八M著M知0QQ-1二叩E(卜(7)式說(shuō)明平均在忙的服務(wù)臺(tái)個(gè)數(shù)不依賴(lài)于服務(wù)臺(tái)個(gè)數(shù)S,這時(shí)一個(gè)特殊的結(jié)果。由(7)式，可得到平均隊(duì)長(zhǎng)L為：L二平均排隊(duì)長(zhǎng)+正在接受服務(wù)的顧客的平均數(shù)=Lq十P對(duì)多服務(wù)臺(tái)系統(tǒng)，Uttle公式依然成立。即有平均逗留時(shí)間W=1;平均等待九Lq1時(shí)Hjwq='=w。.實(shí)例分析模型假說(shuō)假定學(xué)生在高峰期這段時(shí)間達(dá)到的人數(shù)是無(wú)限的，并且一次以參數(shù)九的泊松過(guò)程達(dá)到，達(dá)到的時(shí)間間隔是隨機(jī)的，服從負(fù)指數(shù)分布。每個(gè)服務(wù)窗口以并聯(lián)的方式連接，且每個(gè)窗口對(duì)學(xué)生來(lái)說(shuō)都是一樣的，服務(wù)時(shí)間服從參數(shù)為N的負(fù)指數(shù)分

7、布。食堂實(shí)行先來(lái)先服務(wù)原則，且學(xué)生可自由在隊(duì)列間進(jìn)行轉(zhuǎn)移，并總向最短的對(duì)轉(zhuǎn)移，沒(méi)有學(xué)生會(huì)因?yàn)殛?duì)列過(guò)長(zhǎng)而離去，故可認(rèn)為排隊(duì)方式是單一隊(duì)列等待制。一般打到飯的同學(xué)都能找到座位吃飯，故我們可認(rèn)為，食堂的可容納學(xué)生數(shù)是足夠的，所以解決食堂的擁擠現(xiàn)象，主要是解決排長(zhǎng)隊(duì)與服務(wù)窗口的問(wèn)題。以下數(shù)據(jù)來(lái)源于網(wǎng)絡(luò)（作者：李晟源）高峰期食堂的學(xué)生流分布情況：共統(tǒng)計(jì)了3059人次的數(shù)據(jù)（以10秒為一個(gè)單位），見(jiàn)下表：表一每10秒到達(dá)人數(shù)123457頻數(shù)257441894956350161由概率論的知識(shí)可知，若分布滿足工=士，則該分布為泊松分布。（其中PkPkk為泊松分布的密度，丸為泊松分布的參數(shù)）由上表可知人=3.3

8、9。模型建立及求解基于以上的假設(shè)，我們的模型符合排隊(duì)論中的多服務(wù)臺(tái)等待模型（M/M/s）.該模型的特點(diǎn)是：服務(wù)系統(tǒng)中有s個(gè)窗口（即s個(gè)服務(wù)員），學(xué)生按泊松流來(lái)到服務(wù)系統(tǒng)，到達(dá)強(qiáng)度為兒；服務(wù)員的能力都是N,服務(wù)時(shí)間服從指數(shù)分布，每個(gè)顧客的平均服務(wù)時(shí)間to當(dāng)顧客到達(dá)時(shí)，如果所有服務(wù)員都忙著，顧客便參加排隊(duì)等待服務(wù)，一直等到有服務(wù)員為他服務(wù)為止。由我的調(diào)查數(shù)據(jù)可知人=3.39,t=1.5,s=6（食堂現(xiàn)有窗口6個(gè)）帶入以上各式可得：.八，1服務(wù)員能力：/=1=0.67t509、一.系統(tǒng)服務(wù)強(qiáng)度：P=-=5.09,因?yàn)镻s=5*=0.85<1,所以極限存在?？趕61fnpi)pn平_空閑概率：P

9、0=|l£+=0.031gi!Jn!(n-P)_PcPSP系統(tǒng)中排隊(duì)顧客的平均數(shù)：Lq=P0s2=27a1-：sL顧客平均排隊(duì)時(shí)間：Wq='=2=7.96q-3.39顧客平均逗留時(shí)間：Wa=Wt=7.961.5=9.46q系統(tǒng)中顧客的平均數(shù)：L=Lq。=275.09=32.09q由此可見(jiàn)，當(dāng)我們?cè)谶@個(gè)時(shí)間段去食堂吃飯時(shí)，一進(jìn)門(mén)就會(huì)發(fā)現(xiàn)里面已經(jīng)是人滿為患了，幾乎不可能找到空閑的窗口。而且，已經(jīng)有32個(gè)同學(xué)在排隊(duì)買(mǎi)飯，27個(gè)人這在排隊(duì)等待，平均一個(gè)窗口5人。當(dāng)我們開(kāi)始排隊(duì)時(shí)要過(guò)80秒鐘才輪到我們，要過(guò)95秒鐘才能吃到可口的飯菜，來(lái)填飽我們的肚子。2.3模型分析對(duì)于學(xué)生來(lái)說(shuō)中午的時(shí)

10、間是很有限的，能盡快吃上飯對(duì)我們來(lái)說(shuō)是很重要的。同時(shí)，學(xué)生在食堂的排隊(duì)的平均逗留時(shí)間Wq很大程度上可以決定學(xué)生對(duì)食堂的選擇，所以食堂的工作人員也希望盡可能的滿足學(xué)生的要求。研究學(xué)生平均逗留時(shí)間Wq將是解決本模型的關(guān)鍵所在，平均逗留時(shí)間Wq是由平均排隊(duì)時(shí)間Wqq和平均服務(wù)時(shí)間t組成。我個(gè)人認(rèn)為15秒的平均服務(wù)時(shí)間t對(duì)于服務(wù)員來(lái)說(shuō)已經(jīng)是極限了，如果在加快速度反而可能手忙腳亂，增大出錯(cuò)的可能性，到時(shí)反而會(huì)降低效率，一次我認(rèn)為平均服務(wù)時(shí)間t不可改變，是個(gè)常數(shù)。至于平均排隊(duì)時(shí)間W我們有公式可知它由顧客到達(dá)強(qiáng)度兒,每個(gè)顧客的平均服務(wù)時(shí)間和窗口數(shù)S來(lái)決定的，由于學(xué)生對(duì)食堂的選擇有一定的偏好，即一般都會(huì)去同一個(gè)食堂吃飯，因此我們可以認(rèn)為學(xué)生流是穩(wěn)定的，即人為常數(shù)，由上面的分析可知t也是常數(shù)因此能對(duì)平均排隊(duì)時(shí)間構(gòu)成影響的就只有窗口S了。對(duì)于我們大學(xué)食堂，每層12