魏煥東

摘 要 等待空間有限的模型在排隊(duì)系統(tǒng)中是十分常見的，本文將等待空間有限的條件轉(zhuǎn)化為算法中更新的向量，為等待空間有限的模型的模擬仿真提供一條可行的思路，并用matlab進(jìn)行模擬仿真。

關(guān)鍵詞 等待空間有限 排隊(duì)系統(tǒng) 模擬仿真

中圖分類號(hào)：U495 文獻(xiàn)標(biāo)識(shí)碼：A

1研究背景和意義

排隊(duì)在日常生產(chǎn)和生活中十分常見，關(guān)于排隊(duì)系統(tǒng)的理論研究國(guó)內(nèi)外學(xué)者做了大量的工作，ward whitt作為該領(lǐng)域的領(lǐng)軍人在他的專注[1]中做了大量的工作，模擬仿真研究作為理論研究的補(bǔ)充和驗(yàn)證同樣有許多人進(jìn)行研究。本文主要是將等待空間有限的條件數(shù)學(xué)化，轉(zhuǎn)化為算法可以操作的向量，為等待空間有限的排隊(duì)模型的研究提供一條新的思路。

2對(duì)等待空間的處理

在等待空間無限的排隊(duì)模型中，每一個(gè)到達(dá)的顧客都可以進(jìn)入系統(tǒng)，若顧客到達(dá)時(shí)服務(wù)臺(tái)有空位，則顧客可以直接接受服務(wù)；若無空位，則進(jìn)入隊(duì)列等待。不考慮顧客放棄，顧客的等待時(shí)間可以借助上一個(gè)顧客的信息來計(jì)算，為上一個(gè)顧客進(jìn)入服務(wù)臺(tái)的時(shí)間與該顧客到達(dá)時(shí)間之差，顧客的離開時(shí)間為顧客到達(dá)時(shí)間、等待時(shí)間與服務(wù)時(shí)間之和。對(duì)于顧客數(shù)據(jù)的的處理詳細(xì)可見文獻(xiàn)[2，3]。

若系統(tǒng)的等待空間有限，考慮G/G/n/K模型，模型具有n個(gè)服務(wù)臺(tái)，等待空間有限為K。本文中的等待空間指的是隊(duì)列的中的人數(shù)，則系統(tǒng)中最多可以容納的顧客數(shù)為n+K。當(dāng)系統(tǒng)中人數(shù)達(dá)到系統(tǒng)可容納的上限時(shí)顧客便不能進(jìn)入，此時(shí)到達(dá)的顧客被阻塞而不能進(jìn)入系統(tǒng)，顧客的離開時(shí)間等于顧客的到達(dá)時(shí)間。若顧客可以進(jìn)入系統(tǒng)，顧客的等待時(shí)間借助上一個(gè)進(jìn)入系統(tǒng)的顧客的信息來計(jì)算。用ui表示第i個(gè)顧客的到達(dá)時(shí)間，vi表示第i個(gè)顧客的服務(wù)時(shí)間，wi代表第i個(gè)顧客的等待時(shí)間。用表i示顧客的離開時(shí)間，則

i=ui+vi+wi

為了輔助算法的實(shí)現(xiàn)，創(chuàng)建一個(gè)向量queue。首先對(duì)向量進(jìn)行初始化，前n個(gè)顧客無論以怎樣的路徑到達(dá)都可以直接進(jìn)入服務(wù)臺(tái)，所以前n個(gè)顧客的等待時(shí)間必然為0，計(jì)算出前n個(gè)顧客的離開時(shí)間。初始化的向量queue保存前n個(gè)顧客的離開時(shí)間，此時(shí)最新的一個(gè)成功進(jìn)入系統(tǒng)的顧客為第n個(gè)顧客。

當(dāng)?shù)趇（i>n）個(gè)顧客到達(dá)系統(tǒng)時(shí)，首先判斷此時(shí)隊(duì)列中剩余的顧客數(shù)，即在第i個(gè)顧客到達(dá)時(shí)尚未離開系統(tǒng)的顧客數(shù)，即離開時(shí)間大于第i個(gè)顧客到達(dá)時(shí)間的顧客數(shù)。計(jì)算向量queue中大于第i個(gè)顧客到達(dá)時(shí)間ui的元素的個(gè)數(shù)，若該值小于n+K，說明此時(shí)系統(tǒng)中的人數(shù)沒有到達(dá)上限，第i個(gè)顧客可以進(jìn)入系統(tǒng)中；若該值等于n+K，則第i個(gè)顧客被阻塞而不能進(jìn)入系統(tǒng)。

若第i個(gè)顧客可以進(jìn)入系統(tǒng)，計(jì)算出該顧客的等待時(shí)間和離開時(shí)間，此時(shí)需要更新向量queue，用向量中大于ui的元素以及第i個(gè)顧客的離開時(shí)間i組成新的向量queue，新的向量queue由大于離開時(shí)間大于第i個(gè)顧客到達(dá)時(shí)間的顧客的離開時(shí)間和第i個(gè)顧客的離開時(shí)間組成。若顧客被阻塞則不需要更新向量queue。

對(duì)向量queue的更新操作，保存每個(gè)顧客進(jìn)入系統(tǒng)后剩余顧客的離開時(shí)間，通過比較前面顧客的離開時(shí)間與顧客到達(dá)時(shí)間判斷顧客到達(dá)時(shí)系統(tǒng)中剩余的顧客數(shù)，來控制等待空間有限的條件。

3模擬仿真

以M/M/n/K模型為例，令顧客到達(dá)率為20，每個(gè)服務(wù)臺(tái)服務(wù)率為1，系統(tǒng)具有20個(gè)服務(wù)臺(tái)，模擬出前1000個(gè)顧客的到達(dá)時(shí)間和服務(wù)時(shí)間，取等待空間為5，等待空間有限和無限的系統(tǒng)中人數(shù)如圖1所示：

4總結(jié)

本文研究和分析了排隊(duì)系統(tǒng)的模擬仿真中對(duì)等待空間有限的處理方法，通過matlab的模擬仿真可以看出該處理方式是有效的，為研究等待空間有限的排隊(duì)系統(tǒng)的提供了一條新的思路。

參考文獻(xiàn)

[1] WhittWard. Stochastic-Process Limits[M]. New York， Springer， 2002.

[2] 宋振峰，席志紅，劉飛.基于Matlab的排隊(duì)模型的仿真[J].現(xiàn)代電子技術(shù)，2005，28（06）：29—30.

[3] 秦海林，劉建民.帶優(yōu)先權(quán)與不耐煩顧客排隊(duì)模型的模擬仿真[J].現(xiàn)代電子技術(shù)，2012，35（20）：91-94.

[4] 張建航，李宗成，宋曉峰.單服務(wù)員排隊(duì)模型及其蒙特卡洛模擬[J].現(xiàn)代電子技術(shù)，2006，29（24）：44-46.