簡易檢索 / 詳目顯示
| 研究生： |
林建佑 |
|---|---|
| 論文名稱： |
車輛服務系統之最佳路由策略 Optimal Routing for General Vehicle Service Systems |
| 指導教授： | 洪英超 |
| 學位類別： |
碩士
Master |
| 系所名稱： |
商學院 - 統計學系 Department of Statistics |
| 論文出版年： | 2014 |
| 畢業學年度： | 102 |
| 語文別： | 中文 |
| 論文頁數： | 34 |
| 中文關鍵詞： | 車輛路由策略 、系統穩定性 、佇列 、吞吐量 |
| 相關次數： | 點閱：83 下載：14 |
| 分享至: |
| 查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
在本文中我們探討具有K座服務站的車輛平行處理系統(Parallel processing system)，並且對於系統的假設更加一般化。車輛在抵達該區域時會面臨選擇服務站的問題，所以路由策略的使用對於系統中車輛滯留時間的表現值顯得更加重要。我們藉由系統的穩定條件(Stability conditions)來比較文獻中常見的車輛路由策略以及我們提出的動態策略(Dynamic policy)之間的差異性，並且探討隨機車輛服務系統(Stochastic vehicle service system)的輸入強度之表現。我們提出一種全新的車輛路由策略：“最小加權佇列長度策略”(Join-the-Weighted-Shortest-Queue Policy)，並且證明了在系統的一般性假設之下此策略可以維持系統的強穩定性，間接也證明了本策略為一種最大吞吐量策略。其證明方式主要是以偏離分析(Drift analysis)作為基礎，並搭配相關的定理結果來證明。此外，我們也對於不同的最大吞吐量策略之下的車輛滯留時間平均值與第九十五百分位數的表現做出評估。最後，我們會對於各種不同的車輛輸入強度以及行駛速度之下，提出路由策略的建議方針。
第一章 緒論 1
第二章 系統描述與假設 3
第2.1節 系統描述 3
第2.2節 系統穩定性(System Stability) 6
第三章 路由策略 10
第3.1節 最近服務站策略(Routing to the Nearest Station Policy) 10
第3.2節 循環服務策略 (The Round Robin Policy) 10
第3.3節 最大服務率策略(Maximum Service Rate Policy) 11
第3.4節 其他路由策略 12
第四章 系統穩定性證明 14
第五章 系統的滯留時間表現值評估 20
第5.1節 系統模擬設定 20
第5.2節 滯留時間平均值 21
第5.3節 滯留時間第九十五百分位數 25
第5.4節 系統繁忙的模擬表現值 28
第六章 結論與討論 31
參考文獻 33
[1] B. Hajek (1982). Hitting time and occupation time bounds implied by drift analysis with applications. Adv. Appl. Prob., 14(3), pp.502-525.
[2] D. Bertsimas and D. Nakazato (1995). The distributional Little's law and its applications. Operations Research, 43(2), pp. 298-310.
[3] D. J. Bertsimas and G. Van Ryzin (1991). A stochastic and dynamic vehicle routing problem in the Euclidean plane. Operations Research, 39(4), pp.601-615.
[4] D. J. Bertsimas and G. Van Ryzin (1993). Stochastic and dynamic vehicle routing with general demand and interarrival time distributions. Advances in Applied Probability, pp.947-978.
[5] D. L. Iglehart and W. Whitt (1970). Multiple Channel Queues in heavy traffic, I. Adv. Appi. Prob, 2, pp.150-177
[6] E. Leonardi, M. Mellia, F. Neri and M. Ajmone Marsan (2001). On the stability of input-queued switches with speed-up. Networking, IEEE/ACM Transactions on, 9(1), pp.104-118.
[7] F. Jensen and N. E. Petersen (1982). Burn-in: an engineering approach to the design and analysis of burn-in procedures.
[8] H.N. Psaraftis (1988). Dynamic vehicle routing problems. Vehicle routing: Methods and studies, 16, pp. 223-248.
[9] J.G. Dai (1995). On positive Harris recurrence of multiclass queueing networks: a unified approach via fluid limit models. The Annals of Applied Probability, 5(1), pp.49-77.
[10] J. Walrand (1988). Introduction to queueing networks. Englewood Cliffs, Prentice Hall.
[11] R. Pemantle and J.S. Rosenthal (1999). Moment conditions for a sequence with negative drift to be uniformly bounded in . Stochastic Processes and their Applications, 82(1), pp.143-155.
[12] R.W. Wolff (1982). Poisson arrivals see time averages. Operations Research, 30(2), pp. 223-231.
[13] S. L. Bell and R. J. Williams (2001). Dynamic scheduling of a system with two parallel servers in heavy traffic with resource pooling: asymptotic optimality of a threshold policy. The Annals of Applied Probability, 11(3), pp.608-649.
[14] S. P. Meyn (1996). Stability and optimization of queueing networks and their fluid models. The Mathematics of Stochastic Manufacturing Systems, pp.17-21.
[15] Y. C. Hung and C.C. Chang (2008). Dynamic scheduling for switched processing systems with substantial service-mode switching times. Queueing systems, 60(1-2), pp.87-109.
[16] Y. C. Hung and G. Michailidis (2008). Modeling, scheduling, and simulation of switched processing systems. ACM Transactions on Modeling and Computer Simulation (TOMACS), 18(3), 12.
[17] Y. C. Hung and G. Michailidis (2012). Stability and control of acyclic stochastic processing networks with shared resources. Automatic Control, IEEE Transactions on, 57(2), pp.489-494.
