По закону обслуживания заявок

Экспоненциальное распределение (считается, что это самый тяжелый случай), при котором вероятность завершения обслуживания за время t равна:

 ,

где   –– интенсивность обслуживания заявок, которая связана со средним временем обслуживания заявок:  = 1/ , где  .

Смещенное экспоненциальное распределение –– всегда есть некоторая постоянная составляющая времени на прием заявки.

Регулярное обслуживание –– время обслуживания есть величина постоянная (нет случайного процесса).

 

По наличию взаимопомощи в обслуживании заявок

По наличию взаимопомощи в обслуживании заявок выделяют:

· без взаимопомощи –– заявка обслуживается с интенсивностью µ одним из n параллельно работающих устройств (многоканальное устройство).

· со взаимопомощью ––  предполагается, что процесс обслуживания заявки, поступающей на вход n -канального устройства, возможно распределить между n каналами, например, делением (декомпозицией) процесса на n равноценных по времени выполнения подпроцессов, тогда интенсивность обслуживания одной заявки возрастает до n µ.

 

ТЕМА 4. Построение аналитических моделей типовых схем СМО - на примерах одно- и многоканальных СМО без очереди (с отказами) и с ограниченной очередью

Замечание. При построении АМ есть очень важные аспекты, на которые надо особо обратить внимание на такие понятия как: 1) понятие состояния СМО, 2) граф состояний, 3) проставление на графе интенсивностей переходов СМО из одного состояния в другое (особенно для графов многоканальных СМО).

Что такое состояние системы? – это общее количество  заявок в системе - в устройстве (или в устройствах) на обслуживании и в очереди (или в очередях).

Что такое интенсивность?  – это количество  заявок за единицу времени – появляются или обслуживаются… В литературе по теории массового обслуживания принято интенсивность вх. потока обозначать λ, а интенсивность обслуживания обозначать µ (мю). Отношение λ/µ = ρ (ро-не путать с р, P).

 

Построение моделей расчёта характеристик одноканальных систем

Одноканальная Система с одноместной очередью

Рассмотрим систему М/М/1/1 –– это одноканальная система с одноместной очередью, поток заявок и обслуживание экспоненциальные.

Структурная схема системы показана на Рисунке 4.1.

 

Рисунок 4.1 –– Одноканальная СМО с одноместной очередью

 

Эта система имеет три состояния:

1. S₀ –– система свободна (устройство обслуживания не занято, очередь пуста).

2. S₁ –– устройство занято, очередь пуста.

3. S₂ –– система занята (устройство и место в очереди заняты).

Граф состояний системы показан на Рисунок 4.2.

 

Рисунок 4.2 –– Граф состояний одноканальной СМО с одноместной очередью

 

Система уравнений Колмогорова, построенная по графу состояний, имеет вид:

                                                     – λ P ₀ + µ P ₁=0;     (1)                             

                                               λ P ₀ – (λ+µ) P ₁ +µ P ₂=0; (2)                                

                                                       λ P ₁ – µ P ₂=0; (3)                             

                                                       P ₀ + P ₁+ P ₂ =1.     (4)                                

Особенностью системы уравнений Колмогорова является то, что одно уравнение всегда лишнее, но только не последнее – нормирующее. Одно из уравнений, например, уравнение (2), из данной системы уравнений удалим как избыточное: для определения 3 неизвестных (вероятности состояний) достаточно трёх уравнений, включая обязательное –– нормирующее уравнение.

 

                                          – λ P ₀ + µ P ₁=0;   (1)                                               – λ P ₁ – µ P ₂=0;            (2)                         

                                      P ₀ + P ₁+ P ₂ =1  (3)

 

Из (1) находим .

Из (2) находим .

Тогда уравнение (3) получаем в виде , из которого получаем

P ₀  = 1/(1+ ρ + ρ²) = (1– ρ)/(1– ρ³),

так как 1+ ρ + ρ² = (1– ρ³)/(1– ρ)   ––  как сумма членов геометрической прогрессии, первый член которой b ₁=1, знаменатель q = ρ.

4.1.2. Одноканальную СМО с ограниченной очередью длины m –– систему М/М/1/m.

Структурная схема этой системы аналогична схеме системы М/М/1/1, только длина очереди не 1, а m. Граф состояний системы показан на Рисунке 4.3.

