М/Д/1 хвост

В теории массового обслуживания , дисциплине математической теории вероятностей , очередь M/D/1 представляет длину очереди в системе с одним сервером, где поступления определяются процессом Пуассона , а время обслуживания заданий фиксировано (детерминировано). Название модели написано в нотации Кендалла . Агнер Краруп Эрланг впервые опубликовал эту модель в 1909 году, положив начало теме теории массового обслуживания . Расширением этой модели с более чем одним сервером является очередь M/D/c .

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

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

• Поступления происходят со скоростью λ в соответствии с процессом Пуассона и переводят процесс из состояния i в состояние i + 1.
• Время обслуживания представляет собой детерминированное время D (обслуживание со скоростью µ = 1/ D ).
• Один сервер обслуживает объекты по одному, начиная с начала очереди, в соответствии с принципом «первым пришел — первым обслужен» . Когда обслуживание завершено, объект покидает очередь, и количество объектов в системе уменьшается на один.
• Буфер имеет бесконечный размер, поэтому количество сущностей, которые он может содержать, не ограничено.

Матрица перехода

Матрица вероятности перехода для очереди M/D/1 со скоростью поступления λ и временем обслуживания 1, такой что λ <1 (для стабильности очереди), определяется как P, как показано ниже:

$P={\begin{pmatrix}a_{0}&a_{1}&a_{2}&a_{3}&...\\a_{0}&a_{1}&a_{2}&a_{3}&...\\0&a_{0}&a_{1}&a_{2}&...\\0&0&a_{0}&a_{1}&...\\...&...&...&...&...\\\end{pmatrix}}$ ， $a_{n}={\frac {\lambda ^{n}}{n!}}e^{-\lambda }$, n = 0,1,....

Классические показатели производительности

Следующие выражения представляют классические показатели производительности системы массового обслуживания с одним сервером, такой как M/D/1, с:

• скорость прибытия $=\lambda$,
• ставка обслуживания $=\mu$, и
• использование $=\rho ={\frac {\lambda }{\mu }}$

Среднее количество объектов в системе L определяется следующим образом:

$L=\rho +{\frac {1}{2}}\left({\frac {\rho ^{2}}{1-\rho }}\right);$

Среднее количество объектов в очереди (линии), L _Q, определяется по формуле:

$L_{Q}={\frac {1}{2}}\left({\frac {\rho ^{2}}{1-\rho }}\right);$

Среднее время ожидания в системе ω определяется выражением:

$\omega ={\frac {1}{\mu }}+{\frac {\rho }{2\mu (1-\rho )}};$

Среднее время ожидания в очереди (линии) ω _Q определяется выражением:

$\omega _{Q}={\frac {\rho }{2\mu (1-\rho )}}$

Пример

Рассмотрим систему, имеющую только один сервер, со скоростью прибытия 20 объектов в час и постоянной скоростью обслуживания 30 в час.

Таким образом, загрузка сервера равна: ρ=20/30=2/3. Используя приведенные выше метрики, результаты следующие: 1) Среднее число в строке L _Q = 0,6667; 2) Среднее число в системе L =1,333; 3) Среднее время в линии ω _Q = 0,033 часа; 4) Среднее время в системе ω = 0,067 часа.

Соотношения для среднего времени ожидания в очередях M/M/1 и M/D/1

Для равновесной очереди M/G/1 ожидаемое значение времени W, проведенного клиентом в очереди, определяется формулой Поллачека-Хинчина, как показано ниже:

$E(W)={\frac {\rho \tau }{2(1-\rho )}}\left(1+{\frac {\sigma ^{2}}{\tau ^{2}}}\right)$

где τ — среднее время обслуживания; σ ² – дисперсия времени обслуживания; и ρ=λτ < 1, λ — скорость поступления заявок.

Для очереди M/M/1 времена обслуживания распределены экспоненциально, тогда σ ² = т ² а среднее время ожидания в очереди, обозначенное WM _, определяется следующим уравнением:

${W_{M}}={\frac {\rho \tau }{1-\rho }}$

Используя это, можно вывести соответствующее уравнение для очереди M/D/1, предполагая постоянное время обслуживания. Тогда дисперсия времени обслуживания становится равной нулю, т.е. σ ² = 0. Среднее время ожидания в очереди M/D/1, обозначенное как WD _, определяется следующим уравнением:

${W_{D}}={\frac {\rho \tau }{2(1-\rho )}}$

Из двух приведенных выше уравнений мы можем сделать вывод, что средняя длина очереди в очереди M/M/1 вдвое больше, чем в очереди M/D/1.

Стационарное распределение

Количество заданий в очереди можно записать как цепь Маркова типа M/G/1 , а стационарное распределение, найденное для состояния i (обозначенное π _i ), в случае D = 1 будет

${\begin{aligned}\pi _{0}&=1-\lambda \\\pi _{1}&=(1-\lambda )(e^{\lambda }-1)\\\pi _{n}&=(1-\lambda )\left(e^{n\lambda }+\sum _{k=1}^{n-1}e^{k\lambda }(-1)^{n-k}\left[{\frac {(k\lambda )^{n-k}}{(n-k)!}}+{\frac {(k\lambda )^{n-k-1}}{(n-k-1)!}}\right]\right)\quad (n\geq 2).\end{aligned}}$

Задерживать

Определим ρ = λ / µ как коэффициент использования; тогда средняя задержка в системе в очереди M/D/1 равна

${\frac {1}{2\mu }}\cdot {\frac {2-\rho }{1-\rho }}.$

и в очереди:

${\frac {1}{2\mu }}\cdot {\frac {\rho }{1-\rho }}.$

Напряженный период

Период занятости — это период времени, измеряемый с момента прибытия первого клиента в пустую очередь до момента, когда очередь снова становится пустой. Этот период времени равен D , умноженному на количество обслуженных клиентов. Если ρ < 1, то количество обслуженных заявок в период занятости очереди имеет борелевское распределение с параметром ρ .

Конечная емкость

Стационарное распределение

Стационарное распределение количества клиентов в очереди и средней длины очереди можно вычислить с помощью функций, генерирующих вероятность .

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

Переходное решение очереди M/D/1 конечной емкости N, часто обозначаемой M/D/1/N, было опубликовано Гарсиа и др. в 2002 году.

Приложение

Включает в себя приложения для проектирования глобальных сетей , где один центральный процессор считывает заголовки пакетов, поступающих в экспоненциальном порядке, затем вычисляет следующий адаптер, к которому должен идти каждый пакет, и соответствующим образом отправляет пакеты. Здесь время обслуживания — это обработка заголовка пакета и проверка циклическим избыточным кодом, которые не зависят от длины каждого пришедшего пакета. Следовательно, ее можно смоделировать как очередь M/D/1.