王穎俐，王 飛，謝文丹

(長治學(xué)院 數(shù)學(xué)系,山西 長治 046011)

排隊系統(tǒng)也稱隨機服務(wù)系統(tǒng),是一種比較典型的離散動態(tài)系統(tǒng),是為了研究“服務(wù)”系統(tǒng)因“需求”擁擠從而產(chǎn)生排隊現(xiàn)象,以及合理的協(xié)調(diào)“需要”與“服務(wù)”關(guān)系的數(shù)學(xué)理論,是運籌學(xué)的一個重要分支.它適用于幾乎所有的服務(wù)系統(tǒng),如通信系統(tǒng)、銀行的叫號服務(wù)系統(tǒng)、醫(yī)院的排隊系統(tǒng)、購票系統(tǒng)、超市的收銀服務(wù)系統(tǒng)等.其中,對超市收銀服務(wù)系統(tǒng)的優(yōu)化問題是當(dāng)今排隊論應(yīng)用的熱點研究課題之一.

近年來,我國超市的規(guī)模發(fā)展迅速,顧客數(shù)量劇增使得超市結(jié)賬排隊的現(xiàn)象日益嚴重,等待時間過久會導(dǎo)致顧客滿意度下降.優(yōu)化排隊系統(tǒng),提供更加快速的收銀服務(wù)是超市經(jīng)營者的必然選擇.目前已有些學(xué)者運用數(shù)學(xué)建模的方法得到一些成果,見文獻[1，2]所示.但超市的收銀服務(wù)系統(tǒng)是一個動態(tài)的多服務(wù)臺等待制的隨機服務(wù)系統(tǒng),計算和實驗方法對該問題可以得到較好的結(jié)論.本文引入M/M/c/∞排隊模型,運用離散事件系統(tǒng)的仿真方法——事件調(diào)度法對超市收銀服務(wù)系統(tǒng)進行模擬仿真,并與理論值進行比較.

1 M/M/c/∞排隊模型

根據(jù)超市收銀服務(wù)系統(tǒng)的特征,引入一個多服務(wù)單到達M/M/c/∞排隊系統(tǒng)[3],其運行規(guī)則如下:

顧客以參數(shù)為λ(λ>0)的速率泊松到達,λ為單位時間內(nèi)的顧客平均到達量.當(dāng)顧客到達時,若服務(wù)臺空閑,則立即接受服務(wù);否則排隊等待,直到服務(wù)臺空閑再接受服務(wù).每位顧客接受完服務(wù)后就立即離開系統(tǒng),且服務(wù)原則遵循先到先服務(wù).

2 排隊系統(tǒng)活動流程及仿真程序流程分析

首先,分析顧客從進入排隊系統(tǒng)到離開系統(tǒng)的過程.當(dāng)一個顧客到達后,先判斷當(dāng)前系統(tǒng)中哪個隊列最短,然后加入到該隊列中.若此時隊列為空,且該收銀臺的狀態(tài)為閑,則立即接受服務(wù);否則,需等待.在等待過程中,隊首顧客接受完服務(wù)立即離開排隊系統(tǒng),收銀臺的狀態(tài)此時為閑,從而該隊顧客排隊位置前移,下一位顧客接受服務(wù),收銀臺的狀態(tài)此時為忙.如此循環(huán),直到該顧客到達隊首,且收銀臺為閑時,才能接受服務(wù)離開系統(tǒng).

其次,根據(jù)排隊系統(tǒng)內(nèi)顧客的到達事件與離去事件之間的關(guān)系,可采用仿真策略中的事件調(diào)度法[5],即:當(dāng)仿真程序運行時,由時鐘控制程序?qū)⒎抡鏁r刻推進到最早的事件發(fā)生的時刻,進而調(diào)用相應(yīng)事件的處理程序.

在仿真程序中有四個必不可少的模塊.系統(tǒng)的初始模塊,用來設(shè)置各種參數(shù);顧客的到達處理模塊,用來記錄每位顧客的到達時間、系統(tǒng)的隊長,以及選擇收銀臺的程序,若顧客加入的隊列為忙,則調(diào)用等待處理模塊;顧客的等待處理模塊,當(dāng)有顧客加入時,等待隊長數(shù)加1,該隊隊首顧客接受完服務(wù)時,顧客的位置前移,直至隊首,可求得顧客的等待時間和等待隊長;顧客的離去處理模塊,用來記錄顧客離開的時刻,以及此時系統(tǒng)隊長,并置收銀臺的狀態(tài)為閑.顧客的到達流程圖及離去流程圖為圖1、圖2所示.

圖1 顧客到達的程序操作流程圖2 顧客離去的程序操作流程

算法描述:系統(tǒng)輸入顧客的平均到達時間、接受服務(wù)時間、收銀臺數(shù)目,以及仿真時間內(nèi)到達的顧客總數(shù),顧客事件初始化,系統(tǒng)按負指數(shù)分布產(chǎn)生各顧客的到達時間.顧客到達后選擇隊列長度較短的隊伍加入,并等待接受服務(wù),該顧客的等待時間為他所排隊列中前一顧客結(jié)束服務(wù)時刻減去他的到達時刻.在計算某時刻隊列長度時,將該時刻前系統(tǒng)中的總顧客數(shù)減去結(jié)束服務(wù)的顧客數(shù),即可求得平均隊列長度,最后輸出等待時間及隊列長度.

3 仿真結(jié)果及分析

圖3和圖4給出顧客數(shù)為100時的顧客到達時間與離開時間曲線圖以及顧客等待時間與逗留時間曲線圖.

圖3 顧客到達與離開時間曲線圖圖4 顧客等待與逗留時間曲線圖

通過比較仿真結(jié)果和理論值,發(fā)現(xiàn)其誤差不大,由此可證該模型的有效性.應(yīng)用排隊論,結(jié)合仿真技術(shù),對超市收銀排隊系統(tǒng)進行模擬分析,可以對超市排隊情況進行預(yù)估,從而可由各個時段的客流量來動態(tài)控制收銀臺的需求量,節(jié)約成本,進而提高顧客的滿意度.