Очередь М/М/1

В теории массового обслуживания , дисциплине математической теории вероятностей , очередь M/M/1 представляет длину очереди в системе с одним сервером, где поступления определяются процессом Пуассона , а время обслуживания заданий имеет экспоненциальное распределение . Название модели написано в нотации Кендалла . Модель является самой элементарной из моделей массового обслуживания. ^[1] и привлекательный объект исследования в виде выражений в замкнутой форме может быть получен для многих показателей, представляющих интерес в этой модели. Расширением этой модели с более чем одним сервером является очередь M/M/c .

Определение модели

Очередь M/M/1 — это случайный процесс, пространство состояний которого представляет собой набор {0,1,2,3,...}, где значение соответствует количеству клиентов в системе, включая всех, кто в данный момент обслуживается.

Поступления происходят со скоростью λ в соответствии с процессом Пуассона и переводят процесс из состояния i в состояние i + 1.
Время обслуживания имеет экспоненциальное распределение с параметром скорости μ в очереди M/M/1, где 1/μ — среднее время обслуживания.
Все времена прибытия и времени обслуживания (обычно) считаются независимыми друг от друга. ^[2]
Один сервер обслуживает клиентов по одному, начиная с начала очереди, в соответствии с принципом «первым пришел — первым обслужен» . По завершении обслуживания клиент покидает очередь, и количество клиентов в системе уменьшается на одного.
Буфер имеет бесконечный размер, поэтому количество клиентов, которые он может содержать, не ограничено.

Модель можно описать как цепь Маркова с непрерывным временем и матрицей скорости перехода.

Q={\begin{pmatrix}-\lambda &\lambda \\\mu &-(\mu +\lambda )&\lambda \\&\mu &-(\mu +\lambda )&\lambda \\&&\mu &-(\mu +\lambda )&\lambda &\\&&&&\ddots \end{pmatrix}}

в пространстве состояний {0,1,2,3,...}. Это та же непрерывная по времени цепь Маркова, что и в процессе рождения-смерти . Диаграмма пространства состояний для этой цепочки показана ниже.

Стационарный анализ

Модель считается устойчивой только в том случае, если λ < µ. Если в среднем прибытие происходит быстрее, чем завершение обслуживания, очередь будет расти бесконечно долго, и система не будет иметь стационарного распределения. Стационарное распределение является предельным распределением для больших значений t .

Различные показатели производительности могут быть вычислены явно для очереди M/M/1. Мы пишем ρ = λ/μ для использования буфера и требуем ρ < 1, чтобы очередь была стабильной. ρ представляет собой среднюю долю времени, в течение которого сервер занят.

Вероятность того, что стационарный процесс находится в состоянии i (содержит i заявок, в том числе находящихся в обслуживании), равна ^[3]^{: 172–173}

\pi _{i}=(1-\rho )\rho ^{i}.\,

Среднее количество клиентов в системе

Мы видим, что количество заявок в системе геометрически распределено с параметром 1 − ρ . Таким образом, среднее количество заявок в системе равно ρ /(1 − ρ ), а дисперсия количества заявок в системе равна ρ /(1 – ρ ). ². Этот результат справедлив для любого режима обслуживания, сохраняющего работу, такого как совместное использование процессора. ^[4]

Период занятости сервера

Период занятости — это период времени, измеряемый с момента прибытия клиента в пустую систему до момента его ухода, оставив после себя пустую систему. Период занятости имеет функцию плотности вероятности ^[5]^[6]^[7]^[8]

f(t)={\begin{cases}{\frac {1}{t{\sqrt {\rho }}}}e^{-(\lambda +\mu )t}I_{1}(2t{\sqrt {\lambda \mu }})&t>0\\0&{\text{otherwise}}\end{cases}}

где I ₁ — модифицированная функция Бесселя первого рода , ^[9] полученное с помощью преобразований Лапласа и обращения решения. ^[10]

Преобразование Лапласа периода занятости M/M/1 определяется выражением ^[11]^[12]^[13]^: 215

\mathbb {E} (e^{-sF})={\frac {1}{2\lambda }}(\lambda +\mu +s-{\sqrt {(\lambda +\mu +s)^{2}-4\lambda \mu }})

