Формула Поллачека – Хинчина - Pollaczek–Khinchine formula

В теория массового обслуживания, дисциплина в рамках математической теория вероятности, то Формула Поллачека – Хинчина устанавливает связь между длиной очереди и распределением времени обслуживания Преобразования Лапласа для Очередь M / G / 1 (где вакансии поступают согласно Пуассоновский процесс и имеют общее распределение времени обслуживания). Этот термин также используется для обозначения отношений между средней длиной очереди и средним временем ожидания / обслуживания в такой модели.^[1]

Формула была впервые опубликована Феликс Поллачек в 1930 г.^[2] и преобразовать в вероятностные термины Александр Хинчин^[3] два года спустя.^[4][5] В теория разорения формулу можно использовать для вычисления вероятности окончательного разорения (вероятности банкротства страховой компании).^[6]

Средняя длина очереди

Формула утверждает, что среднее количество клиентов в системе L дан кем-то^[7]

${\displaystyle L=\rho +{\frac {\rho ^{2}+\lambda ^{2}\operatorname {Var} (S)}{2(1-\rho )}}}$

где

• ${\displaystyle \lambda }$ скорость прибытия Пуассоновский процесс
• ${\displaystyle 1/\mu }$ среднее значение распределения времени обслуживания S
• ${\displaystyle \rho =\lambda /\mu }$ это использование
• Вар (S) это отклонение распределения времени обслуживания S.

Для того чтобы средняя длина очереди была конечной, необходимо, чтобы ${\displaystyle \rho <1}$ в противном случае задания прибывают быстрее, чем покидают очередь. «Интенсивность трафика» находится в диапазоне от 0 до 1 и представляет собой среднюю долю времени, в течение которого сервер занят. Если скорость прибытия ${\displaystyle \lambda }$ больше или равно стоимости услуги ${\displaystyle \mu }$, задержка в очереди становится бесконечной. Член дисперсии входит в выражение из-за Парадокс Феллера.^[8]

Среднее время ожидания

Если мы напишем W в среднем время, которое клиент проводит в системе, то ${\displaystyle W=W'+\mu ^{-1}}$ где ${\displaystyle W'}$ - среднее время ожидания (время, проведенное в очереди в ожидании обслуживания) и ${\displaystyle \mu }$ ставка услуги. С помощью Закон Литтла, в котором говорится, что

${\displaystyle L=\lambda W}$

где

• L среднее количество клиентов в системе
• ${\displaystyle \lambda }$ скорость прибытия Пуассоновский процесс
• W среднее время, проведенное в очереди как в ожидании, так и на обслуживании,

так

${\displaystyle W={\frac {\rho +\lambda \mu {\text{Var}}(S)}{2(\mu -\lambda )}}+\mu ^{-1}.}$

Мы можем записать выражение для среднего времени ожидания как^[9]

${\displaystyle W'={\frac {L}{\lambda }}-\mu ^{-1}={\frac {\rho +\lambda \mu {\text{Var}}(S)}{2(\mu -\lambda )}}.}$

Преобразование длины очереди

Написание π (z) для функция, генерирующая вероятность от количества заявок в очереди^[10]

${\displaystyle \pi (z)={\frac {(1-z)(1-\rho )g(\lambda (1-z))}{g(\lambda (1-z))-z}}}$

где g (s) это Преобразование Лапласа функции плотности вероятности времени обслуживания.^[11]

Преобразование времени ожидания

Написание W^*(s) для Преобразование Лапласа – Стилтьеса распределения времени ожидания,^[10]

${\displaystyle W^{\ast }(s)={\frac {(1-\rho )s}{s-\lambda (1-g(s))}}}$

где снова g (s) это Преобразование Лапласа функции плотности вероятности времени обслуживания. пмоменты могут быть получены дифференцированием преобразования п раз, умножив на (−1)^п и оценка на s = 0.

использованная литература

1. Асмуссен, С. Р. (2003). «Случайные прогулки». Прикладная вероятность и очереди. Стохастическое моделирование и прикладная вероятность. 51. С. 220–243. Дои:10.1007/0-387-21525-5_8. ISBN  978-0-387-00211-8.
2. Поллачек, Ф. (1930). "Über eine Aufgabe der Wahrscheinlichkeitstheorie". Mathematische Zeitschrift. 32: 64–100. Дои:10.1007 / BF01194620.
3. Хинчин, А. (1932). «Математическая теория стационарной очереди». Математический сборник. 39 (4): 73–84. Получено 2011-07-14.
4. Такач, Лайош (1971). "Обзор: Дж. У. Коэн, Очередь на одном сервере". Анналы математической статистики. 42 (6): 2162–2164. Дои:10.1214 / aoms / 1177693087.
5. Кингман, Дж. Ф. С. (2009). «Первый век Эрланга - и следующий». Системы массового обслуживания. 63: 3–4. Дои:10.1007 / s11134-009-9147-4.
6. Рольски, Томаш; Шмидли, Ханспетер; Шмидт, Фолькер; Teugels, Йозеф (2008). «Риск-процессы». Стохастические процессы для страхования и финансов. Серия Уайли по вероятности и статистике. С. 147–204. Дои:10.1002 / 9780470317044.ch5. ISBN  9780470317044.
7. Хей, Джон (2002). Вероятностные модели. Springer. п. 192. ISBN  1-85233-431-2.
8. Купер, Роберт Б .; Ниу, Шун-Чен; Шринивасан, Мандьям М. (1998). "Некоторые размышления о парадоксе теории восстановления в теории массового обслуживания" (PDF). Журнал прикладной математики и стохастического анализа. 11 (3): 355–368. Получено 2011-07-14.
9. Харрисон, Питер Г.; Патель, Нареш М. (1992). Моделирование производительности сетей связи и компьютерных архитектур. Эддисон-Уэсли. п.228. ISBN  0-201-54419-9.
10. Дейгл, Джон Н. (2005). «Базовая система массового обслуживания M / G / 1». Теория массового обслуживания с приложениями к пакетной связи. С. 159–223. Дои:10.1007/0-387-22859-4_5. ISBN  0-387-22857-8.
11. Peterson, G.D .; Чемберлен, Р. Д. (1996). «Производительность параллельных приложений в среде общих ресурсов». Распределенная системная инженерия. 3: 9. Дои:10.1088/0967-1846/3/1/003.