基于顏色Petri網(wǎng)的食堂窗口排隊(duì)模擬仿真

鄧雪峰 侯益明 馮靈清

摘? ?要：食堂窗口是高校中排隊(duì)現(xiàn)象最普遍的服務(wù)窗口，在就餐高峰期容易出現(xiàn)排長(zhǎng)隊(duì)的情況。文章對(duì)高校食堂的4個(gè)服務(wù)窗口進(jìn)行了實(shí)地的調(diào)查，發(fā)現(xiàn)高校食堂窗口的平均到達(dá)率為1.3，平均服務(wù)率為0.672 413 793，平均隊(duì)長(zhǎng)為3.741 935 485，在此基礎(chǔ)上，利用CPN Tools工具對(duì)食堂的排隊(duì)情況進(jìn)行動(dòng)態(tài)仿真與監(jiān)測(cè)。經(jīng)實(shí)驗(yàn)證明，在可控制的誤差范圍內(nèi)，該模型可以有效地對(duì)高校食堂的排隊(duì)情況進(jìn)行模擬仿真。

關(guān)鍵詞：顏色Petri網(wǎng);食堂窗口;CPN Tools

隨著中國(guó)教育規(guī)模的擴(kuò)大，高校的各項(xiàng)服務(wù)設(shè)施的流程優(yōu)化可以提升服務(wù)窗口的服務(wù)效率，從而滿足日益增長(zhǎng)的消費(fèi)需求。在大學(xué)的服務(wù)設(shè)施中，食堂是一個(gè)重要的服務(wù)窗口，食堂的排隊(duì)亂一直是大學(xué)食堂廣泛存在的現(xiàn)象[1-2]，在就餐高峰期如何優(yōu)化排隊(duì)、提升食堂的服務(wù)效率一直是一個(gè)值得研究的問題。

排隊(duì)論是一種對(duì)排隊(duì)現(xiàn)象進(jìn)行分析的數(shù)學(xué)方法，排隊(duì)論的思想已經(jīng)用于多種領(lǐng)域，如計(jì)算機(jī)系統(tǒng)[3]、物流管理[4]、醫(yī)院管理[5]、通信系統(tǒng)[6]、遠(yuǎn)程服務(wù)系統(tǒng)[7]等。排隊(duì)系統(tǒng)同樣也可以用于對(duì)食堂排隊(duì)現(xiàn)象進(jìn)行分析。排隊(duì)系統(tǒng)的仿真可以模擬研究當(dāng)前排隊(duì)系統(tǒng)的相關(guān)特性，動(dòng)態(tài)地模擬排隊(duì)過程，有助于分析排隊(duì)系統(tǒng)的性能[8]。顏色Petri網(wǎng)[9]（Color Petri Nets，CPN）是一種形式化的建模方法，通過CPN可以簡(jiǎn)化建模過程，并且可以利用CPN Tools等工具對(duì)模型進(jìn)行仿真運(yùn)行。本文利用顏色Petri網(wǎng)對(duì)食堂排隊(duì)系統(tǒng)進(jìn)行建模并仿真，根據(jù)食堂的排隊(duì)實(shí)際數(shù)據(jù)模擬出食堂的排隊(duì)情況，從而為食堂排隊(duì)窗口的優(yōu)化管理提供一種模擬仿真的方法。

1? ? 食堂排隊(duì)過程

1.1? 食堂排隊(duì)系統(tǒng)的組成

一個(gè)排隊(duì)系統(tǒng)一般由系統(tǒng)的輸入過程、系統(tǒng)的排隊(duì)規(guī)則以及系統(tǒng)服務(wù)窗口的服務(wù)方式組成。一個(gè)典型的食堂排隊(duì)系統(tǒng)如圖1所示。

食堂排隊(duì)系統(tǒng)的輸入過程是一個(gè)隨機(jī)的過程，一般來(lái)說，食堂就餐顧客的到達(dá)服從指數(shù)分布，到達(dá)每一個(gè)服務(wù)窗口的顧客服從泊松分布，食堂排隊(duì)系統(tǒng)的排隊(duì)方式一般服從先來(lái)先服務(wù)的原則。

1.2? 食堂排隊(duì)系統(tǒng)的服務(wù)流程