который дает моменты периода занятости, в частности, среднее значение равно 1/( µ − λ ), а дисперсия определяется выражением

{\frac {1+{\frac {\lambda }{\mu }}}{\mu ^{2}(1-{\frac {\lambda }{\mu }})^{3}}}.

Время ответа

Среднее время ответа или время пребывания (общее время, которое клиент проводит в системе) не зависит от дисциплины планирования и может быть рассчитано с использованием закона Литтла как 1/( μ − λ ). Среднее время, затраченное на ожидание, составляет 1/( µ − λ ) − 1/ µ = ρ /( µ − λ ). Распределение времени отклика действительно зависит от дисциплины планирования.

Дисциплина в порядке очереди

Для клиентов, которые приходят и обнаруживают, что очередь представляет собой стационарный процесс, время ответа, которое они испытывают (сумма времени ожидания и времени обслуживания), имеет преобразование Лапласа.( µ - λ )/( s + µ - λ ) ^[14] и, следовательно, функция плотности вероятности ^[15]

f(t)={\begin{cases}(\mu -\lambda )e^{-(\mu -\lambda )t}&t>0\\0&{\text{otherwise.}}\end{cases}}

Дисциплина совместного использования процессоров

В очереди M/M/1-PS нет очереди ожидания, и все задания получают равную долю мощности обслуживания. ^[16] Предположим, что один сервер обслуживается со скоростью 16 и в системе имеется 4 задания, каждое задание будет обслуживаться со скоростью 4. Скорость, с которой задания получают обслуживание, меняется каждый раз, когда задание поступает в систему или покидает ее. ^[16]

Для клиентов, которые приходят и обнаруживают, что очередь представляет собой стационарный процесс, в 1970 году было опубликовано преобразование Лапласа распределения времени отклика, с которым сталкиваются клиенты: ^[16] для которого известно интегральное представление. ^[17] Распределение времени ожидания (время ответа минус время обслуживания) для клиента, которому требуется x объем услуг, изменилось. ^[3]^: 356

W^{\ast }(s|x)={\frac {(1-\rho )(1-\rho r^{2})e^{-[\lambda (1-r)+s]x}}{(1-\rho r^{2})-\rho (1-r)^{2}e^{-(\mu /r-\lambda r)x}}}

где r — меньший корень уравнения

\lambda r^{2}-(\lambda +\mu +s)r+\mu =0.

Таким образом , среднее время ответа для поступающего задания, требующего объема обслуживания x , можно вычислить как x µ /( µ − λ ). Альтернативный подход позволяет получить те же результаты, используя метод спектрального разложения . ^[4]

Переходное решение

Мы можем написать функцию вероятности, зависящую от t, чтобы описать вероятность того, что очередь M/M/1 находится в определенном состоянии в данный момент времени. что очередь изначально находится в состоянии i , и записываем pk _{Мы предполагаем ,} ( t ) для вероятности нахождения в состоянии k в момент времени t . Затем ^[2]^[18]

p_{k}(t)=e^{-(\lambda +\mu )t}\left[\rho ^{\frac {k-i}{2}}I_{k-i}(at)+\rho ^{\frac {k-i-1}{2}}I_{k+i+1}(at)+(1-\rho )\rho ^{k}\sum _{j=k+i+2}^{\infty }\rho ^{-j/2}I_{j}(at)\right]

где $i$ - начальное количество клиентов на станции в данный момент $t=0$ , $\rho =\lambda /\mu$ , $a=2{\sqrt {\lambda \mu }}$ и $I_{k}$ — модифицированная функция Бесселя первого рода . Моменты переходного решения можно выразить как сумму двух монотонных функций . ^[19]

Диффузионное приближение

Когда коэффициент использования ρ близок к 1, процесс можно аппроксимировать отраженным броуновским движением с параметром дрейфа λ – µ и параметром дисперсии λ + µ . Это ограничение интенсивного трафика было впервые введено Джоном Кингманом . ^[20]

Ссылки