Система имеет m + 2 состояния:

· S ₀ –– система свободна;

· S ₁ ––  устройство занято, очереди нет;

· S ₂ –– в очереди 1 заявка;

· S ₃ ––  в очереди 2 заявки;

· …

· S_m –– в очереди m – 1 заявка;

· S_{m +1} ––  в очереди m заявок (следующей заявке будет отказано).

  Рисунок 4.3 –– Граф состояний одноканальной СМО с ограниченной очередью длины m

 

Система уравнений КОЛМОГОРОВА:

–λ P ₀ + µ P ₁ = 0;        

λ P ₀ –(λ+µ) P ₁ +µ P ₂ = 0; 

λ P ₁ – (λ +µ) P ₂ + µ P ₃ = 0;

…

λ P_{m– 1} – (λ +µ) P_m + µ P_{m+ 1} = 0;

λ P_m – µ P_{m +1} = 0;

P ₀ + P ₁ + P ₂ + … + P_m + P_{m +1} = 1 или .

Используя результаты, полученные при расчете характеристик системы М/М/1/1, здесь будем иметь следующие результаты решения системы уравнений:

P ₁ = ρ P ₀;

P ₂ = ρ² P ₀;  

P ₃ = ρ³ P ₀;  

…

P_m = ρ ^m P ₀;

P_{m +1} = ρ ^{m +1} P ₀.   

P ₀ =1/(1+ ρ+ ρ²+ ρ³ +.... + ρ ^{m +1}) = (1 – ρ)/(1 – ρ ^{m +2}), так как в знаменателе снова имеем геометрическую прогрессию с первым членом, равным 1, и знаменателем ρ<>1.

Характеристики одноканальной СМО с ограниченной очередью:

1. Вероятность простоя системы P ₀ = (1 – ρ)/(1 – ρ ^{m +2}).

2. Вероятность потерь (отказов): , ρ<>1.

3. Относительная пропускная способность (доля обслуженных заявок) .

4. Абсолютная пропускная способность А = λ q ––  интенсивность потока обслуженных заявок.

5. Среднее число заявок в очереди .

Вероятности соответствующего числа заявок в очереди:

· нет заявок в очереди P ₀ + P ₁;     

· одна заявка в очереди P ₂;

· две заявки в очереди P ₃  и т.д.

  = 1ρ² P ₀  + 2 ρ³ P ₀ +...+ m ρ ^{m +1} P ₀ = ρ² P ₀(1 + 2ρ +...+ m ρ ^{m –1}) =

= ρ P ₀ = .

Ряд, представленный в полученном выражении суммой, можно свернуть, но получаемая при этом формула сложна. Вот что получается

При вычислениях (особенно на компьютере) удобнее воспользоваться выражением

= ρ P ₀ .

6. Среднее число заявок на обслуживании вычисляется по формуле:

 = 0* P ₀ + 1*(1 – P ₀),

так как в состоянии S₀ на обслуживании заявок нет заявок, а в остальных состояниях на обслуживании находится одна заявка (как при отсутствии очереди, так и наличии её!).

Для вероятности 1– P ₀ получаем

1 – P ₀  = ((1 – ρ ^{m +2}) – (1 – ρ))/(1 – ρ ^{m +2}) = (ρ – ρ ^{m +2})/(1 – ρ ^{m +2}).

Поэтому

 = (ρ – ρ ^{m +2})/(1 – ρ^m+2).

 

7. Среднее число заявок в системе (в очереди и на обслуживании):

.

8. Среднее время ожидания в очереди определяется из следующих соображений.

первая заявка в очереди ждет, пока будет обработана заявка, находящаяся на обслуживании в приборе, вторая заявка в очереди ждет, пока будут обработаны заявка, находящаяся в приборе, и первая заявка в очереди, т.е. пока будут обработаны две заявки, и т.д.

Вероятность нахождения заявки только в канале равна P ₁, вероятность того, что длина очереди равна 1, равна P ₂ и т.д.

Воспользовавшись формулой оценки математического ожидания случайной величины, получаем среднее время ожидания заявки в очереди

Умножив и разделив это выражение на ρ, получаем

 

 

9. Среднее время пребывания заявки в системе

.