Обозначения Кендалла

В теории массового обслуживания , дисциплине математической теории вероятностей , нотация Кендалла (или иногда нотация Кендалла ) является стандартной системой, используемой для описания и классификации узла массового обслуживания. Д.Г. Кендалл предложил описывать модели массового обслуживания с использованием трех факторов, написанных 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 = FIFO . ^{[ 5 ]}

Первый пример: очередь M/M/1

Очередь M/M/1 означает, что время между поступлениями является марковским (M), т.е. время между поступлениями подчиняется экспоненциальному распределению параметра λ. Второе M означает, что время обслуживания является марковским: оно следует экспоненциальному распределению параметра μ. Последний параметр — это номер служебного канала, который один (1).

Описание параметров

В этом разделе мы описываем параметры A/S/ c / K / N /D слева направо.

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

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

Символ	Имя	Описание	Примеры
М	Марковские или безпамятные ^{[ 6 ]}	Пуассоновский процесс (или случайный) процесс поступления (т. е. экспоненциальное время между поступлениями).	Очередь М/М/1
М ^Х	партия Маркова	Пуассоновский процесс со случайной величиной X для количества одновременно прибывших.	М ^Х/М ^И/1 очередь
КАРТА	Марковский процесс прибытия	Обобщение процесса Пуассона.
БМАП	Пакетный марковский процесс прибытия	Обобщение MAP с множественными поступлениями
ММПП	Марковский модулированный пуассоновский процесс	Процесс Пуассона, при котором поступления группируются в «кластеры».
Д	Вырожденное распределение	Детерминированное или фиксированное время между прибытиями.	Очередь Д/М/1
я _к	Распределение Эрланга	Распределение Эрланга с k в качестве параметра формы (т. е. сумма k i.id ). экспоненциальных случайных величин
Г	Общее распространение	Хотя G обычно относится к независимым прибытиям, некоторые авторы предпочитают использовать GI для явного выражения.
PH	Распределение фазового типа	Некоторые из приведенных выше распределений представляют собой частные случаи фазового типа, часто используемые вместо общего распределения.

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

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

Символ	Имя	Описание	Примеры
М	Марковские или безпамятные ^{[ 6 ]}	Экспоненциальное время обслуживания.	Очередь М/М/1
М ^И	bulk Markov	Экспоненциальное время обслуживания со случайной величиной Y для размера пакета объектов, обслуживаемых одновременно.	М ^Х/М ^И/1 очередь
Д	Вырожденное распределение	Детерминированное или фиксированное время обслуживания.	Очередь М/Д/1
я _к	Распределение Эрланга	Распределение Эрланга с k в качестве параметра формы (т. е. сумма k i.id ). экспоненциальных случайных величин
Г	Общее распространение	Хотя G обычно относится к независимому времени обслуживания, некоторые авторы предпочитают использовать GI для явного обозначения.	Очередь M/G/1
PH	Распределение фазового типа	Некоторые из приведенных выше распределений представляют собой частные случаи фазового типа, часто используемые вместо общего распределения.
ММПП	Марковский модулированный пуассоновский процесс	Экспоненциальные распределения времени обслуживания, где параметр скорости контролируется цепью Маркова. ^{[ 7 ]}

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

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

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

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

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

N: Звонящая популяция

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

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

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

Символ	Имя	Описание
ФИФО/FCFS	«Первым пришел — первым ушел»/«Первым пришел — первым обслужен»	Клиенты обслуживаются в том порядке, в котором они прибыли (используется по умолчанию).
ЛИФО/LCFS	Последний пришёл — первым ушёл/Последним пришёл — первым обслужен	Клиенты обслуживаются в порядке, обратном тому, в котором они прибыли.
СИРО	Сервис в случайном порядке	Клиенты обслуживаются в случайном порядке, независимо от порядка прибытия.
ПК	Приоритетная очередь	Существует несколько вариантов: организация очереди с вытесняющим приоритетом, организация очереди без вытеснения, взвешенная справедливая организация очереди на основе классов, взвешенная справедливая организация очереди.
ПС	Совместное использование процессора	Клиенты обслуживаются в установленном порядке, независимо от порядка прибытия.

Примечание . Альтернативной практикой записи является запись дисциплины очереди перед заполнением и пропускной способностью системы, с закрывающими круглыми скобками или без них. Обычно это не вызывает путаницы, поскольку обозначения разные.

Ссылки

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

[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. ИСБН 978-81-203-3930-9 .

[5] Гаутам, Н. (2007). «Теория массового обслуживания». Справочник по исследованию операций и науке управления . Серия исследований операций. Том. 20073432. стр. 1–2. дои : 10.1201/9781420009712.ch9 . ISBN 978-0-8493-9721-9 .

[Zonderland-6] Jump up to: ^а ^б Зондерленд, Мэн; Бушери, Р.Дж. (2012). «Сети массового обслуживания в системах здравоохранения». Справочник по планированию системы здравоохранения . Международная серия по исследованию операций и науке управления. Том. 168. с. 201. дои : 10.1007/978-1-4614-1734-7_9 . ISBN 978-1-4614-1733-0 .

[7] Чжоу, Юн-Пин; Ганс, Ной (октябрь 1999 г.). «# 99-40-B: Очередь из одного сервера с марковским модулированным временем обслуживания» . Центр финансовых учреждений, Уортон, Университет Пенсильвании. Архивировано из оригинала 21 июня 2010 г. Проверено 11 января 2011 г.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

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