^ Стургул, Джон Р. (2000). Проектирование шахты: примеры с использованием моделирования . МСП. п. VI. ISBN 0-87335-181-9 .
^ Jump up to: ^а ^б Кляйнрок, Леонард (1975). Системы массового обслуживания Том 1: Теория . п. 77. ИСБН 0471491101 .
^ Jump up to: ^а ^б Харрисон, Питер ; Патель, Нареш М. (1992). Моделирование производительности сетей связи и компьютерных архитектур . Аддисон-Уэсли.
^ Jump up to: ^а ^б Гиймен, Ф.; Бойер, Дж. (2001). «Анализ очереди M/M/1 с совместным использованием процессора с помощью спектральной теории» (PDF) . Системы массового обслуживания . 39 (4): 377. doi : 10.1023/A:1013913827667 . Архивировано из оригинала (PDF) 29 ноября 2006 г.
^ Абате, Дж.; Уитт, В. (1988). «Простые спектральные представления для очереди M/M/1» (PDF) . Системы массового обслуживания . 3 (4): 321. дои : 10.1007/BF01157854 .
^ Кейлсон, Дж.; Кухарян, А. (1960). «Процессы массового обслуживания, зависящие от времени» . Анналы математической статистики . 31 (1): 104–112. дои : 10.1214/aoms/1177705991 . JSTOR 2237497 .
^ Карлин, Сэмюэл ; МакГрегор, Джеймс (1958). «Многие серверные процессы организации очередей с входными данными Пуассона и экспоненциальным временем обслуживания» (PDF) . Пасифик Дж. Математика . 8 (1): 87–118. дои : 10.2140/pjm.1958.8.87 . МР 0097132 .
^ Гросс, Дональд; Шортл, Джон Ф.; Томпсон, Джеймс М.; Харрис, Карл М. (23 сентября 2011 г.). «2.12 Анализ периода занятости». Основы теории массового обслуживания . Уайли. ISBN 1118211642 .
^ Адан, Иво. «Курс QUE: Теория массового обслуживания, осень 2003 г.: Система M/M/1» (PDF) . Проверено 6 августа 2012 г.
^ Стюарт, Уильям Дж. (2009). Вероятность, цепи Маркова, очереди и моделирование: математическая основа моделирования производительности . Издательство Принстонского университета. п. 530 . ISBN 978-0-691-14062-9 .
^ Асмуссен, СР (2003). «Теория массового обслуживания на марковском уровне». Прикладная вероятность и очереди . Стохастическое моделирование и прикладная теория вероятности. Том. 51. С. 60–31. дои : 10.1007/0-387-21525-5_3 . ISBN 978-0-387-00211-8 .
^ Адан, И.; Резинг, Дж. (1996). «Простой анализ гибкой очереди, управляемой очередью M/M/1». Системы массового обслуживания . 22 (1–2): 171–174. дои : 10.1007/BF01159399 .
^ Кляйнрок, Леонард (1975). Системы массового обслуживания: Теория, Том 1 . Уайли. ISBN 0471491101 .
^ Харрисон, П.Г. (1993). «Распределение времени отклика в моделях сетей массового обслуживания». Оценка производительности компьютерных и коммуникационных систем . Конспекты лекций по информатике. Том. 729. стр. 147–164. дои : 10.1007/BFb0013852 . ISBN 3-540-57297-Х .
^ Стюарт, Уильям Дж. (2009). Вероятность, цепи Маркова, очереди и моделирование: математическая основа моделирования производительности . Издательство Принстонского университета. п. 409 . ISBN 978-0-691-14062-9 .
^ Jump up to: ^а ^б ^с Коффман, Э.Г .; Мунц, РР; Троттер, Х. (1970). «Распределение времени ожидания для систем совместного использования процессоров» . Журнал АКМ . 17 : 123–130. дои : 10.1145/321556.321568 .
^ Моррисон, Дж. А. (1985). «Распределение времени отклика для системы совместного использования процессоров». SIAM Journal по прикладной математике . 45 (1): 152–167. дои : 10.1137/0145007 . JSTOR 2101088 .
^ Робертацци, Томас Г. (2000). Компьютерные сети и системы . Нью-Йорк, штат Нью-Йорк: Springer New York. п. 72. дои : 10.1007/978-1-4612-1164-8 . ISBN 978-1-4612-7029-4 .
^ Абате, Дж.; Уитт, В. (1987). «Переходное поведение очереди M/M/l: начиная с источника» (PDF) . Системы массового обслуживания . 2 : 41–65. дои : 10.1007/BF01182933 .
^ Кингман, JFC ; Атья (октябрь 1961 г.). «Очередь на одном сервере при интенсивном трафике». Математические труды Кембриджского философского общества . 57 (4): 902. doi : 10.1017/S0305004100036094 . JSTOR 2984229 .

