Приближение интенсивного движения - Heavy traffic approximation

В теория массового обслуживания, дисциплина в рамках математической теория вероятности, а приближение интенсивного движения (иногда теорема о ограничении интенсивного движения^[1] или же диффузионное приближение) - согласование модели массового обслуживания с диффузионный процесс под некоторыми ограничение условия на параметры модели. Первый такой результат опубликовал Джон Кингман кто показал, что когда параметр использования M / M / 1 очередь близка к 1, масштабированная версия процесса длины очереди может быть точно аппроксимирована отраженное броуновское движение.^[2]

Состояние интенсивного движения

Для процесса обычно указываются приближения интенсивного движения. Икс(т) описывающее количество клиентов в системе в момент времени т. Они достигаются путем рассмотрения модели при предельных значениях некоторых параметров модели, и поэтому для того, чтобы результат был конечным, модель должна быть масштабирована с коэффициентом п, обозначенный^[3]:490

${\displaystyle {\hat {X}}_{n}(t)={\frac {X(nt)-\mathbb {E} (X(nt))}{\sqrt {n}}}}$

и предел этого процесса рассматривается как п → ∞.

Обычно рассматриваются три класса режимов.

1. Количество серверов фиксировано, а интенсивность трафика (загрузка) увеличивается до 1 (снизу). Приближение длины очереди - это отраженное броуновское движение.^[4][5][6]
2. Интенсивность трафика фиксирована, а количество серверов и скорость поступления увеличиваются до бесконечности. Здесь предел длины очереди сходится к нормальное распределение.^[7][8][9]
3. Количество β фиксируется где

${\displaystyle \beta =(1-\rho ){\sqrt {s}}}$

с ρ представляющий интенсивность движения и s количество серверов. Интенсивность трафика и количество серверов увеличиваются до бесконечности, и процесс ограничения представляет собой гибрид приведенных выше результатов. Этот случай, впервые опубликованный Халфином и Уиттом, часто известен как режим Халфина – Уитта.^[1][10][11] или режим, основанный на качестве и эффективности (QED).^[12]

Результаты для очереди G / G / 1

Теорема 1. ^[13] Рассмотрим последовательность Очереди G / G / 1 проиндексировано ${\displaystyle j}$.
Для очереди ${\displaystyle j}$
позволять ${\displaystyle T_{j}}$ обозначают случайное время между прибытиями, ${\displaystyle S_{j}}$ обозначим случайное время обслуживания; пусть ${\displaystyle \rho _{j}={\frac {\lambda _{j}}{\mu _{j}}}}$ обозначим интенсивность движения с помощью ${\displaystyle {\frac {1}{\lambda _{j}}}=E(T_{j})}$ и ${\displaystyle {\frac {1}{\mu _{j}}}=E(S_{j})}$; позволять ${\displaystyle W_{q,j}}$ обозначают время ожидания в очереди для заявки в устойчивом состоянии; Позволять ${\displaystyle \alpha _{j}=-E[S_{j}-T_{j}]}$ и ${\displaystyle \beta _{j}^{2}=\operatorname {var} [S_{j}-T_{j}];}$

Предположим, что ${\displaystyle T_{j}{\xrightarrow {d}}T}$, ${\displaystyle S_{j}{\xrightarrow {d}}S}$, и ${\displaystyle \rho _{j}\rightarrow 1}$. тогда

${\displaystyle {\frac {2\alpha _{j}}{\beta _{j}^{2}}}W_{q,j}{\xrightarrow {d}}\exp(1)}$

при условии, что:

(а) ${\displaystyle \operatorname {Var} [S-T]>0}$

(б) для некоторых ${\displaystyle \delta >0}$, ${\displaystyle E[S_{j}^{2+\delta }]}$ и ${\displaystyle E[T_{j}^{2+\delta }]}$ оба меньше, чем некоторая константа ${\displaystyle C}$ для всех ${\displaystyle j}$.

Эвристический аргумент

• Время ожидания в очереди

Позволять ${\displaystyle U^{(n)}=S^{(n)}-T^{(n)}}$ - разница между n-м временем обслуживания и n-м временем между прибытиями; Пусть ${\displaystyle W_{q}^{(n)}}$ время ожидания в очереди n-го запроса;

Тогда по определению:

${\displaystyle W_{q}^{(n)}=\max(W_{q}^{(n-1)}+U^{(n-1)},0)}$

После рекурсивного расчета имеем:

