Моделирование одноканальной системы массового обслуживания.

Рассмотрим наиболее простой случай применения теории массового обслуживания в моделировании:

– поток заявок простейший и определяется интенсивностью их поступления l;

– поток обслуживания заявок тоже простейший, интенсивность обслуживания – m.

Поскольку потоки поступления заявок и их обслуживания простейшие, за достаточно малое время Dt в систему может поступить только одна заявка и покинуть систему тоже может только одна заявка.

За время Dt с вероятностью l×Dt поступит одна заявка и с вероятностью m×Dt очередная заявка будет обслужена. Очевидно с вероятностью 1 -l×Dt ни одна заявка в систему не поступит и с вероятностью 1 -m×Dt ни одна заявка не будет обслужена.

Обозначим через Р_n (t) вероятность того, что в момент времени t в системе будет ровно n заявок. Рассчитаем вероятность того, что в момент времени t+Dt в системе окажется ровно n заявок. Возможны четыре ситуации, приводящие к этому исходу:

– в момент времени t в системе было n -1 заявок, за время Dt поступила одна заявка и ни одна не была обслужена. Вероятность этого события равна: P_n-1(t)×l×Dt×(1-m×Dt);

– в момент времени t в системе n заявок, ни одна не поступила и ни одна не обслужена: P_n(t)×(1-l×Dt)×(1-m×Dt);

– в момент времени t в системе n заявок, одна поступила и одна обслужена: P_n(t)× l×Dt×m×Dt;

– в момент времени t в системе n=1 заявка, ни одна не поступила, одна обслужена: P_n+1(t)×(1-l×Dt)×m×Dt;

Вероятность того, что в момент времени t+Dt в системе останется ровно n заявок, равна сумме указанных выше вероятностей:

P_n(t+Dt)=P_n-1(t)×l×Dt(1-m×Dt)+ P_n(t)×(1-l×Dt)×(1-m×Dt)+

+ P_n(t)× l×Dt×m×Dt+ P_n+1(t)×(1-l×Dt)×m×Dt.

Раскроем скобки, исключим слагаемые, в которых содержится Dt в квадрате (величины второй степени малости), перенесём влево P_n(t) и разделим левую и правую части на Dt.

Устремив Dt к нулю, получим следующее дифференциальное уравнение:

Это уравнение описывает все возможные ситуации, кроме случаев, когда n= 0.

Возможны два независимых случая, когда в момент времени t+Dt в системе нет заявок:

– в момент времени t в системе нет заявок, за время Dt они не поступали. Вероятность этого события равна: P₀(t)×(1-l×Dt);

– в момент времени t в системе одна заявка, она обслужена, другие заявки не поступали: P₁(t)×(1-l×Dt)×m×Dt.

Следовательно, P₀(t+Dt)= P₀(t)×(1-l×Dt)+ P₁(t)×(1-l×Dt)×m×Dt.

Выполнив такие же аналогичные преобразования, получим второе уравнение:

В установившемся режиме вероятности P_n(t) не зависят от времени, поэтому их производные по времени равны нулю. В результате этого получим систему алгебраических уравнений:

-P₀×l+P₁×m=0, n=0,

P_n-1×l - P_n(l+m) + P_n+1×m, n>0.

 

Введём обозначение: r=l¤m. Из первого уравнения получим P₁=r×P₀.

Пусть n= 1, тогда второе уравнение примет вид:

Преобразовав его, получим P₂=P₀×r ². Приняв n= 2, получим P₃=P₀×r ³. Постепенно увеличивая n, получим P_n=P₀×r ⁿ.

Поскольку P_n= 1, получим P_n= P₀ r ⁿ= 1. Поскольку r<1, под знаком суммы находится геометрическая прогрессия, её сумма равна 1/(1-r). В результате этого получим: P₀=1-r, P_n=rⁿ(1- r).

Определим перечисленные выше характеристики системы:

– вероятность занятости канала (доля времени, в течение которого канал занят) – Р_ож=1-Р₀ =r;

– вероятность наличия очереди (n> 0) равна Р _n>0 = 1 – Р₀ – Р₁ = r ²;

– среднее число заявок, находящихся в системе:

n_ср= nP_n= (1-r) nrⁿ=(1-r)r nr^n-1=(1-r) r ( rⁿ)¢ =

=(1-r)r (1 / (1-r))¢ = r /(1-r).

Обратите внимание на то, что после выноса r за знак суммы, под знаком суммы оказалась производная от rⁿ;

– среднее число заявок, ожидающих обслуживания (длинна очереди), равно n_ож= n_ср - 1;

– среднее время нахождения заявки в системе (ожидающих в очереди и обслуживаемых) – T_ср=n_ср/m;

– среднее время ожидания обслуживания – Т_ож= Т_ср-1 / m.

Вопрос 11

Модели, построенные с применением Марковских процессов, способы задания систем. Марковская схема с поглощающим состоянием.

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

Поскольку длина очереди не ограничена, граф состояний системы будет иметь сколько угодно вершин. Максимальная интенсивность обслуживания заявок системой равна km, при числе заявок в системе, большем km, интенсивность обслуживания остаётся неизменной. Граф состояний k– канальной СМО:

Уравнение Колмогорова: , где P_i – вероятность нахождения системы в i-том состоянии, справа - S, имеющая столько слаг., сколько имеется переходов из данного сост., и в данное сост., слагаемое является произведением интенсивности перехода на вероятность состояния, из которого осуществляется переход.

Не трудно видеть, что это граф эргодического Марковского процесса. Описывается этот граф системой алгебраических уравнений.

n=0: 0 = – p₀l + p₁m

0 = – p_i(l + im) + p_i-1l + (i+1)p_i+1m, 0 < i < k

0 = – p_j(l + km) + p_j-1l + k p_j+1 m, ¥>j³ k

Система решается.

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

Матрица вероятностей перехода поглощающей Марковской цепи имеет следующий вид:

Граф, моделирующий надёжность дублированной системы с постоянно включенным резервом и обслуживанием. Поскольку отказы устройств и процессы восстановления устройств после отказа подчинены экспоненциальному закону, возле стрелок в место вероятностей указаны интенсивности переходов из одного состояния в другое (l – интенсивность отказа, m – интенсивность восстановления).

Эта Марковская схема отображает функционирование системы до её отказа. При этом в первом состоянии исправны и работают оба блока, во втором – отказал один из блоков, в третьем – отказали оба блока, т.е. отказала система (поглощающее состояние). Над стрелками указаны интенсивности переходов их одного состояния в другое.

Для описания работы этого графа используется система уравнений А.Н. Колмогорова. Система уравнений содержит столько уравнений, сколько вершин имеет граф (за исключением поглощающих). Слева записывается производная вероятности нахождения системы в данном состоянии, справа – многочлен, содержащий столько слагаемых, сколько стрелок входит в данное состояние или выходит из него. Если стрелка направлена из данного состояния, соответствующий член имеет знак «минус», в данное состояние – «плюс». Каждое из слагаемых равно произведению интенсивности перехода на вероятность нахождения системы в состоянии, из которого осуществляется переход. В рассматриваемом случае указанный на рис.2.5 граф описывается двумя уравнениями:

Умножим оба уравнения на dt и проинтегрируем их в пределах [0, ¥].

В результате решения этих уравнений получим:

Т_СР=Т₀+Т₁

Математическое ожидание времени от момента включения системы до её отказа будет равно: Т_СР=Т₀+Т₁

Вопрос 12