[1] Стургул, Джон Р. (2000). Проектирование шахты: примеры с использованием моделирования . МСП. п. VI. ISBN 0-87335-181-9 .

[Kleinrock-2] Jump up to: ^а ^б Кляйнрок, Леонард (1975). Системы массового обслуживания Том 1: Теория . п. 77. ИСБН 0471491101 .

[harrison-3] Jump up to: ^а ^б Харрисон, Питер ; Патель, Нареш М. (1992). Моделирование производительности сетей связи и компьютерных архитектур . Аддисон-Уэсли.

[guillemin-4] Jump up to: ^а ^б Гиймен, Ф.; Бойер, Дж. (2001). «Анализ очереди M/M/1 с совместным использованием процессора с помощью спектральной теории» (PDF) . Системы массового обслуживания . 39 (4): 377. doi : 10.1023/A:1013913827667 . Архивировано из оригинала (PDF) 29 ноября 2006 г.

[5] Абате, Дж.; Уитт, В. (1988). «Простые спектральные представления для очереди M/M/1» (PDF) . Системы массового обслуживания . 3 (4): 321. дои : 10.1007/BF01157854 .

[6] Кейлсон, Дж.; Кухарян, А. (1960). «Процессы массового обслуживания, зависящие от времени» . Анналы математической статистики . 31 (1): 104–112. дои : 10.1214/aoms/1177705991 . JSTOR 2237497 .

[7] Карлин, Сэмюэл ; МакГрегор, Джеймс (1958). «Многие серверные процессы организации очередей с входными данными Пуассона и экспоненциальным временем обслуживания» (PDF) . Пасифик Дж. Математика . 8 (1): 87–118. дои : 10.2140/pjm.1958.8.87 . МР 0097132 .

[8] Гросс, Дональд; Шортл, Джон Ф.; Томпсон, Джеймс М.; Харрис, Карл М. (23 сентября 2011 г.). «2.12 Анализ периода занятости». Основы теории массового обслуживания . Уайли. ISBN 1118211642 .

[9] Адан, Иво. «Курс QUE: Теория массового обслуживания, осень 2003 г.: Система M/M/1» (PDF) . Проверено 6 августа 2012 г.

[stewart-10] Стюарт, Уильям Дж. (2009). Вероятность, цепи Маркова, очереди и моделирование: математическая основа моделирования производительности . Издательство Принстонского университета. п. 530 . ISBN 978-0-691-14062-9 .

[11] Асмуссен, СР (2003). «Теория массового обслуживания на марковском уровне». Прикладная вероятность и очереди . Стохастическое моделирование и прикладная теория вероятности. Том. 51. С. 60–31. дои : 10.1007/0-387-21525-5_3 . ISBN 978-0-387-00211-8 .

[12] Адан, И.; Резинг, Дж. (1996). «Простой анализ гибкой очереди, управляемой очередью M/M/1». Системы массового обслуживания . 22 (1–2): 171–174. дои : 10.1007/BF01159399 .

[13] Кляйнрок, Леонард (1975). Системы массового обслуживания: Теория, Том 1 . Уайли. ISBN 0471491101 .

[14] Харрисон, П.Г. (1993). «Распределение времени отклика в моделях сетей массового обслуживания». Оценка производительности компьютерных и коммуникационных систем . Конспекты лекций по информатике. Том. 729. стр. 147–164. дои : 10.1007/BFb0013852 . ISBN 3-540-57297-Х .

[15] Стюарт, Уильям Дж. (2009). Вероятность, цепи Маркова, очереди и моделирование: математическая основа моделирования производительности . Издательство Принстонского университета. п. 409 . ISBN 978-0-691-14062-9 .

