基于排隊(duì)論的某款臺結(jié)算方式的優(yōu)化模型

1、蘭州交通大學(xué)2011年大學(xué)生數(shù)學(xué)建模競賽論文題目： 基于排隊(duì)論的某款臺結(jié)算方式 的優(yōu)化模型 參賽人1： 姓名 田 疆 學(xué)院 自動化與電氣工程學(xué)院 班級 電氣084班 參賽人2： 姓名 尹健寧 學(xué)院 自動化與電氣工程學(xué)院 班級 電氣084班 參賽人3： 姓名 鄭瑩瑩 學(xué)院 自動化與電氣工程學(xué)院 班級 電氣084班 學(xué)校統(tǒng)一編號，個人不得填寫論文編號： 基于排隊(duì)論的某款臺結(jié)算方式的優(yōu)化模型一、摘要超市款臺結(jié)算方式的優(yōu)化調(diào)整是超市和顧客都共同關(guān)注的問題，從理論上講，這一問題兼有排隊(duì)論和規(guī)劃論的特點(diǎn)?？紤]到顧客、收銀臺和購買商品付款服務(wù)之間的流程關(guān)系，確定出使用平均排隊(duì)等待時間、平均接受服務(wù)時間、平均

2、逗留時間、各個服務(wù)臺的平均服務(wù)速率（也即超市的服務(wù)效率）、平均每單位時間中系統(tǒng)可以為顧客服務(wù)的比例（也即服務(wù)強(qiáng)度）來做為評價指標(biāo)，這些指標(biāo)可以充分反映超市款臺結(jié)算方式安排的優(yōu)劣。題目中當(dāng)前超市實(shí)行的規(guī)則可以看作是一個多隊(duì)列多服務(wù)臺的排隊(duì)模型（M/M/s且當(dāng)s=4的情況），所有的款臺現(xiàn)金結(jié)算和銀行卡與支票結(jié)算這兩種結(jié)算方式都結(jié)算，這當(dāng)然不能有效地分配超市收款臺資源。因此，我們把顧客按照結(jié)算方式類型不同分為4個隊(duì)列，將收款臺當(dāng)作服務(wù)臺，建立了一個4隊(duì)列多服務(wù)臺的無優(yōu)先權(quán)的排隊(duì)模型，其中一個為快速服務(wù)款臺，專為購買8個或8個以下商品的顧客服務(wù)，另外兩個為現(xiàn)金支付款臺，只結(jié)算現(xiàn)金結(jié)算業(yè)務(wù)，最后一個為兩

3、種結(jié)算方式都結(jié)算的傳統(tǒng)服務(wù)款臺。模型中的服務(wù)規(guī)則為“當(dāng)前被服務(wù)的顧客總平均逗留時間最短”和“同類型內(nèi)部先到先服務(wù)”。為了實(shí)現(xiàn)該排隊(duì)系統(tǒng)中的實(shí)時服務(wù)臺分配，在系統(tǒng)中嵌入了一個規(guī)劃模型，模型目標(biāo)是使“當(dāng)前被服務(wù)的顧客總平均逗留時間最短”，約束條件中考慮了服務(wù)臺被服務(wù)顧客滿員原則?？梢宰C明該規(guī)劃模型滿足“同類型內(nèi)部先到先服務(wù)”規(guī)則。我們使用了計算機(jī)系統(tǒng)仿真求解模型，仿真算法即排隊(duì)論的蒙特卡洛算法，編程語言使用Matlab編程仿真實(shí)現(xiàn)。得出結(jié)論：倡議模型比現(xiàn)有模型在客戶滿意度上有較大的改善。建議超市采納倡議模型以提高客戶滿意度和經(jīng)營效率。關(guān)鍵詞：排隊(duì)模型 系統(tǒng)仿真 款臺結(jié)算方式優(yōu)化二、問題的提出款臺結(jié)