食堂排隊(duì)系統(tǒng)的一般流程為：食堂的排隊(duì)分為有排隊(duì)情況和無(wú)排隊(duì)情況兩種，當(dāng)顧客當(dāng)達(dá)時(shí)，如果有排隊(duì)的隊(duì)列，則到達(dá)的顧客服從先來(lái)先服務(wù)的原則，到隊(duì)尾進(jìn)行排隊(duì)，等待隊(duì)列前無(wú)顧客進(jìn)行服務(wù)，當(dāng)顧客到達(dá)時(shí)，如果沒有排隊(duì)的現(xiàn)象，則直接穿過空隊(duì)列進(jìn)行服務(wù)，此時(shí)，不存在排隊(duì)模型，因此，也無(wú)需進(jìn)行優(yōu)化。當(dāng)顧客到達(dá)較為密集時(shí)，將會(huì)出現(xiàn)排長(zhǎng)隊(duì)和等待時(shí)間過長(zhǎng)的問題，此時(shí)，就需要根據(jù)實(shí)際情況進(jìn)行窗口的設(shè)置與排隊(duì)系統(tǒng)的優(yōu)化。

2? ? 食堂排隊(duì)系統(tǒng)建模

2.1? 顏色Petri網(wǎng)簡(jiǎn)介

顏色Petri網(wǎng)是一種以Petri網(wǎng)為基礎(chǔ)發(fā)展起來(lái)的高級(jí)網(wǎng)絡(luò)系統(tǒng)，與謂詞Petri網(wǎng)有著同樣重要的作用，可以對(duì)離散的事件進(jìn)行模擬仿真，并進(jìn)行性質(zhì)分析及狀態(tài)空間的分析。顏色Petri網(wǎng)定義為六元組∑=（P，T;F，C，I，M0），（P，T;F）為有向網(wǎng)，為∑的基礎(chǔ)網(wǎng);C為顏色集，在本文中采用了賦時(shí)顏色集、整數(shù)顏色集等顏色集;I分為I﹢和I﹣，代表P×T是正函數(shù)和負(fù)函數(shù);M0代表托肯色。

2.2? 排隊(duì)系統(tǒng)模型建立

排隊(duì)系統(tǒng)的模型有到達(dá)和服務(wù)兩部分。（1）到達(dá)部分：由P1，P2，T1，P3，T2組成;（2）服務(wù)部分：由P6，P3，P4，T3，P5，T4組成，P3是排隊(duì)狀態(tài)，屬于到達(dá)與服務(wù)的分界線，在本系統(tǒng)中用到的顏色集部分及函數(shù)如表1所示。

食堂排隊(duì)系統(tǒng)的模型如圖2所示，其中，P1—P2產(chǎn)生服從于作業(yè)到達(dá)情況的隨機(jī)數(shù);在P2—P3過程中，進(jìn)行隊(duì)列的排隊(duì)過程;當(dāng)系統(tǒng)處于P4空閑時(shí)期時(shí)，到達(dá)的作業(yè)直接進(jìn)行服務(wù);當(dāng)系統(tǒng)處于P5的忙碌時(shí)期時(shí)，到達(dá)的作業(yè)根據(jù)先來(lái)先服務(wù)原則到隊(duì)尾進(jìn)行排隊(duì);直至系統(tǒng)處于P4的空閑時(shí)間進(jìn)行服務(wù)，通過T4服務(wù)完成。表2闡述了每一個(gè)庫(kù)所和變遷的實(shí)際意義。

3? ? 排隊(duì)系統(tǒng)模型模擬分析

3.1? 模擬