[coffman-16] Jump up to: ^а ^б ^с Коффман, Э.Г .; Мунц, РР; Троттер, Х. (1970). «Распределение времени ожидания для систем совместного использования процессоров» . Журнал АКМ . 17 : 123–130. дои : 10.1145/321556.321568 .

[17] Моррисон, Дж. А. (1985). «Распределение времени отклика для системы совместного использования процессоров». SIAM Journal по прикладной математике . 45 (1): 152–167. дои : 10.1137/0145007 . JSTOR 2101088 .

[18] Робертацци, Томас Г. (2000). Компьютерные сети и системы . Нью-Йорк, штат Нью-Йорк: Springer New York. п. 72. дои : 10.1007/978-1-4612-1164-8 . ISBN 978-1-4612-7029-4 .

[19] Абате, Дж.; Уитт, В. (1987). «Переходное поведение очереди M/M/l: начиная с источника» (PDF) . Системы массового обслуживания . 2 : 41–65. дои : 10.1007/BF01182933 .

[20] Кингман, JFC ; Атья (октябрь 1961 г.). «Очередь на одном сервере при интенсивном трафике». Математические труды Кембриджского философского общества . 57 (4): 902. doi : 10.1017/S0305004100036094 . JSTOR 2984229 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

v т и Теория массового обслуживания
Одиночные узлы массового обслуживания	Д/М/1 хвост М/Д/1 хвост М/Д/Ц хвост Очередь М/М/1 Теорема Берка Очередь М/М/Ц Очередь М/М/∞ Очередь M/G/1 Формула Поллачека – Хинчина Матричный аналитический метод Очередь M/G/k Очередь G/M/1 Очередь G/G/1 Формула Кингмана Уравнение Линдли Разветвить очередь – присоединиться к ней Массовая очередь
Процессы прибытия	Точный процесс Пуассона Марковский процесс прибытия Рациональный процесс прибытия
Сети массового обслуживания	Сеть Джексона Уравнения дорожного движения Теорема Гордона – Ньюэлла Анализ среднего значения Алгоритм Бузена сеть Келли G-сеть Сеть BCMP
Политика обслуживания	ФИФО ЛИФО Совместное использование процессора Круговой Самая короткая работа следующая Кратчайшее оставшееся время
Ключевые понятия	Цепь Маркова с непрерывным временем Обозначения Кендалла Закон Литтла Решение в форме продукта Уравнение баланса Квазиобратимость Потоко-эквивалентный серверный метод Теорема о прибытии Метод разложения метод Бенеша
Предельные теоремы	Предел жидкости Теория среднего поля Приближение интенсивного движения Отраженное броуновское движение
Расширения	Жидкая очередь Многоуровневая сеть массового обслуживания Система опроса Состязательная сеть массового обслуживания Сеть потерь Очередь повторных попыток
Информационные системы	Буфер данных Эрланг (единица измерения) Распределение Эрланга Управление потоком (данные) Очередь сообщений Перегрузка сети Сетевой планировщик Конвейер (программное обеспечение) Качество обслуживания Планирование (вычисления) Телетрафик инжиниринг
Категория