${\displaystyle W_{q}^{(n)}=\max(U^{(1)}+\cdots +U^{(n-1)},U^{(2)}+\cdots +U^{(n-1)},\ldots ,U^{(n-1)},0)}$

• Случайная прогулка

Позволять ${\displaystyle P^{(k)}=\sum _{i=1}^{k}U^{(n-i)}}$, с ${\displaystyle U^{(i)}}$ i.i.d; Определять ${\displaystyle \alpha =-E[U^{(i)}]}$ и ${\displaystyle \beta ^{2}=\operatorname {var} [U^{(i)}]}$;

Тогда у нас есть

${\displaystyle E[P^{(k)}]=-k\alpha }$

${\displaystyle \operatorname {var} [P^{(k)}]=k\beta ^{2}}$

${\displaystyle W_{q}^{(n)}=\max _{n-1\geq k\geq 0}P^{(k)};}$

мы получили ${\displaystyle W_{q}^{(\infty )}=\sup _{k\geq 0}P^{(k)}}$ взяв предел ${\displaystyle n}$.

Таким образом, время ожидания в очереди n-го запроса ${\displaystyle W_{q}^{(n)}}$ является супремумом случайная прогулка с отрицательным дрейфом.

• Приближение броуновского движения

Случайная прогулка можно аппроксимировать Броуновское движение когда размер прыжка приближается к 0, а время между прыжком приближается к 0.

У нас есть ${\displaystyle P^{(0)}=0}$ и ${\displaystyle P^{(k)}}$ имеет независимые и стационарные приращения. Когда интенсивность движения ${\displaystyle \rho }$ подходы 1 и ${\displaystyle k}$ как правило ${\displaystyle \infty }$, у нас есть ${\displaystyle P^{(t)}\ \sim \ \mathbb {N} (-\alpha t,\beta ^{2}t)}$ после замены ${\displaystyle k}$ с непрерывным значением ${\displaystyle t}$ в соответствии с функциональная центральная предельная теорема.^[14]:110 Таким образом, время ожидания в очереди ${\displaystyle n}$-го покупателя можно аппроксимировать супремумом Броуновское движение с отрицательным дрейфом.

• Супремум броуновского движения

Теорема 2.^[15]:130 Позволять ${\displaystyle X}$ быть Броуновское движение с дрейфом ${\displaystyle \mu }$ и стандартное отклонение ${\displaystyle \sigma }$ начиная с начала координат, и пусть ${\displaystyle M_{t}=\sup _{0\leq s\leq t}X(s)}$

если ${\displaystyle \mu \leq 0}$

${\displaystyle \lim _{t\rightarrow \infty }P(M_{t}>x)=\exp(2\mu x/\sigma ^{2}),x\geq 0;}$

иначе

${\displaystyle \lim _{t\rightarrow \infty }P(M_{t}\geq x)=1,x\geq 0.}$

Вывод

${\displaystyle W_{q}^{(\infty )}\thicksim \exp \left({\frac {2\alpha }{\beta ^{2}}}\right)}$ в условиях интенсивного движения

Таким образом, эвристически обосновывается теорема о ограничении интенсивного движения транспорта (теорема 1). Формальные доказательства обычно используют другой подход, который включает: характеристические функции.^[4][16]

Пример

Рассмотрим Очередь M / G / 1 со скоростью прибытия ${\displaystyle \lambda }$, среднее время обслуживания ${\displaystyle E[S]={\frac {1}{\mu }}}$, а дисперсия времени обслуживания ${\displaystyle \operatorname {var} [S]=\sigma _{B}^{2}}$. Какое среднее время ожидания в очереди в устойчивое состояние ?

Точное среднее время ожидания в очереди в устойчивое состояние дан кем-то:

${\displaystyle W_{q}={\frac {\rho ^{2}+\lambda ^{2}\sigma _{B}^{2}}{2\lambda (1-\rho )}}}$

Соответствующее приближение интенсивного движения:

${\displaystyle W_{q}^{(H)}={\frac {\lambda ({\frac {1}{\lambda ^{2}}}+\sigma _{B}^{2})}{2(1-\rho )}}.}$

Относительная погрешность приближения интенсивного движения:

${\displaystyle {\frac {W_{q}^{(H)}-W_{q}}{W_{q}}}={\frac {1-\rho ^{2}}{\rho ^{2}+\lambda ^{2}\sigma _{B}^{2}}}}$

Таким образом, когда ${\displaystyle \rho \rightarrow 1}$, у нас есть :