4、算方式的優(yōu)化調(diào)整隨著高科技在社會生活各個領(lǐng)域應(yīng)用的不斷深入，人們的生活方式也在逐漸隨著這種高科技的應(yīng)用而發(fā)生重大的變化，尤其是與人們正常生活息息相關(guān)的各社會服務(wù)行業(yè)都以一種人性化的方式在改進(jìn)服務(wù)方式。其中服務(wù)臺結(jié)算方式的改變時幾乎影響每個人的一種變化形式，以前的款臺結(jié)算方式只有現(xiàn)金結(jié)算，而目前大多數(shù)服務(wù)行業(yè)的款臺結(jié)算都采用兩種形式：現(xiàn)金結(jié)算和銀行卡與支票結(jié)算；當(dāng)然后者在某種程度上確實(shí)為人們的生活消費(fèi)提供了方便，避免了諸如攜帶現(xiàn)金的不便與不安全等因素，但在諸如超市等一些顧客流量交大而款臺較少需要排隊(duì)等候結(jié)算的服務(wù)場所則出現(xiàn)課一個問題，盡管銀行卡或支票結(jié)算方便了這些結(jié)算的人，但這種結(jié)算方式比較耗時

5、，因而對持現(xiàn)金結(jié)算而排隊(duì)等候的人來說延長了他們排隊(duì)等候的時間，造成了他們情緒的不滿，其中一部分人便放棄到該場所來接受服務(wù)而轉(zhuǎn)投別的同類服務(wù)機(jī)構(gòu)，這樣就勢必給服務(wù)機(jī)構(gòu)造成一定的損失，因而作為該機(jī)構(gòu)的負(fù)責(zé)人在資源有限的情形下就要對結(jié)算方式進(jìn)行結(jié)構(gòu)調(diào)整，以保證兩種結(jié)算方式的顧客的總體滿意程度只有達(dá)到最大才能保證自身的利益，然而如何進(jìn)行結(jié)算方式結(jié)構(gòu)的合理調(diào)整，一直是服務(wù)機(jī)構(gòu)經(jīng)營者需要解決的問題。現(xiàn)有一小超市有4個付款臺，所有的款臺兩種結(jié)算方式都結(jié)算，每個款臺為一位顧客計算貨款數(shù)的時間與顧客所購得商品件數(shù)成正比（大約每件費(fèi)時2秒），約有20%的顧客用支票或銀行卡等手段支付，這個過程需要1.5分鐘，付現(xiàn)金

6、則僅需要0.5分鐘；為了使顧客的總體滿意程度達(dá)到最大，有人倡議設(shè)其中一個為快速服務(wù)款臺，專為購買8個或8個以下商品的顧客服務(wù)，指定另外兩個為現(xiàn)金支付款臺，只結(jié)算現(xiàn)金結(jié)算業(yè)務(wù)；假設(shè)顧客到達(dá)的平均時間間隔是0.5分鐘，顧客購買商品的件數(shù)按一下頻率表分布：件數(shù)891920293039404950相對頻數(shù)0.120.100.180.28分0.20分0.12分請你在合理的假設(shè)下，利用計算機(jī)的仿真功能建立一個模擬模型，對現(xiàn)有的系統(tǒng)和倡議的系統(tǒng)的運(yùn)轉(zhuǎn)進(jìn)行比較，針對超市的款臺結(jié)算結(jié)構(gòu)，對超市經(jīng)營者提供一種合理的建議。三、問題的分析超市款臺服務(wù)系統(tǒng)具有以下特點(diǎn)：顧客的來源是無限的，以顧客到達(dá)超市購物為標(biāo)志，進(jìn)入

