王穎俐，王 飛，謝文丹

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

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

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

1 M/M/c/∞排隊(duì)模型

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

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

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

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

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

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

圖1 顧客到達(dá)的程序操作流程圖2 顧客離去的程序操作流程

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

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

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

圖3 顧客到達(dá)與離開時(shí)間曲線圖圖4 顧客等待與逗留時(shí)間曲線圖

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