${\displaystyle {\frac {W_{q}^{(H)}-W_{q}}{W_{q}}}\rightarrow 0.}$

внешняя ссылка

• Очередь G / G / 1 Сергей Фосс

Рекомендации

1. Halfin, S .; Уитт, В. (1981). «Пределы интенсивного трафика для очередей с множеством экспоненциальных серверов» (PDF). Исследование операций. 29 (3): 567. Дои:10.1287 / opre.29.3.567.
2. Кингман, Дж. Ф. С.; Атья (октябрь 1961 г.). «Единая очередь сервера в условиях интенсивного трафика». Математические труды Кембриджского философского общества. 57 (4): 902. Bibcode:1961PCPS ... 57..902K. Дои:10.1017 / S0305004100036094. JSTOR  2984229.
3. Гаутам, Натараджан (2012). Анализ очередей: методы и приложения. CRC Press. ISBN  9781439806586.
4. Кингман, Дж. Ф. С. (1962). «В очередях в плотном потоке». Журнал Королевского статистического общества. Серия B (Методологическая). 24 (2): 383–392. Дои:10.1111 / j.2517-6161.1962.tb00465.x. JSTOR  2984229.
5. Iglehart, Donald L .; Уорд, Уитт (1970). «Многоканальные очереди в интенсивном трафике. II: Последовательности, сети и пакеты» (PDF). Достижения в прикладной теории вероятностей. 2 (2): 355–369. Дои:10.2307/1426324. JSTOR  1426324. Получено 30 ноя 2012.
6. Köllerström, Джулиан (1974). «Теория интенсивного трафика для очередей с несколькими серверами. I». Журнал прикладной теории вероятностей. 11 (3): 544–552. Дои:10.2307/3212698. JSTOR  3212698.
7. Иглхарт, Дональд Л. (1965). «Ограничение приближения диффузии для множества серверных очередей и проблема ремонтника». Журнал прикладной теории вероятностей. 2 (2): 429–441. Дои:10.2307/3212203. JSTOR  3212203.
8. Боровков А.А. (1967). «О предельных законах сервисных процессов в многоканальных системах». Сибирский математический журнал. 8 (5): 746–763. Дои:10.1007 / BF01040651.
9. Иглхарт, Дональд Л. (1973). «Слабая сходимость в теории массового обслуживания». Достижения в прикладной теории вероятностей. 5 (3): 570–594. Дои:10.2307/1425835. JSTOR  1425835.
10. Пухальский, А. А .; Рейман М. И. (2000). «Мультиклассовая очередь GI / PH / N в режиме Halfin-Whitt». Достижения в прикладной теории вероятностей. 32 (2): 564. Дои:10.1239 / aap / 1013540179.
11. Рид, Дж. (2009). «Очередь G / GI / N в режиме Хальфина – Уитта». Анналы прикладной теории вероятностей. 19 (6): 2211–2269. arXiv:0912.2837. Дои:10.1214 / 09-AAP609.
12. Уитт, В. (2004). «Ориентированное на эффективность приближение интенсивного трафика для многосерверных очередей с отказами» (PDF). Наука управления. 50 (10): 1449–1461. CiteSeerX  10.1.1.139.750. Дои:10.1287 / mnsc.1040.0279. JSTOR  30046186.
13. Gross, D .; Shortie, J. F .; Томпсон, Дж. М .; Харрис, К. М. (2013). «Границы и приближения». Основы теории массового обслуживания. С. 329–368. Дои:10.1002 / 9781118625651.ch7. ISBN  9781118625651.
14. Chen, H .; Яо, Д. Д. (2001). «Техническая Дезидерата». Основы сетей массового обслуживания. Стохастическое моделирование и прикладная вероятность. 46. С. 97–124. Дои:10.1007/978-1-4757-5301-1_5. ISBN  978-1-4419-2896-2.
15. Chen, H .; Яо, Д. Д. (2001). «Очереди на одной станции». Основы сетей массового обслуживания. Стохастическое моделирование и прикладная вероятность. 46. С. 125–158. Дои:10.1007/978-1-4757-5301-1_6. ISBN  978-1-4419-2896-2.
16. Асмуссен, С. Р. (2003). «Стационарные свойства GI / G / 1». Прикладная вероятность и очереди. Стохастическое моделирование и прикладная вероятность. 51. С. 266–301. Дои:10.1007/0-387-21525-5_10. ISBN  978-0-387-00211-8.