7、款臺結(jié)算排隊(duì)系統(tǒng)；排隊(duì)等待的顧客如果暫時沒有遇到可立刻對其進(jìn)行結(jié)算服務(wù)的空閑款臺，則排隊(duì)等待結(jié)算服務(wù)，因而等待的人數(shù)及空間在理論上是無限制的。顧客按照先到先服務(wù)的規(guī)則，排成4隊(duì)，依次等待結(jié)算服務(wù)；從顧客進(jìn)入等待隊(duì)列到結(jié)算完畢表示服務(wù)完成，離開排隊(duì)系統(tǒng)。在本系統(tǒng)中先到先服務(wù)規(guī)則可看作是一個多隊(duì)列多服務(wù)臺的排隊(duì)系統(tǒng)，其中，服務(wù)臺即為款臺。題目主要要求比較現(xiàn)有的系統(tǒng)和倡議的系統(tǒng)的運(yùn)轉(zhuǎn)誰優(yōu)誰劣，因此問題構(gòu)成了一個具有4個隊(duì)列，4個服務(wù)臺的排隊(duì)系統(tǒng)，只是不同點(diǎn)在于現(xiàn)有系統(tǒng)的4個服務(wù)臺結(jié)算方式均相同而倡議的系統(tǒng)中4個服務(wù)臺的結(jié)算方式各有不同罷了。當(dāng)然，對于現(xiàn)有的系統(tǒng)，若按照先到先服務(wù)的規(guī)則進(jìn)行排隊(duì)可能會導(dǎo)

8、致等待結(jié)算的顧客隊(duì)列越來越長，不能有效的利用超市款臺資源。四、符號說明與模型假設(shè)1符號說明 ：結(jié)算臺個數(shù)； ：最簡單流(顧客流)的參數(shù)； ：單個結(jié)算臺單位時間平均服務(wù)完的顧客數(shù)： ：服務(wù)強(qiáng)度； ：時刻結(jié)算系統(tǒng)內(nèi)顧客人數(shù)； ：系統(tǒng)內(nèi)已有個顧客的到達(dá)率； ：系統(tǒng)內(nèi)有個顧客時，結(jié)算臺單位時間平均服務(wù)的顧客數(shù); ：平均等待隊(duì)長； ：平均逗留的顧客人數(shù)； ：平均等待時間； ：平均逗留時間； ：每位顧客購買件商品的概率； ：使用支票或者銀行卡等手段支付的顧客占所有顧客的比例； ：現(xiàn)金支付所用時間； ：支票或者銀行卡等手段支付所需時間； ：計算件商品的時間； ：顧客購買商品在第個區(qū)間所占全部區(qū)間的比重；2模

9、型假設(shè)本文所研究的排隊(duì)系統(tǒng)是指顧客在超市里挑選好商品后，在收銀臺前排隊(duì)等待付款的排隊(duì)系統(tǒng)。收銀臺是服務(wù)臺，顧客付款被認(rèn)為是接受服務(wù)。套用以上三方面規(guī)則：輸入過程是指顧客挑選好商品后來到收銀臺前；排隊(duì)規(guī)則是指顧客按單隊(duì)單服務(wù)臺、多隊(duì)多服務(wù)臺或單隊(duì)多服務(wù)臺的方式排隊(duì)；服務(wù)機(jī)構(gòu)是服務(wù)臺。經(jīng)過我們的分析得出本系統(tǒng)是一個M/M/4模型。并做出如下假設(shè)：（1）顧客以最簡單流到達(dá)結(jié)算臺。（2）結(jié)伴顧客(同時到達(dá)結(jié)算臺的顧客人數(shù))看成有時間間隔的到達(dá)結(jié)算臺，并且顧客到達(dá)結(jié)算臺的相繼到達(dá)時間間隔獨(dú)立。若設(shè)是顧客的平均到達(dá)率，那么是相鄰兩個顧客到達(dá)的平均間隔時間,并服從均值為的指數(shù)分布（即輸入過程為Poisson

