M/M^(N)/K 批次服務系統下平行排隊系統的最佳使用者決策

User optimal policy for a parallel queueing system with state dependent routing under a (M/M^(N)/K) batch service

鄭文豪(Wen-Hao Cheng)

指導教授 ： 白惠明

國立臺北大學/商學院/統計學系/碩士(2011年)

摘要

考慮一個平行排隊系統的網絡，排隊系統 1 為 M/M/1 單一服務和無窮容量的佇列，而排隊系統 2 為M/M^(N)/K 批次服務佇列，其批次大小為 2<=N，且服務人員有限 。在網絡中，使用者選擇一個排隊系統加入，以求在觀察瞬間系統狀態，能使自己在系統的等候時間最小。這裡證得此平行排隊系統存在一個使用者最佳決策(user optimal policy)且該決策唯一。除了針對決策外，本篇論文還探討唐斯-湯姆森(Downs-Thomson)謬論。在此系統下，藉由數值呈現，在狀態相依決策(state-dependent routing)下，唐斯-湯姆森謬論現象相對於比例決策(probabilistic routing)是輕微地。

關鍵字

使用者最佳決策 ； 平行排隊系統 ； 狀態相依決策 ； 唐斯-湯姆森謬論

並列摘要

Consider a system of two queues in parallel, one of which is M/M/1 single-server infinite capacity queue, andthe other M/M^(N)/K batch service queue,where batch size 2<=N and K is finite. In the network, a stream of Poisson arrivals choose which queue to join, after observing the current state of the system, and so as to minimize their own expected delay. We show that a user optimal policy exists, and that it possesses various monotonicity properties. In addition, we give examples where state-dependent routing mitigates the Downs-Thomson effect observed under probabilistic routing.

並列關鍵字

User optimal policy ； Parallel queue ； State-dependent routing ； Downs-Thomson paradox

參考文獻

[1] Arnott, R., Small, K.: The economics of traffic

Thomson paradox:existence, uniqueness and stability of

user equilibria. Queueing Syst. 49, 321-334 (2005)

[3] Calvert, B.: The Downs-Thomson effect in a Markov

process. Probab. Eng. Inf. Sci. 11, 327-340 (1997)