Нотация Кендалла

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

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

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

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

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

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

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

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

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

N: Звонящее население

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

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

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

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

Ссылки

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