基于排隊論的食堂排隊問題研究

基于排隊論的食堂排隊問題研究

1.窗口數(shù)量的確定這就是經(jīng)常看到的情況。下課后，許多學(xué)生還跑到食堂買東西。在賣一個小的介餐室之前，一些學(xué)生坐在隊伍中，很快就聚集在長凳上。以前的混亂很快就變得荒涼了。饑腸咕嚕的同學(xué)們見到這種長蛇陣,怎能不怨聲載道。增加窗口數(shù)量,減少排隊等待時間,是學(xué)生們十分關(guān)心的問題。然而就食堂的角度來說,雖說增加窗口數(shù)量可以減少排隊等待時間,提高學(xué)生對該食堂的滿意度,從而贏得更多的學(xué)生到該食堂就餐,但是同時也會增加食堂的運營成本,因此如何在這兩者之間進行權(quán)衡,找到最佳的窗口數(shù)量,對學(xué)生和食堂雙方來說都是很重要的。排隊論是通過研究各種服務(wù)系統(tǒng)的排隊現(xiàn)象,解決服務(wù)系統(tǒng)最優(yōu)設(shè)計和最優(yōu)化控制的一門科學(xué)。本論文將根據(jù)食堂排隊狀況建立數(shù)學(xué)模型,運用排隊論的觀點進行分析,通過比較各方面因素的關(guān)系,為其擁擠狀況找到一個較合理的解決方案。2.多服務(wù)站點系統(tǒng)的數(shù)學(xué)模型2.1系統(tǒng)的響應(yīng)問題排隊論是研究排隊系統(tǒng)(又稱為隨機服務(wù)系統(tǒng))的數(shù)學(xué)理論和方法,是運籌學(xué)的一個重要分支。在日常生活中,人們會遇到各種各樣的排隊問題。排隊問題的表現(xiàn)形式往往是擁擠現(xiàn)象。排隊系統(tǒng)的符號一般形式為:X/Y/Z/A/B/C。其中:X表示顧客相繼到達時問間隔的分布;Y表示服務(wù)時間的分布;Z表示服務(wù)臺的個數(shù);A表示系統(tǒng)的容量,即可容納的最多顧客數(shù);B表示顧客源的數(shù)目;C表示服務(wù)規(guī)則。排隊論的基本問題是研究一些數(shù)量指標在瞬時或平穩(wěn)狀態(tài)下的概率分布及其數(shù)字特征,了解系統(tǒng)運行的基本特征;系統(tǒng)數(shù)量指標的統(tǒng)計推斷和系統(tǒng)的優(yōu)化問題等。當系統(tǒng)運行一定時間達到平穩(wěn)狀態(tài)后,對任一個狀態(tài)n來說,單位時間內(nèi)進入該狀態(tài)的平均次數(shù)和單位時間內(nèi)離開該狀態(tài)的平均次數(shù)應(yīng)相等,即系統(tǒng)在統(tǒng)計平衡下“流入=流出”。據(jù)此.可得任一狀態(tài)下的平衡方程如下:由上述平衡方程,可求得:平衡狀態(tài)的分布為:其中:注意:(3)式只有當級數(shù)收斂時才有意義,即當時,才能由上述公式得到平穩(wěn)狀態(tài)的概率分布。2.2總體平穩(wěn)分布設(shè)顧客單個到達,相繼到達的時間間隔服從參數(shù)為λ的指數(shù)分布,系統(tǒng)中共有S個服務(wù)員,每個服務(wù)臺的服務(wù)時間相互獨立,且服從參數(shù)為μ的指數(shù)分布。當顧客到達時,若有空閑的服務(wù)臺則可以馬上接受服務(wù),否則便排成一個隊列等待,等待空間為無限。下面討論這個排隊系統(tǒng)的平穩(wěn)分布。記:p=p{N=n}(n=0,1,2…)為系統(tǒng)達到平穩(wěn)狀態(tài)后隊長N的概率分布,注意到對個數(shù)為S的多服務(wù)臺系統(tǒng),有:公式(4)和公式(5)給出了在平衡條件下系統(tǒng)中顧客數(shù)為n的概率,當n≥s時,即系統(tǒng)中顧客數(shù)大于或等于服務(wù)臺個數(shù),這時再來的顧客必須等待,因此記:式(6)稱為Erlang等待公式,它給出了顧客到達系統(tǒng)時需要等待的概率。對多服務(wù)臺等待制排隊系統(tǒng),由已得到的平穩(wěn)分布可得平均排隊長Lq為:記系統(tǒng)中正在接受服務(wù)的顧客的平均數(shù)為,顯然也是正在忙的服務(wù)臺的平均數(shù),故:式(7)說明,平均在忙的服務(wù)臺個數(shù)不依賴于服務(wù)臺個數(shù)s,這是一個有趣的結(jié)果。由(7)式,可得到平均隊長L為:對多服務(wù)臺系統(tǒng),Little公式依然成立,即有平均逗留時間;平均等待時間。3.實例分析3.1校園體現(xiàn)了單一陣列優(yōu)先制3.1.1假定學(xué)生在高峰期這段時間達到的人數(shù)是無限的,并且依次以參數(shù)為λ的泊松過程達到,達到的時間間隔是隨機的,服從負指數(shù)分布。3.1.2每個服務(wù)窗口以并聯(lián)的方式連接,且每個窗口對學(xué)生來說都是一樣的,服務(wù)時間服從參數(shù)為μ的負指數(shù)分布。3.1.3食堂實行先來先服務(wù)原則,且學(xué)生可自由在隊列間進行轉(zhuǎn)移,并總向較短的隊進行轉(zhuǎn)移,沒有學(xué)生會因為隊列過長而離去,故可認為排隊方式是單一隊列等待制。由于周六周日學(xué)校沒課,故學(xué)生去食堂的時間較為分散,很少發(fā)生排長隊的現(xiàn)象,我們在此就不做分析了。我們僅就周一至周五的食堂擁擠情況進行分析。經(jīng)我們觀察發(fā)現(xiàn),一般打到飯的同學(xué)都能找到座位吃飯,故我們可認為,食堂的容納學(xué)生數(shù)是足夠的,所以解決食堂擁擠狀況,主要是解決排長隊與服務(wù)窗口的問題。我們統(tǒng)計了從某周一到周五11:45至12:15高峰期食堂的學(xué)生流分布情況:共統(tǒng)計了3059人次的數(shù)據(jù)(以10秒為一個時間單位),見下表:(部分數(shù)據(jù))表一由上表可得λ=3.39。經(jīng)檢驗,該分布近似于泊松分布。雖然我們僅僅調(diào)查了一周的數(shù)據(jù),但考慮到學(xué)生到食堂就餐具有較大的穩(wěn)定性,所以認為調(diào)查的數(shù)據(jù)還是較為可靠的。另外在非高峰時段很少發(fā)生排隊現(xiàn)象,故在此我們也不做分析。3.2顧客到達時,服務(wù)能力調(diào)查基于以上的假設(shè),我們的模型符合排隊論中的多服務(wù)臺等待模型(M/M/s)。該模型的特點是:服務(wù)系統(tǒng)中有s個窗口(即s個服務(wù)員),學(xué)生按泊松流來到服務(wù)系統(tǒng),到達強度為λ;服務(wù)員的能力都是μ,服務(wù)時間服從指數(shù)分布,每個顧客的平均服務(wù)時間。當顧客到達時,如果所有服務(wù)員都忙著,顧客便參加排隊,等待服務(wù),一直等到有服務(wù)員為他服務(wù)為止。由我們調(diào)查的數(shù)據(jù)可知λ=3.39,s=6(食堂現(xiàn)有窗口6個)代入以上各式可得:服務(wù)員能力:系統(tǒng)服務(wù)強度:,因為,所以極限存在。由此可見,當我們中午在11:45至12:15這個時間段去食堂吃飯時,一進門就會發(fā)現(xiàn)里面已經(jīng)人滿為患,幾乎不可能找到空閑的窗口。而且,已經(jīng)有32個同學(xué)正在排隊買飯。27個人正在排隊等待,平均一個窗口5人。當我們開始排隊時,要過80秒鐘才輪到我們,要過95秒鐘我們才能吃上可口的飯菜,來填飽我們的肚子。為了檢驗我們的數(shù)據(jù)與事實相符,我們特地親身體驗了一番,下表是我們的統(tǒng)計數(shù)據(jù):表二忽略那些隨機因素,我們得到的那些結(jié)論和實際數(shù)據(jù)還是較為符合的,可見我們的模型還是很成功的。3.3平均服務(wù)時間是個常數(shù)還是個一無所不生對于學(xué)生來說,中午的時間是很有限的,能盡快吃上飯對我們來說是很重要的。同時,學(xué)生在食堂排隊的平均逗留時間Wq很大程度上可以決定學(xué)生對食堂的選擇,所以食堂工作人員也希望能盡可能的滿足學(xué)生的需求。研究學(xué)生平均逗留時間Wq,將是解決本模型的關(guān)鍵所在。平均逗留時間Wq是由平均排隊時間W和平均服務(wù)時間組成。我們認為15秒的平均服務(wù)時間對于服務(wù)員來說已經(jīng)是極限了,如果再加快速度反而可能手忙腳亂,增大出錯的可能性,到時反而會降低效率,故我們認為平均服務(wù)時間不可改變,是個常數(shù)。至于平均排隊時間W,我們由公式可知它是由顧客到達強度λ,每個顧客的平均服務(wù)時間和窗口數(shù)s來決定的,由于學(xué)生對于食堂的選擇都有一定的偏好,即一般都會去同一個食堂吃飯,所以我們可以認為學(xué)生流是穩(wěn)定的,即λ為常數(shù),由上面的分析又可知也是常數(shù),因此能對平均排隊時間構(gòu)成影響的就只有窗口數(shù)s了,下面我們就s的取值對W的影響進行分析:由matlab我們可以得到它們兩者之間的散點圖:從圖中可看出我們各點之間的變化規(guī)律較為平穩(wěn),所以我們有可能用多次多項式將其擬合,所以我們又用matlab對其進行了三次多項式的擬合,從而得到了它們的擬合圖。它們之間的二次多項式關(guān)系式是:從圖中可以看出,隨著窗口數(shù)的增加,平均排隊等待時間急劇減少,當窗口數(shù)達到5以后時,變化趨于平緩。從擬合圖中,我們只能看出窗口數(shù)與平均排隊等待時間的大致關(guān)系,為了得到更精確的分析,我們將用靈敏度的觀點進行討論。由于窗口數(shù)s只能是整數(shù),我們得到如表三的對應(yīng)關(guān)系:表三(單位:秒)面=我們分析平均排隊時間對窗口數(shù)的靈敏度:靈敏度由此我們可得不同的窗口數(shù)s下的靈敏度:表四由此可見,平均排隊時間W對窗口數(shù)十分敏感,均達到了16以上,其中以窗口數(shù)從6變成7時尤為明顯,其平均排隊時間由27秒變?yōu)?.23秒。而其他幾種情況雖也很敏感,但是平均排隊時間變化的絕對值很小,大小不超過4秒鐘。3.4窗口費用wc由于對于學(xué)生方面來說,當然是排隊等待時間越短越好;而對于食堂方面來說,窗口數(shù)的增加一方面會導(dǎo)致成本的增加,帶來大的成本壓力;另一方面會縮短排隊時間,即意味著它能為更多學(xué)生服務(wù),所以它是否會增加窗口數(shù)就取決于成本和收益的大小關(guān)系。因此,需要對系統(tǒng)進行優(yōu)化,在成本和利益之間尋求可能有的平衡點。我們可以把該系統(tǒng)優(yōu)化表述為:尋求最佳的服務(wù)窗口數(shù)量s,使系統(tǒng)總費用C(s)最小。那么:minC(s)=CS?s+CW?L其中:s為并聯(lián)的窗口臺數(shù)量,C(s)是關(guān)于窗口臺數(shù)量的費用,SC是單位時間里平均每個窗口的費用,WC為平均每個學(xué)生在系統(tǒng)中等待(或逗留)單位時間的等待損失,L是平均隊長。在理論上,上述目標函數(shù)存在著優(yōu)化解。一般來說,每增加一個窗口,需要多配備一名服務(wù)人員以及一些配套的設(shè)施。所以增加窗口數(shù)所帶來的成本等于新增服務(wù)人員的工資加上配套設(shè)施的維修與清洗費。新增窗口得到的收益是很難估量的。在此我們引入等待損失的概念,即由于排隊等待食堂所減少的收益,得到等待損失等于食堂單位時間收益乘以平均等待時間乘以顧客數(shù)。我們調(diào)查得知服務(wù)人員的每月平均工資為700元,即每周平均175元。至于配套設(shè)施的維修與清洗,我們可大致認為其每周不超過300元。由此可知每增加一個窗口,食堂的成本就得增加825元。至于食堂從每個學(xué)生身上可獲得多少利潤,因為學(xué)生要的菜不同,而且菜的利潤也不同,所以是很難確定的,故我們由一般規(guī)律假定其每十秒鐘可得0.5元利潤。所以,學(xué)生因等待而使食堂發(fā)生的損失C=0.3×3059W,當窗口數(shù)從6變?yōu)?時,食堂可少損失?C=0.1×3059×?W=0.5×3059×(2.7-0.523)=3329.72元。由此可知最佳的窗口數(shù)為7。由概率分布的要求:,有:,于是:。λn=λ,n=0,1,2…,和,