10、過程）。（3）若設(shè)是一個連續(xù)工作服務(wù)臺的平均服務(wù)率，那么是顧客的期望服務(wù)時間。對每個顧客的平均服務(wù)時間服從均值為的指數(shù)分布。（4）顧客所購商品數(shù)量在給定區(qū)間內(nèi)服從均勻分布。（5）本系統(tǒng)中各個服務(wù)臺工作相互獨(dú)立(不搞協(xié)助) 。（6）每個結(jié)算臺的服務(wù)效率相同。（7）對于本系統(tǒng)中的多服務(wù)臺模型，有效因子的公式為。表示每一個服務(wù)臺都單獨(dú)用來為顧客提供服務(wù)時花在服務(wù)上的平均時間。因此，為了使每一個服務(wù)臺都有一個可控的有效因子，仍然需要1，這使得排隊(duì)系統(tǒng)可以達(dá)到平穩(wěn)條件。（8）顧客結(jié)算按照FIFS(先來先服務(wù))原則進(jìn)行。五、模型的建立1模型的分析基于標(biāo)準(zhǔn)的模型，我們在分析這個排隊(duì)系統(tǒng)時，仍然從其狀態(tài)轉(zhuǎn)移關(guān)

11、系開始，其狀態(tài)圖如圖(1),轉(zhuǎn)移模型如圖(2).如狀態(tài)1轉(zhuǎn)移到狀態(tài)0(系統(tǒng)中有一名顧客被服務(wù)完了)的轉(zhuǎn)移率為，狀態(tài)2轉(zhuǎn)移到狀態(tài)1(在兩個服務(wù)臺上有一個顧客被服務(wù)完成而離去)，因?yàn)椴幌奘悄膫€服務(wù)臺，所以轉(zhuǎn)移率為，同理考慮狀態(tài)轉(zhuǎn)移到狀態(tài)(在個服務(wù)臺上有一個顧客被服務(wù)完成而離去)，因?yàn)椴幌奘悄膫€服務(wù)臺，所以當(dāng)?shù)脮r候，轉(zhuǎn)移率為；當(dāng)?shù)脮r候，因?yàn)橹挥袀€服務(wù)臺，換句話說，最多只有個顧客被服務(wù)，個顧客在等待，轉(zhuǎn)移率為。 。顧客離開超市結(jié)算臺結(jié)算臺1結(jié)算臺2結(jié)算臺3結(jié)算臺4完成顧客圖(1)圖(2)根據(jù)圖(2)，可以得到轉(zhuǎn)移方程：其中：，且.遞推上述差分方程，可以求得：特別的，當(dāng)只有一個服務(wù)臺時，系統(tǒng)變?yōu)?，各個指

12、標(biāo)為：，2評價指標(biāo)的建立題目要求使得顧客的總體滿意度達(dá)到最大，故對現(xiàn)有模型和倡議模型進(jìn)行對比，為了建立恰當(dāng)?shù)臐M意度評價體系，結(jié)合排隊(duì)論中的各個系統(tǒng)指標(biāo)，在這里，我們僅僅考慮顧客在整個付款系統(tǒng)中的逗留時間，將這個時間作為滿意度的一個最重要的指標(biāo)，而將整個隊(duì)長作為顧客滿意度的另外一個指標(biāo)，并給予相應(yīng)的權(quán)系數(shù)，為了使得評價體系完整，具有說服力，我們先將評價指標(biāo)歸一化，應(yīng)用簡單的線性函數(shù)歸一化，如下：統(tǒng)一化后數(shù)據(jù)后，對于現(xiàn)有系統(tǒng)模型及倡議系統(tǒng)模型，我們應(yīng)用如下量化指標(biāo)來描述顧客的滿意度： (其中:,為歸一化數(shù)據(jù)).其滿意度定義為：從而本文的滿意度評價指標(biāo)為：3模型一(現(xiàn)有系統(tǒng))建立對于單個顧客，其購買

