Нотация Кендалла - Википедия - Kendalls notation

Схема очереди M / M / 1
Узел очередей M / M / 1

В теория массового обслуживания, дисциплина в рамках математической теория вероятности, Обозначения Кендалла (или иногда Обозначение Кендалла) - стандартная система, используемая для описания и классификации узлов очередей. Д. Г. Кендалл предложено описание моделей массового обслуживания с использованием трех факторов, записанных A / S /c в 1953 г.[1] где A обозначает время между поступлениями в очередь, S - распределение времени обслуживания и c количество каналов обслуживания, открытых в узле. С тех пор он был расширен до A / S /c/K/N/ D где K - вместимость очереди, N - это количество рабочих мест, которые необходимо обслуживать, а D - дисциплина в очереди.[2][3][4]

Если последние три параметра не указаны (например, M / M / 1 очередь ), предполагается K = ∞, N = ∞ и D =ФИФО.[5]

A: процесс прибытия

Код, описывающий процесс прибытия. Используемые коды:

СимволИмяОписаниеПримеры
MМарковский или без памяти[6]Пуассоновский процесс (или случайный) процесс прибытия (т.е. экспоненциальный время между прибытиями).M / M / 1 очередь
MИкспартия МарковаПуассоновский процесс со случайной величиной Икс по количеству заездов за один раз.MИкс/ МY/ 1 очередь
КАРТАМарковский процесс прибытияОбобщение пуассоновского процесса.
BMAPПакетный марковский процесс прибытияОбобщение КАРТА с многократным заездом
ММППМарковский модулированный пуассоновский процессПуассоновский процесс, при котором поступления находятся в «кластерах».
DВырожденное распределениеДетерминированное или фиксированное время между прибытиями.Очередь D / M / 1
EkРаспределение ErlangРаспределение Erlang с k как параметр формы (т.е. сумма k i.i.d. экспоненциальный случайные переменные).
граммОбщее распространениеНесмотря на то что грамм обычно относится к независимым поступлениям, некоторые авторы предпочитают использовать GI быть точным.
PHРаспределение фазового типаНекоторые из вышеупомянутых распределений являются частными случаями фазового типа, часто используемыми вместо общего распределения.

S: Распределение времени обслуживания

Это дает распределение времени обслуживания клиента. Вот некоторые общие обозначения:

СимволИмяОписаниеПримеры
MМарковский или без памяти[6]Экспоненциальный время обслуживания.M / M / 1 очередь
MYНавальный МарковЭкспоненциальный время обслуживания со случайной величиной Y за размер пакета лиц, обслуживаемых единовременно.MИкс/ МY/ 1 очередь
DВырожденное распределениеДетерминированное или фиксированное время обслуживания.Очередь M / D / 1
EkРаспределение ErlangРаспределение Erlang с k как параметр формы (т.е. сумма k i.i.d. экспоненциальный случайные переменные).
граммОбщее распространениеНесмотря на то что грамм обычно относится к автономному времени обслуживания, некоторые авторы предпочитают использовать GI быть точным.Очередь M / G / 1
PHРаспределение фазового типаНекоторые из вышеупомянутых распределений являются частными случаями фазового типа, часто используемыми вместо общего распределения.
ММППМарковский модулированный пуассоновский процессЭкспоненциальный распределения времени обслуживания, где параметр скорости управляется цепью Маркова.[7]

c: Количество серверов

Количество каналов обслуживания (или серверов). В M / M / 1 очередь имеет один сервер и M / M / c очередь c серверы.

K: количество мест в очереди

Емкость очереди или максимальное количество заявок, разрешенных в очереди. Когда число достигает этого максимума, дальнейшие прибытия не принимаются. Если это число не указано, предполагается, что емкость неограничена или бесконечна.

Примечание. Иногда это обозначается c + K куда K - размер буфера, количество мест в очереди над количеством серверовc.

N: вызывающее население

Размер источника вызова. Размер населения, из которого приходят клиенты. Небольшая популяция существенно повлияет на эффективный скорость прибытия, потому что чем больше заданий встает в очередь, тем меньше остается доступного для поступления в систему. Если это число не указано, предполагается, что численность населения неограничена или бесконечна.

D: Дисциплина очереди

Дисциплина обслуживания или приоритетный порядок обслуживания заданий в очереди или очереди ожидания:

СимволИмяОписание
FIFO / FCFSПервый пришел - первый ушел / первый пришел - первым обслуженКлиенты обслуживаются в том порядке, в котором они прибыли (используется по умолчанию).
LIFO / LCFSПоследний пришел - первый ушел / Последний пришел - первым обслуженКлиенты обслуживаются в порядке, обратном порядку, в котором они прибыли.
SIROОбслуживание в произвольном порядкеКлиенты обслуживаются в произвольном порядке, независимо от порядка прибытия.
PQПриоритетная очередьСуществует несколько вариантов: организация очереди с приоритетом с приоритетом, организация очереди без прерывания, организация взвешенной справедливой очереди на основе классов, взвешенная справедливая организация очереди.
PSСовместное использование процессораКлиенты обслуживаются в определенном порядке, независимо от порядка прибытия.
Примечание: Альтернативная практика записи состоит в том, чтобы записывать дисциплину очереди перед заполнением и емкостью системы с заключительными скобками или без них. Обычно это не вызывает путаницы, потому что обозначения другие.

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

  1. ^ Кендалл, Д. (1953). «Стохастические процессы, происходящие в теории массового обслуживания и их анализ методом вложенной цепи Маркова». Анналы математической статистики. 24 (3): 338–354. Дои:10.1214 / aoms / 1177728975. JSTOR  2236285.
  2. ^ Ли, Алек Миллер (1966). «Проблема стандартов обслуживания (Глава 15)». Прикладная теория массового обслуживания. Нью-Йорк: Макмиллан. ISBN  0-333-04079-1.
  3. ^ Таха, Хэмди А. (1968). Исследование операций: введение (Предварительная ред.).
  4. ^ Сен, Ратиндра П. (2010). Исследование операций: алгоритмы и приложения. Прентис-холл Индии. п. 518. ISBN  978-81-203-3930-9.
  5. ^ Гаутам, Н. (2007). «Теория массового обслуживания». Справочник по исследованиям операций и управлению. Серия исследований операций. 20073432. С. 1–2. Дои:10.1201 / 9781420009712.ch9. ISBN  978-0-8493-9721-9.
  6. ^ а б Zonderland, M.E .; Бушери, Р. Дж. (2012). «Сети массового обслуживания в системах здравоохранения». Справочник по планированию системы здравоохранения. Международная серия исследований по операциям и менеджменту. 168. п. 201. Дои:10.1007/978-1-4614-1734-7_9. ISBN  978-1-4614-1733-0.
  7. ^ Чжоу Юн-Пин; Ганс, Ноа (октябрь 1999 г.). "# 99-40-B: Очередь на одном сервере с временами обслуживания, модулированными по Маркову". Центр финансовых институтов, Wharton, UPenn. Получено 2011-01-11.