v т и Случайные процессы
Дискретное время	Процесс Бернулли Процесс ветвления процесс в китайском ресторане Процесс Гальтона – Ватсона Независимые и одинаково распределенные случайные величины Цепь Маркова Процесс Морана Случайное блуждание Петля стерта Самоизбегание Пристрастный Максимальная энтропия
Непрерывное время	Аддитивный процесс Бессельский процесс Процесс рождения-смерти чистое рождение Броуновское движение Мост Экскурсия Дробный Геометрический Меандр Процесс Коши Контактный процесс Случайное блуждание в непрерывном времени Процесс Кокса Процесс диффузии Броуновское движение Дайсона Эмпирический процесс Валочный процесс Процесс Флеминга-Вио Гамма-процесс Геометрический процесс Процесс Хоукса Процесс охоты Взаимодействующие системы частиц Диффузия Ито Ито-процесс Прыжковая диффузия Процесс перехода Процесс Леви Местное время Марковский аддитивный процесс Процесс Маккина – Власова Процесс Орнштейна – Уленбека Пуассоновский процесс Сложный Неоднородный Эволюция Шрамма – Лёвнера Семимартингалы Сигма-мартингейл Стабильный процесс Суперпроцесс Телеграфный процесс Дисперсионный гамма-процесс Винеровский процесс Венская колбаса
Оба	Процесс ветвления Гауссов процесс Скрытая модель Маркова (HMM) Марковский процесс Мартингейл Различия Местный Суб- Супер- Случайная динамическая система Регенеративный процесс Процесс продления Стохастические цепочки с памятью переменной длины Белый шум
Поля и прочее	Процесс Дирихле Гауссово случайное поле Мера Гиббса Модель Хопфилда Модель Изинга Модель Поттса Логическая сеть Марковское случайное поле перколяция Процесс Питмана-Йора Точечный процесс Кокс Пуассон Случайное поле Случайный график
Модели временных рядов	Модель авторегрессионной условной гетероскедастичности (ARCH) Модель авторегрессионного интегрированного скользящего среднего (ARIMA) Авторегрессионная (AR) модель Модель авторегрессии – скользящего среднего (ARMA) Модель обобщенной авторегрессии условной гетероскедастичности (GARCH) Модель скользящего среднего (MA)
Финансовые модели	Модель ценообразования биномиальных опционов Черный–Дерман–Игрушка Блэк – Карасински Блэк – Скоулз Чан – Каройи – Лонгстафф – Сандерс (CKLS) Чен Постоянная эластичность отклонения (CEV) Кокс – Ингерсолл – Росс (CIR) Гарман-Кольхаген Хит – Джарроу – Мортон (HJM) Хестон Хо-Ли Корпус – Белый Корн-Креер-Ленссен рынок ЛИБОР Рендлман-Барттер Волатильность SABR Ваш Уилки
Актуарные модели	Бюльманн Крамер-Лундберг Процесс риска Спарре-Андерсон
Модели массового обслуживания	Масса Жидкость Обобщенная сеть массового обслуживания М/Г/1 М/М/1 М/М/с
Характеристики	Тропы Кадлага Непрерывный Непрерывные пути Эргодический Сменный Феллер-непрерывный Гаусс–Марков Марков Смешивание Кусочно-детерминированный Предсказуемый Постепенно измеримый Самоподобный Стационарный обратимый во времени
Предельные теоремы	Центральная предельная теорема Теорема Донскера Теоремы о мартингальной сходимости Дуба Эргодическая теорема Теорема Фишера – Типпетта – Гнеденко. Принцип большого отклонения Закон больших чисел (слабый/сильный) Закон повторного логарифма Максимальная эргодическая теорема Теорема Санова Законы нуля–единицы ( Блюменталь , Борель–Кантелли , Энгельберт–Шмидт , Хьюитт–Сэвидж , Колмогоров , Леви )
Неравенства	Беркхолдер – Дэвис – Ганди Мартингейл Дуба Апкросс Дуба Кунита – Ватанабэ Марцинкевич–Зигмунд
Инструменты	Формула Кэмерона-Мартина Сходимость случайных величин Экспонента Долеана-Дада Теорема Дуба о разложении Теорема Дуба – Мейера о разложении Необязательная теорема Дуба об остановке Формула Дынкина Формула Фейнмана – Каца Фильтрация Girsanov theorem Infinitesimal generator Itô integral Itô's lemma Karhunen–Loève theorem Kolmogorov continuity theorem Kolmogorov extension theorem Lévy–Prokhorov metric Malliavin calculus Martingale representation theorem Optional stopping theorem Prokhorov's theorem Quadratic variation Reflection principle Skorokhod integral Skorokhod's representation theorem Skorokhod space Snell envelope Stochastic differential equation Tanaka Stopping time Stratonovich integral Uniform integrability Usual hypotheses Wiener space Classical Abstract
Disciplines	Actuarial mathematics Control theory Econometrics Ergodic theory Extreme value theory (EVT) Large deviations theory Mathematical finance Mathematical statistics Probability theory Queueing theory Renewal theory Ruin theory Signal processing Statistics Stochastic analysis Time series analysis Machine learning
List of topics Category