Очередь G/G/1
В теории массового обслуживания , дисциплине математической теории вероятностей , очередь G/G/1 представляет длину очереди в системе с одним сервером, где время между прибытиями имеет общее (то есть произвольное) распределение, а время обслуживания имеет (различное) распределение. общее распространение. [1] Эволюцию очереди можно описать уравнением Линдли . [2]
Система описывается в обозначениях Кендалла , где G обозначает общее распределение времени между поступлениями и времени обслуживания, а 1 означает, что модель имеет один сервер. [3] [4] Различные времена прибытия и обслуживания считаются независимыми, и иногда модель обозначается GI/GI/1, чтобы подчеркнуть это. Численное решение для GI/G/1 можно получить путем дискретизации времени. [5]
Время ожидания
[ редактировать ]Формула Кингмана дает приблизительное значение среднего времени ожидания в очереди G/G/1. [6] Интегральное уравнение Линдли представляет собой соотношение, которому удовлетворяет стационарное распределение времени ожидания, которое можно решить с помощью метода Винера – Хопфа . [7]
Несколько серверов
[ редактировать ]известно немного результатов, Для общей модели G/G/ k поскольку она обобщает очередь M/G/k , для которой известно мало метрик. Границы могут быть вычислены с использованием методов анализа средних значений , адаптации результатов модели очереди M/M/c , использования приближений к интенсивному трафику и эмпирических результатов. [8] : 189 [9] или аппроксимация распределений распределениями фазового типа с последующим использованием методов матричного анализа для решения приближенных систем. [8] : 201
Известно, что в очереди G/G/2 с объемами заданий с тяжелыми хвостами хвост распределения времени задержки ведет себя как хвост экспоненциального распределения, возведенного в квадрат при низких нагрузках, и как хвост экспоненциального распределения при высоких нагрузках. [10] [11] [12]
Ссылки
[ редактировать ]- ^ Бхат, ООН (2008). «Общая очередь G/G/1 и приближения». Введение в теорию массового обслуживания . стр. 169–183 . дои : 10.1007/978-0-8176-4725-4_9 . ISBN 978-0-8176-4724-7 .
- ^ Фосс, С. (2011). «Очередь G/G/1». Энциклопедия исследований операций и науки управления Wiley . дои : 10.1002/9780470400531.eorms0878 . ISBN 9780470400531 .
- ^ Кендалл, генеральный директор (1953). «Стохастические процессы, возникающие в теории массового обслуживания, и их анализ методом вложенной цепи Маркова» . Анналы математической статистики . 24 (3): 338. doi : 10.1214/aoms/1177728975 . JSTOR 2236285 .
- ^ Смит, WL (1953). «О распределении времени ожидания». Математические труды Кембриджского философского общества . 49 (3): 449. Бибкод : 1953PCPS...49..449S . дои : 10.1017/S0305004100028620 .
- ^ Грассманн, Винфрид; Таваколи, Джавад (июнь 2019 г.). «Распределение длины строки в очереди GI/G/1 дискретного времени». Оценка производительности . 131 : 43–53.
- ^ Кингман, JFC ; Атья (октябрь 1961 г.). «Очередь на одном сервере при интенсивном трафике». Математические труды Кембриджского философского общества . 57 (4): 902. Бибкод : 1961PCPS...57..902K . дои : 10.1017/S0305004100036094 . JSTOR 2984229 .
- ^ Прабху, Нью-Йорк (1974). «Методы Винера-Хопфа в теории массового обслуживания». Математические методы в теории массового обслуживания . Конспект лекций по экономике и математическим системам. Том. 98. стр. 81–90. дои : 10.1007/978-3-642-80838-8_5 . ISBN 978-3-540-06763-4 .
- ^ Перейти обратно: а б Гаутам, Натараджан (2012). Анализ очередей: методы и приложения . ЦРК Пресс. ISBN 9781439806586 .
- ^ Уитт, В. (2009). «Приближения для очереди GI/G/m» (PDF) . Управление производством и эксплуатацией . 2 (2): 114–161. дои : 10.1111/j.1937-5956.1993.tb00094.x .
- ^ Хархол-Балтер, М. (2012). «Политики назначения задач для серверных ферм». Моделирование производительности и проектирование компьютерных систем . п. 408. дои : 10.1017/CBO9781139226424.031 . ISBN 9781139226424 .
- ^ Уитт, В. (2000). «Влияние распределения времени обслуживания с тяжелым хвостом на распределение времени ожидания M/GI/s» (PDF) . Системы массового обслуживания . 36 : 71–87. дои : 10.1023/А:1019143505968 .
- ^ Фосс, С.; Коршунов, Д. (2006). «Тяжелые хвосты в многосерверной очереди». Системы массового обслуживания . 52:31 . arXiv : 1303.4705 . дои : 10.1007/s11134-006-3613-z .
| Одиночные узлы массового обслуживания | |
|---|---|
| Процессы прибытия | |
| Сети массового обслуживания | |
| Политика обслуживания | |
| Ключевые понятия | |
| Предельные теоремы | |
| Расширения | |
| Информационные системы | |