13、件商品的概率為，現(xiàn)在考慮購買商品數(shù)的所有可能情況，根據(jù)題意，購買商品數(shù)在區(qū)間的平均件數(shù)為，則：每位顧客購買商品的平均數(shù)量為：而本文為離散模型，即： （1） (2)結(jié)算人員為每位顧客計算結(jié)算時間為： (3)結(jié)算人員為每位顧客服務(wù)的平均時間為： (4)從而： (5)根據(jù)模型分析，結(jié)算服務(wù)系統(tǒng)的運(yùn)行指標(biāo)如下：平均隊(duì)長： (6) (7)到達(dá)結(jié)算臺后必須等待的概率： (8)平均等待時間和逗留時間，由公式求得： (9) (10)4模型二(倡議系統(tǒng))的建立原四個結(jié)算款臺中，現(xiàn)有一個款臺(快速款臺)專門為購買8個或者8個以下商品的顧客服務(wù)，其服務(wù)的顧客只是在購買商品數(shù)量上有所限定，而并沒有對付款方式有所限定(

14、現(xiàn)金支付和銀行卡及支票支付)；另外三個款臺為購買商品數(shù)量大于8件的顧客服務(wù)，而其中兩個被指定為只能使用現(xiàn)金支付；其支付系統(tǒng)可以表示為如下圖形(3)：顧客離開超市結(jié)算臺快速臺1()2()3()現(xiàn)4()現(xiàn)完成顧客 圖(3)：倡議系統(tǒng)的服務(wù)示意圖對結(jié)算臺1，專門為購買8個或者8個以下商品的顧客服務(wù)，其服務(wù)的顧客只是在購買商品數(shù)量上有所限定，而并沒有對付款方式有所限定(現(xiàn)金支付和銀行卡及支票支付)，對其應(yīng)用模型1,其中： (11) (12) (13)對于結(jié)算臺2，顧客的特征為購買商品數(shù)量在8個以上，但是并沒有對支付方式有所限制，故亦可以應(yīng)用模型1，其中： (14) (15) (16)對于結(jié)算臺3,4，

15、顧客的特征為購買商品數(shù)量在8個以上，且對支付方式有所限制(現(xiàn)金支付)，故亦可以應(yīng)用模型1，其中： (17) (18) (19)六、模型的求解根據(jù)題意，聯(lián)立等式(1)-(10),可以求得模型一(現(xiàn)有的系統(tǒng))在平衡時候的一些重要指標(biāo)，如下表(1)： 模型一 指標(biāo) (1) 服務(wù)臺空閑的概率平均隊(duì)列長平均隊(duì)長平均等待時間平均逗留時間0.41310.97581.85911.9516(分鐘)3.7182(分鐘)表(1)：現(xiàn)有的系統(tǒng)在平衡時候的指標(biāo)聯(lián)立等式(11)-(19)以及應(yīng)用排隊(duì)論中的及相關(guān)理論，可以求得模型二(倡議系統(tǒng))在平衡時候的一些重要指標(biāo)，如下表(2)： 結(jié)算臺 指標(biāo)(1) (2) (3,4)

16、 服務(wù)臺空閑的概率平均隊(duì)列長平均隊(duì)長平均等待時間平均逗留時間000000.63110.21570.58460.94912.57240.64520.16830.59960.44431.5830表(2)：倡議系統(tǒng)在平衡時候的指標(biāo)七、結(jié)果分析與檢驗(yàn)先對兩個模型的系統(tǒng)指標(biāo)應(yīng)用滿意地評價指標(biāo)，可以求得,見下表(3)： 結(jié)算臺歸一化指標(biāo) 模型一結(jié)算臺(1,2,3,4)模型二結(jié)算臺(1)模型二結(jié)算臺(2)模型二結(jié)算臺(3,4)平均隊(duì)長平均逗留時間1.0001.000000.31450.69180.32250.4257表(3)：模型部分指標(biāo)歸一化后數(shù)據(jù)對于模型二，顧客分別可能從不同的結(jié)算臺付款，因此需對四個結(jié)

