基于排隊(duì)論的食堂排隊(duì)問(wèn)題研究

基于排隊(duì)論的食堂排隊(duì)問(wèn)題研究

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