臺灣博碩士論文加值系統

本論文研究一個具有多等級、多個服務單位並且有排隊長度限制的優先佇列系統。其中針對不同優先順序的等級，對抵達過程與服務時間給予假設。本研究在可以插隊與不可以插隊的佇列規則下，使用有限馬可夫鏈來獲得優先佇列的等候時間分配，並優化既有的演算法，使得計算時間減少。我們接著借數例呈現在固定佇列規則之下，給定不同的初始狀態分配所算出來的等候時間分配之差異，以及給定相同的初始狀態，在不同的佇列規則下所算出來的等候時間分配會有所不同。最後，我們介紹一個簡易的方式為前述各個情況所獲得的等候時間分配計算其期望值與變異數。

This paper studies a priority queue system with multiple levels, multiple service units and queue length restrictions. A hypothesis is given to the arrival process and service time for different priority levels. In this study, a Markov chain approach is used to obtain the waiting-time distribution of preemptive or non-preemptive priority queue, and the existing algorithm is optimized to reduce the time for computation. We then demonstrate in numerical examples that, given a rule, different waiting-time distributions are obtained resulting from various initial state distributions; given the same initial state, a waiting-time distribution can be obtained for each of the preemptive or the non-preemptive priority queue with the same parameters. In addition, the expected value of wait time and its variance for a priority queueing system become readily available once the waiting-time distribution is calculated.

摘要……………………………………………………………………………………………………………………i

SUMMARY…………………………………………………………………………………………………………ii

致謝……………………………………………………………………………………………………………………v

目錄…………………………………………………………………………………………………………………vi

表目錄………………………………………………………………………………………………………viii

圖目錄……………………………………………………………………………………………………………ix

第一章 緒論……………………………………………………………………………………………1

第一節 研究背景與動機…………………………………………………………1

第二節 研究目的…………………………………………………………………………2

第三節 研究架構…………………………………………………………………………2

第二章 文獻回顧……………………………………………………………………………………3

第一節 排隊與佇列……………………………………………………………………3

第二節 馬可夫鏈與佇列…………………………………………………………5

第三節 相關之研究……………………………………………………………………5

第三章 模型假設……………………………………………………………………………………6

第一節 抵達過程…………………………………………………………………………7

第二節 佇列規則…………………………………………………………………………8

第三節 服務機制…………………………………………………………………………8

第四章 可同時服務多位顧客的優先佇列…………………………………10

第一節 可插隊優先佇列系統………………………………………………10

第二節 不可插隊優先佇列系統…………………………………………19

第五章 驗證與分析……………………………………………………………………………25

第一節 新舊程式的不同之處………………………………………………25

第二節 可插隊優先佇列系統………………………………………………27

第三節 不可插隊優先佇列系統…………………………………………29

第四節 可插隊與不可插隊佇列系統之等候時間分配比較…32

第六章 結論與未來研究方向…………………………………………………………33

參考文獻……………………………………………………………………………………………………………35

附錄………………………………………………………………………………………………………………………36

附錄表1. 在可插隊之下既有的程式與新程式建造轉移機率矩陣的時間…………36

附錄表2. 在不可插隊之下既有的程式與新程式建造轉移機率矩陣的時間…………37

附錄表3. 可插隊優先佇列系統在不同初始狀態分配下的累積分配函數…………38

附錄表4. 不可插隊優先佇列系統在不同初始狀態分配下的累積分配函數…………39

附錄表5. 在相同初始狀態下，可插隊與不可插隊優先佇列系統的累積分配函數……40

附錄表6. 改變參數後，可插隊與不可插隊優先佇列系統的累積分配函數…………41

附錄表7. 可插隊優先佇列系統在(5.2.1)下的等候時間分配期望值與變異數……41

附錄表8. 可插隊優先佇列系統在(5.2.2)下的等候時間分配期望值與變異數……42

附錄表9. 不可插隊優先佇列系統在(5.3.1)下的等候時間分配期望值與變異數……42

附錄表10.不可插隊優先佇列系統在(5.3.2)下的等候時間分配期望值與變異數……42

圖5.1.1 既有的程式與新程式的不同之處…………………………………………25

圖5.1.2 一對一轉換……………………………………………………………………………………26

附錄圖1. 可插隊優先佇列系統在不同初始狀態分配下的cdf與pmf……………43

附錄圖2. 不可插隊優先佇列系統在不同初始狀態分配下的cdf與pmf……………43

附錄圖3. 在相同初始狀態下，可插隊與不可插隊的cdf與pmf……44

附錄圖4. 改變參數後，可插隊與不可插隊優先佇列系統的cdf與pmf……………45

1. Kendall, D. G. Stochastic processes occurring in the theory of queues and their analysis by the method of the imbedded Markov chain. The Annals of Mathematical Statistics, 24, 338-354 (1953)

2. A. Cobham. Priority assignment in waiting line problems. Journal of the Operations Research Society of America, 3(4) :547 (1954)

3. M. A. Aczel. The effect of introducing priorities.
Journal of the Operations Research Society of America, 8(5): 730-733 (1960)

4. Kleinrock, L. Queueing Systems, Volume II: Computer Applications Wiley- Interscience, New York (1976)

5. Kapadia, A. S., Kazmi, M. F. and Mitchell, A. C. Analysis of a finite capacity nonpreemptive priority queue. Computers and Operations Research, 11, 337-343 (1984)

6. D. Wagner. Waiting times of a finite-capacity multi-server model with non- preemptive priorities. European Journal of Operational Research, 102(1): 227-241 (1997)

7. Laskowsk et al. Models of Emergency Departments for Reducing Patient Waiting Times (2009)

8. H. M. Chang. Waiting-Line Problems with Priority Assignment, and its Application on Hospital Emergency Department Wait-Time. Doctoral dissertation, University of Manitoba (2011)

9. R. Durrett. Essentials of Stochastic Processes, Springer Texts in Statistics, 255-256 (2012)

10. 黃耀輝. “考量具有等待時間限制式之航空站安全檢查問題,國立成功大學工業與資訊管理學系研究所碩士論文 (2015)