排隊論的應用

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

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

3、到平穩(wěn)后，對任一狀態(tài)n來說，單位時間內進入該狀態(tài)的平均次數(shù)和單位時間內離開該狀態(tài)的平均次數(shù)應相等，即系統(tǒng)在統(tǒng)計平衡下“流上流出據(jù)此，可得任一狀態(tài)下的平衡方程如下：°：眄出=入網(wǎng)4網(wǎng)+"必=(4必:4必十問死一(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)式只有當級數(shù)qQ£Cn收斂時才有意義，即當n=o00CCn0&#

4、176;時才能由上n工述公式得到平穩(wěn)狀態(tài)的概率分布M/M/s等待制多服務臺模型設顧客單個到達，相繼到達的時間問隔服從參數(shù)為九的指數(shù)分布，系統(tǒng)中具有S個服務員，每個服務臺的服務時間相互獨立，且服從參數(shù)為N的指數(shù)分布。當顧客到達時，若有空閑的服務臺則可以馬上接受服務，否則便排成一個隊列等待，等待空間為無限。(n=0,1,2,)為卜面討論這個排隊系統(tǒng)的平穩(wěn)分布：即p=pN=n系統(tǒng)達到平穩(wěn)狀態(tài)后隊長N的概率分布,注意到對個數(shù)為S的多服務臺系統(tǒng),有:，-n=九,n=0,1,2,，和士=則當P<1時，由(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的概率，當n之s時,即系統(tǒng)中顧客數(shù)大于或等于服務臺的個數(shù)，這時來的顧客必須等待，因此即:二；scs,：="Pn=P0(6)n3s!1-：飛(6)式成為Erlang等待公式，它給出了顧客到達系統(tǒng)是需要等待的概率。對多服務臺等待制排隊系統(tǒng)，由已得到的平穩(wěn)分布可得平均排隊長Lq為：QOLq=，n-Spn=n1P0:ss!QO'、n-s：；n-SP0Psd仁門n）P0Psps;n-乙ss2s!dPswsa（1-Ps）記系統(tǒng)中正在接受服務的顧客的平均數(shù)為s,顯然s也是正在

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

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

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

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

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