17、算臺都要考慮，其滿意度按照顧客進(jìn)入結(jié)算臺比例加權(quán)，具體：經(jīng)過計算，可以得到如下模型對比圖(4)：滿意度圖(4)：兩個模型滿意度對比圖由上圖可明顯看出：倡議模型比現(xiàn)有模型在客戶滿意度上有較大的改善。所以我們的建議是如果超市采納了倡議模型，那么顧客的滿意度將更高，從而超市的經(jīng)營效率會得到很大提升。八、模型的優(yōu)缺點(diǎn)與改進(jìn)方向 九、參考文獻(xiàn)1盛 驟,謝氏千,潘承毅.概率論與數(shù)理統(tǒng)計（第四版）M.北京:高等教育出版社.2009.2徐玖平,胡知能.運(yùn)籌學(xué)數(shù)據(jù)模型決策（第二版）M.北京:科學(xué)出版社.2009.3劉正君.MATLAB科學(xué)計算與可視化仿真寶典M.北京:電子工業(yè)出版社.2009.4葉 向.實(shí)用運(yùn)籌

18、學(xué)上機(jī)實(shí)驗(yàn)指導(dǎo)及習(xí)題解答M.北京:中國人民大學(xué)出版社.2007.5劉 露.眼科病床安排模型及仿真算法.全國大學(xué)生數(shù)學(xué)建模競賽優(yōu)秀論文匯G.2010, 4(3):76-96. 十、附錄部分1模型計算及仿真源代碼（使用MATLAB語言）%solution model 1lmd=0.5t=0.8*(64/60+0.5)+0.2*(64/60+1.5);miu=1/t;a=lmd/miu;p0=1/(1+a+a*a/2+a*a*a/6+a*a*a*a/24/(1-a/4);pd=(4*a4*p0)/(24*(4-a);lq=4*4*4*4*a5*p0/4/24/(1-a/4)2;ls=lq+a;wq=

19、lq/lmd;ws=ls/lmd;tai2=p0,lq,ls,wq,ws%solution model 2%station 1lmd=0.5/0.12t=0.8*(9/60+0.5)+0.2*(9/60+1.5);miu=1/ta=lmd/miup0=1-alq=a*a/(1-a)ls=a/(1-a)wq=lmd/miu/(miu-lmd)ws=1/(miu-lmd)%station2lmd=0.5/0.88/3*6/5;t=0.8*(55.4/60+0.5)+0.2*(55.4/60+1.5);miu=1/t;a=lmd/miu;p0=1-a;lq=a*a/(1-a);ls=a/(1-a);

20、wq=lmd/miu/(miu-lmd);ws=1/(miu-lmd);tai2=p0,lq,ls,wq,ws %station3.4lmd=0.5/0.88/3*2;t=0.8*(55.4/60+0.5);miu=1/t;a=lmd/miu;p0=1/(1+a+a*a/2/(1-a/2);lq=8*(a/2)*a*a*p0/2/(1-a/2)2;ls=lq+a;wq=lq/lmd;ws=ls/lmd;tai34=p0,lq,ls,wq,ws%guiyihuals=1.8591,0.5846,0.5996,0;ws=3.7182,2.5724,1.5830,0;ls1=(ls-min(ls).

21、/(max(ls)-min(ls)ws1=(ws-min(ws)./(max(ws)-min(ws)%man yi du ji suan a=0.1:0.1:0.9;b=1-a;d1=1./(1*a+1*b)/4;d2=0.88*(1./(0.6918*a+0.3145*b)+1./(0.4257*a+0.3225*b);d2=(d2-min(d2)/(max(d2)-min(d2)plot(b,d1,'r',b,d2)title('現(xiàn)有模型(紅線)與倡議模型滿意度對比')xlabel('等待時間占滿意度的百分比')ylabel('滿意度')legend('現(xiàn)有模型','倡議模型')%solution model 3lmd=0.5t=0.8*(64/60+0.5)+0.2*(64/60+1.5);miu=1/t;a=lmd/miu;p0=1/(1+a+a*a/2+a*a*a/6+a*a*a*a/24/(1-a/4);pd=(4*a4*p0)/(24*(4-a);lq=4*4*4*4*a5*p0/4/24/(1-a/4)2;ls=lq+a;wq=lq/lmd;ws=ls/lmd;tai2=p0,lq,ls,wq,ws