Очередь G/M/1

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

Поступление очереди G/M/1 определяется процессом обновления . Это расширение очереди M/M/1 , где этот процесс обновления должен быть, в частности, процессом Пуассона (так, чтобы время между поступлениями имело экспоненциальное распределение).

Модели этого типа можно решить, рассмотрев одну из двух двойственных систем очередей M/G/1 : одну, предложенную Рамасвами, и одну Брайтом.

Размер очереди во время прибытия

Позволять $(X_{t},t\geq 0)$ быть $G/M(\mu )/1$ очередь со временем прибытия $(A_{n},n\in \mathbb {N} )$ которые имеют распределение между поступлениями A . Определите размер очереди непосредственно перед n- м прибытием процесса. $U_{n}=X_{A_{n}-}$. Это цепь Маркова с дискретным временем и стохастической матрицей :

$P={\begin{pmatrix}1-a_{0}&a_{0}&0&0&0&\cdots \\1-(a_{0}+a_{1})&a_{1}&a_{0}&0&0&\cdots \\1-(a_{0}+a_{1}+a_{2})&a_{2}&a_{1}&a_{0}&0&\cdots \\1-(a_{0}+a_{1}+a_{2}+a_{3})&a_{3}&a_{2}&a_{1}&a_{0}&\cdots \\\vdots &\vdots &\vdots &\vdots &\vdots &\ddots \end{pmatrix}}$

где $a_{v}=\mathbb {E} \left({\frac {(\mu X)^{v}e^{-\mu A}}{v!}}\right)$.

Цепь Маркова $U_{n}$ имеет стационарное распределение тогда и только тогда, когда интенсивность движения $\rho =(\mu \mathbb {E} (A))^{-1}$ меньше 1, и в этом случае единственным таким распределением является геометрическое распределение с вероятностью $\eta$ неудачи, где $\eta$ — наименьший корень уравнения $\mathbb {E} (\exp(\mu (\eta -1)A))$.

В этом случае, если предположить, что очередь организована по принципу «первым пришел — первым обслужен» (FIFO), время ожидания клиента W распределяется по формуле:

$\mathbb {P} (W\leq x)=1-\eta \exp(-\mu (1-\eta )x)~{\text{ for }}x\geq 0$

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

Период занятости можно вычислить, используя двойственность между моделью G/M/1 и очередью M/G/1, созданной преобразованием «рождественской елки».

Время ответа

Время отклика — это количество времени, которое задание проводит в системе с момента прибытия до момента его выхода из системы. Непротиворечивая среднего времени отклика может быть и асимптотически нормальная оценка вычислена как фиксированная точка эмпирического преобразования Лапласа.