跳转到内容

罗斯猜想

维基百科,自由的百科全书

罗斯猜想(英語:Ross's conjecture)是排队理论猜想,若一個排队队伍中,顾客不是随机到达的最简单模型來排队,此猜想提供顾客平均等待时间下界。

这是美国南加州大学教授谢尔顿·M·罗斯英语Sheldon M. Ross在1978年提出的猜想,1981年由波兰弗罗茨瓦夫大学托马什·罗尔斯基教授证明[1]。用罗斯猜想可得到其下界,而在有限的缓冲队列下,下界不成立。[2]

下界

[编辑]

罗斯猜想是指一個隊伍,其到達機率是依考克斯过程英语doubly stochastic Poisson process[3],或是非靜態的卜瓦松過程[1][4],其平均等待時間會大於等於

其中

S為服務時間
λ是平均到達率[1]

參考資料

[编辑]
  1. ^ 1.0 1.1 1.2 Rolski, Tomasz, Queues with non-stationary input stream: Ross's conjecture, Advances in Applied Probability, 1981, 13 (3): 603–618, JSTOR 1426787, MR 0615953, doi:10.2307/1426787 .
  2. ^ Heyman, D. P., On Ross's conjectures about queues with non-stationary Poisson arrivals, Journal of Applied Probability, 1982, 19 (1): 245–249, JSTOR 3213936, MR 0644439, doi:10.2307/3213936 .
  3. ^ Huang, J., A Study on Queuing Theory and Teletraffic Models (Part 1 of 3), Ph.D Dissertation, 1991, (1), doi:10.13140/RG.2.1.1259.6329 .
  4. ^ Ross, Sheldon M., Average delay in queues with non-stationary Poisson arrivals, Journal of Applied Probability, 1978, 15 (3): 602–609, JSTOR 3213122, MR 0483101, doi:10.2307/3213122 .