Системы массового обслуживания с немарковским распределением времени обслуживания

Для входных потоков марковость будет сохранена. В качестве типичной СМО рассмотрим M/G/1.

Обозначим функцию распределения промежутков времени между последовательными поступлениями заявок на входе системы A (t).

По определению марковского процесса

.

Значение λ определяет интенсивность потока заявок, среднее значения промежутка времени между требованиями 1/ λ, а дисперсия промежутка равна:

.

Обозначим функцию распределения времени обслуживания B(x), а плотность распределения b(x).

Рассмотрим теперь описание СМО с точки зрения ее состояния в момент t. Обозначим N(t) число требований, присутствующих в системе в этот момент. Кроме того, необходимо знать время обслуживания, которое к данному моменту получило требование уже находящееся в сервере. Обозначим его X₀(t). Таким образом, от однокомпонентного описания состояния СМО с марковским процессом обслуживания для произвольного закона обслуживания необходимо перейти к двухкомпонентному описанию. Кроме дискретной составляющей N(t), теперь нужно рассматривать пару

Где вторая компонента есть непрерывная функция. Для упрощения решения задачи будем рассматривать только специально выбранные моменты времени, для которых величина времени уже проведенного заявкой в сервере является величиной известной или еще лучше постоянной. Используемый здесь подход состоит в том, чтобы рассматривать исключительно моменты ухода заявок из системы и описывать состояние числом требований, остающихся в эти моменты в системе. На множестве точек на оси времени, определяемых этими моментами, построим вложенную марковскую цепь, как число требований, остающихся после ухода. Можно убедиться, что при этом получается полное описание состояний. Введем обозначения:

C_n – n -ое требование, поступающее в систему; τ _n - время поступления n -го требования, а t_n=τ _n-τ _n-1 = x_n – время обслуживания n -го требования.

Обозначим q_n – число требований, остающихся в системе в момент ухода требования C_n, а число требований, поступающих в систему за время обслуживания этого требования – v_n.

Найдем распределение вероятностей q_n, которое фактически зависит от времени. Предельное распределение, которое мы ранее называли p_k, есть не что иное как предел этого распределения при n → ∞.

Марковская цепь описывается вероятностями перехода. Определим вероятности перехода за один шаг .

Матрица переходов будет иметь вид:

Например, j -элемент первой строки матрицы представляет собой вероятность того, что предыдущее требование, уходя, оставило систему пустой, а за время обслуживания требования C_n+1 поступает ровно j новых требований и все они остаются в системе после ухода требования C_n+1. Точно так же в других строках элемент p_ij при j > i-1 представляет собой вероятность поступления точно j-i+1 требований за время обслуживания n+1 требования при условии, что n -ое требование, уходя, оставляет в системе точно i требований. Диаграмма вероятностей переходов приведена на рис 1.

Рис. 1 Диаграмма вероятностей переходов для вложенной марковской цепи типа M/G/1.

Вычислим теперь значения α _k. Исходя из того, что входной поток пуассоновский и не зависит от состояния СМО, а также время обслуживания каждого требования также не зависит от состояния, отбросим индексы у обозначений соответствующих величин. По формуле полной вероятности будем иметь

Эта формула полностью представляет матрицу перехода.

Все значения α положительны, что означает достижимость и неприводимость рассматриваемой марковской цепи. Введем обычное определение .

2. Формула Полячека –Хинчина

Если ρ < 1, марковская цепь будет эргодична. В этом предположении можно получить матричное уравнение для определения стационарных вероятностей p_k, т.е. вероятностей того, что уходящее требование оставляет в СМО ровно k требований: , где вектор .

Одной из наиболее важных характеристик СМО является значение средней длины очереди.

Для системы M/G/1 она дается формулой Полячека-Хинчина. Определим в пределе длину очереди как .

Анализируя два случая ухода требования С_n когда система остается непустой (Рис. 2) и случай ухода требования, когда система остается пустой (Рис.3),

Получаем два соотношения, связывающие случайные величины, определяющие число требований:

Для непустой .

Для пустой .

Рис. 2 Случай q_n > 0.

Рис. 3 Случай q_n =0.