排隊系統模擬仿真中對空間有限的處理

魏煥東

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

關鍵詞 等待空間有限 排隊系統 模擬仿真

中圖分類號：U495 文獻標識碼：A

1研究背景和意義

排隊在日常生產和生活中十分常見，關于排隊系統的理論研究國內外學者做了大量的工作，ward whitt作為該領域的領軍人在他的專注[1]中做了大量的工作，模擬仿真研究作為理論研究的補充和驗證同樣有許多人進行研究。本文主要是將等待空間有限的條件數學化，轉化為算法可以操作的向量，為等待空間有限的排隊模型的研究提供一條新的思路。

2對等待空間的處理

在等待空間無限的排隊模型中，每一個到達的顧客都可以進入系統，若顧客到達時服務臺有空位，則顧客可以直接接受服務；若無空位，則進入隊列等待。不考慮顧客放棄，顧客的等待時間可以借助上一個顧客的信息來計算，為上一個顧客進入服務臺的時間與該顧客到達時間之差，顧客的離開時間為顧客到達時間、等待時間與服務時間之和。對于顧客數據的的處理詳細可見文獻[2，3]。

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

i=ui+vi+wi

為了輔助算法的實現，創建一個向量queue。首先對向量進行初始化，前n個顧客無論以怎樣的路徑到達都可以直接進入服務臺，所以前n個顧客的等待時間必然為0，計算出前n個顧客的離開時間。初始化的向量queue保存前n個顧客的離開時間，此時最新的一個成功進入系統的顧客為第n個顧客。

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

若第i個顧客可以進入系統，計算出該顧客的等待時間和離開時間，此時需要更新向量queue，用向量中大于ui的元素以及第i個顧客的離開時間i組成新的向量queue，新的向量queue由大于離開時間大于第i個顧客到達時間的顧客的離開時間和第i個顧客的離開時間組成。若顧客被阻塞則不需要更新向量queue。

對向量queue的更新操作，保存每個顧客進入系統后剩余顧客的離開時間，通過比較前面顧客的離開時間與顧客到達時間判斷顧客到達時系統中剩余的顧客數，來控制等待空間有限的條件。

3模擬仿真

以M/M/n/K模型為例，令顧客到達率為20，每個服務臺服務率為1，系統具有20個服務臺，模擬出前1000個顧客的到達時間和服務時間，取等待空間為5，等待空間有限和無限的系統中人數如圖1所示：

4總結

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

參考文獻

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

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

[3] 秦海林，劉建民.帶優先權與不耐煩顧客排隊模型的模擬仿真[J].現代電子技術，2012，35（20）：91-94.

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