在高校的食堂中，用餐高峰期，各個(gè)食堂窗口前會(huì)有學(xué)生排成長(zhǎng)隊(duì)等待打飯的情況，許多同學(xué)打飯時(shí)選擇就餐的飯菜是由哪個(gè)窗口排隊(duì)的人比較少?zèng)Q定的，有的隊(duì)伍會(huì)出現(xiàn)打飯時(shí)間過長(zhǎng)的問題。本文通過對(duì)某高校的食堂的排隊(duì)情況進(jìn)行實(shí)地調(diào)查，以1 min為單位時(shí)間，以4個(gè)窗口為調(diào)查對(duì)象，發(fā)現(xiàn)高校食堂很少存在學(xué)生排隊(duì)過程中離去的狀況，即窗口顧客的損失機(jī)制幾乎為0。通過監(jiān)測(cè)發(fā)現(xiàn)，高校食堂窗口的平均到達(dá)率為1.3，平均服務(wù)率為0.672 413 793，平均對(duì)長(zhǎng)為3.741 935 485。在不考慮插隊(duì)和損失的情況下，對(duì)高校食堂排隊(duì)的隊(duì)長(zhǎng)進(jìn)行約1 h的模擬，一般高校中午的就餐高峰時(shí)間約為1 h，隊(duì)長(zhǎng)的模擬情況如圖3所示，CPN Tools可以通過顏色集及時(shí)間戳的方式對(duì)該模型進(jìn)行有效的監(jiān)督，動(dòng)態(tài)性地證明了該模型的有效性。

3.2? 分析

通過對(duì)模擬情況與實(shí)際情況的對(duì)比分析得到表3，通過表3得出，模擬總計(jì)隊(duì)長(zhǎng)74，實(shí)際總計(jì)隊(duì)長(zhǎng)78，隊(duì)長(zhǎng)總和相差4人，誤差總隊(duì)長(zhǎng)占實(shí)際總隊(duì)長(zhǎng)的5.1%，模擬平均隊(duì)長(zhǎng)4.153 479，約4人，實(shí)際平均隊(duì)長(zhǎng)3.741 935 485，約4人，在可控的誤差范圍內(nèi)，該模型可以有效地描述高校食堂的排隊(duì)模型。

4? ? 結(jié)語(yǔ)

本文通過顏色Petri網(wǎng)對(duì)食堂的排隊(duì)模型進(jìn)行建模并利用CPN Tools工具對(duì)高校食堂的排隊(duì)情況進(jìn)行模擬，將排隊(duì)論的理論模型有效地應(yīng)用于食堂的排隊(duì)系統(tǒng)中，并對(duì)食堂的排隊(duì)情況進(jìn)行動(dòng)態(tài)的仿真。仿真實(shí)驗(yàn)結(jié)果表明，本方法可以對(duì)食堂的排隊(duì)情況進(jìn)行有效的仿真模擬，可以利用仿真的結(jié)果為食堂的管理提供排隊(duì)情況的動(dòng)態(tài)預(yù)測(cè)分析，從而更加方便、可視地對(duì)食堂窗口進(jìn)行管理控制，最大限度地提高食堂排隊(duì)系統(tǒng)的利用率。

[參考文獻(xiàn)]

[1]李欣，肖芳園，楊牡丹.高校食堂排隊(duì)模型的研究[J].現(xiàn)代物業(yè)（上旬刊），2012（10）：37-39.

[2]郝洵.學(xué)生食堂就餐動(dòng)態(tài)過程的數(shù)學(xué)模型及仿真研究[J].武漢理工大學(xué)學(xué)報(bào)，2008（6）：20-22.

[3]佚名.基于排隊(duì)論的級(jí)聯(lián)交換機(jī)網(wǎng)絡(luò)傳輸延遲分析[J].西北工業(yè)大學(xué)學(xué)報(bào)，2017（2）：40-42.

[4]張河山.排隊(duì)論在集裝箱堆場(chǎng)進(jìn)場(chǎng)閘口管理中的應(yīng)用[J].集裝箱化，2017（10）：18-22.

[5]佚名.基于排隊(duì)論的患者預(yù)約容量分配研究[J].湘潭大學(xué)自然科學(xué)學(xué)報(bào)，2017（2）：6-7.

[6]安然.基于排隊(duì)論的數(shù)據(jù)通信網(wǎng)絡(luò)性能優(yōu)化[J].信息通信，2017（4）：5-6.

[7]暴希會(huì)，吳長(zhǎng)奇，白樺，等.遠(yuǎn)程故障診斷系統(tǒng)的排隊(duì)論分析[J].無(wú)線電通信技術(shù)，2007（3）：25-27.

[8]吳可嘉.蒙特卡洛法在解決食堂窗口排隊(duì)問題上的應(yīng)用[J].大連海事大學(xué)學(xué)報(bào)，2007（z1）：11-13.

[9]袁崇義.Petri網(wǎng)原理與應(yīng)用[M].北京：電子工業(yè)出版社，2005.