Моделирование систем массового обслуживания

На любую систему массового обслуживания воздействует два потока событий: входной поток и выходной. В установившемся режиме среднее число входящих событий за единицу времени равно среднему числу выходящих событий и оба потока имеют одну и ту же интенсивность λ=1/ T.

Обозначим через x(T) количество внешних событий за время Т через y(T) количество обслуженных событий.

В момент времени t₁ и t₄ обслуживается одно событие. В момент времени t₂ обслуживается два события, а в t₃ заявок нет, и каналы прислуживания простаивают.

Z(t)= X(t)- Y(t) представляет собой количество событий, которое обслуживается СМО в момент времени Т.

Если t стремится к бесконечности, что среднее число входящих в СМО событий определяется по формуле:

где,  – среднее время пребывания события внутри системы, т. е. среднее время обслуживания системы.

                      

Т. е. для любой системы среднее время обслуживания системы равно среднему числу событий, деленному на интенсивность входного потока событий (λ).

Время ожидания

 – среднее число событий в очереди.

Классификация СМО

1. Одноканальные СМО с неограниченной очередью – такие системы можно представить с помощью графа:

λ            λ             λ             λ

           μ              μ           μ             μ

 

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

Каждая вновь поступившая заявка будет переводить систему в новое состояние S с увеличением индекса на 1, а каждая выполненная заявка будет уменьшать состояние S на 1.

Т. к система обслуживает только одну заявку, то

Длина очереди

Среднее время пребывания заявки в очереди

Среднее время пребывания заявки в очереди:

2. Одноканальные СМО с ограниченной очередью – в отличие от предыдущей системы, после поступления n-й заявки, всем остальным заявкам будет отказано в обслуживании и они покинут систему.

λ            λ             λ 

  μ              μ           μ                 

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

3. Многоканальные СМО с ограниченной очередью.

Обозначим характеристики:

p₀ – вероятность простоев каналов обслуживания;

p_отк – вероятность отказа каналов обслуживания;

p_обс – вероятность обслуживания;

n_z – среднее число каналов, занятых обслуживанием

k_z – доля каналов, занятых обслуживанием.

A – абсолютная пропускная способность, т. е. среднее количество заявок, обслуженных за единицу времени.

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

λ            λ             λ                         λ

           μ              2μ         3μ       mμ       (m+1)μ     nμ

 

Данная система имеет n-каналов с одинаковы техническими характеристиками и может находится в одном из состояний:

S₀ – заявки отсутствуют;

S₁ – поступила одна заявка и она обслуживается первым каналом, остальные каналы простаивают;

S₂ –во время выполнения первой заявки поступила вторая заявка, вторая заявка обслуживается вторая, остальные каналы простаивают.

S_n – во время выполнения n-1 заявок поступила заявка n, которая облаживается n-ым каналом. Все каналы заняты. Последующим заявкам будет отказано в обслуживании.

 

Заявки на обслуживание поступают произвольно с интенсивностью λ. При поступлении второй заявки ее обрабатывает второй канал, и интенсивность обслуживания удваивается, т. е. становится равной 2μ.

Финальная вероятность события S₀:

Относительная пропускная способность:

Абсолютная пропускная способность:

Среднее количество занятых кагалов:

4. Многоканальные СМО с неограниченной очередью.

              λ             λ          λ         λ       λ λ     λ λ

           μ              2μ        3μ mμ (m+1)μ    nμ    nμ   nμ    nμ nμ 

 

S₀ – заявки отсутствуют

…

S_n – все каналы заняты

S_n+1 – вновь поступившая заявка встает в очередь и ожидает обслуживания. Все последующие заявки также встают в очередь.

Для такой системы должно выполняться условие:

Число занятых каналов:
Среднее число заявок в очереди:

Среднее число обслуживаемых заявок  

Среднее время обслуживания:

Среднее время ожидания:

 

Пример 1. Дежурный администратор города имеет 5 телефонов. Звонки поступают с интенсивностью 90 звонков/час. Средняя продолжительность разговора составляет 2 мин.

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

Решение:

1. Классифицируем СМО:

· с отказами (нет накопителя);

· многоканальная (5 телефонов = 5 каналов).

2. Обозначения:

λ – интенсивность потока заявок (λ=90зв/60мин=3зв/2мин)

n – число каналов (n=5);

μ – интенсивность потока обслуживания, т.е. среднее число заявок, обслуживаемых в единицу времени (μ=1/ t_обс)

t_обс – среднее время обслуживания (t_обс=2мин)

ρ – интенсивность нагрузки;

k – номер заявки (число заявок), k=n=5;

Р₀ – вероятность простоя каналов обслуживания, когда нет заявок;

Р_отк – вероятность отказа в обслуживании, когда поступившая на обслуживание заявка найдет все каналы занятыми;

Р_обс – вероятность обслуживания.

n_з = ρ* Р_обс - среднее число занятых обслуживанием каналов.

к_з = n_з / n - для каналов, занятых обслуживанием.

А = λ Р_обс - абсолютная пропускная способность СМО.

3. Определяем характеристики данной СМО:

а) ρ = λ/μ = λ/(1/t_обс) = λ t_обс = 3/2 * 2 = 3 

б) = 1/ (ρ⁰/0!)+(ρ¹/1!)+(ρ²/2!)+(ρ³/3!)+(ρ⁴/4!)+(ρ⁵/5!) =   

=1/ (1+3/1)+(3*3/1*2)+(3*3*3/1*2*3)+(3*3*3*3/1*2*3*4)+(3*3*3*3*3/1*2*3*4*5)

=1/ 1+3+(9/2)+(27/6)+(81/24)+(243/120)=0,054

в) = (3⁵/ 1*2*3*4*5)*0,054=(3*3*3*3*3/1*2*3*4*5)*0,054=(243/120)*0,054=0,12

г) Р_обс = 1- Р_отк = 1-0,12=0,88

д) n_з = ρ*Р_обс = 3*0,88=2,6

е) к_з = n_з / n = 2,6/5=0,52

ж) А = λ Р_обс = (3/2)*0,88 = 1,31.

 

    Пример № 2. На автомобильной стоянке возле магазина имеется 2 места. Рядом находится площадка на 2 а/м. На стоянку прибывает 1 машина в 3 мин. Среднее время нахождения водителя в магазине 2 мин. Определить характеристики этой СМО.

Решение:

       1. Классифицируем СМО:

- с ограниченной длиной очереди

- с накопителем

- многоканальная

- с ограничением общего времени пребывания заявки в системе СМО с ожиданием и с ограниченной длиной очереди.

       2. Обозначения:

m=2 - длина накопителя

n=2 - число каналов

Остальные обозначения - как в Примере № 1.

       3. Определяем характеристики данной СМО:

а) λ = 1/3;        

б) t_обс = 2 мин;

в) ρ = λ/μ = λ/(1/t_обс) = λ t_обс = (1/3)*2=2/3.

г) Вероятность простоя каналов: =

=1/ ((ρ⁰/0!)+(ρ¹/1!)+(ρ²/2!)+(ρ²⁺¹/1*2(2-ρ))*[1-(ρ/2)²]=1/ ((2/3)/0!)+2/3+((2/3)²/(1*2))+

+((2/3)³/ 2(2-2/3)) [1- ((2/3)/2)]= 1/ 1+2/3+2/9+1/9[1-1/9]=0,52

 д) Вероятность отказа в обслуживании: = ((2/3)⁴/1*2*2²)*0,52 =(16/81)/8*0,52=0,013

е) Вероятность обслуживания:    Р_обс = 1- Р_отк = 0,987

ж) Абсолютная пропускная способность: А = λ Р_обс = 0,987*1/3=0,33

з) Среднее число занятых каналов: n_з = ρ*Р_обс = 2/3*0,987=0,658

Для каналов, занятых обслуживанием:

к_з = 0,658/2=0,329.

и) Среднее число заявок в очереди:   

=( (2/3)³/(2*2) ) * 1- ( (2/3)/2)² ) * ( 2+1-2*((2/3)/2) ) / ( 1-(2/3)/2)² ) *0.52

=(8/27)/4* * (1-1/9*7/3) /(4/9)= 2/27*((20/27)/(4/9))*0.52=2/27*5/3*0.52=0.14

к) Среднее время ожидания обслуживания: = 0.14/0.33=0.42

л) Среднее число заявок в системе: = 0,14+0,66=0,8

м) Среднее время пребывания в системе: t_смо= Z/ λ = 0,8/0,33=2,42 или

t_смо= t_or+ t_oбс = 0,42+2=2,42 мин

ЛИТЕРАТУРА

1. Агальцов В.П. Математические методы в программировании. – М.: Издательский дом «ФОРУМ», 2010

2. Балдин К.В., Брызгалов Н.А., Рукосуев А.В. Математическое программирование. – М.: ИТК «Дашков и К», 2008

3. Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика. Математическое программирование.– Изд. Лань, 2010

4. Кузнецов А.В., Сакович В.А., Холод Н.И. Сборник задач и упражнений по высшей математике. Математическое программирование.– Изд. Лань, 2010

5. Юденков А.В., Дли М.И., Круглов В.В. Математическое программирование в экономике. – М.: «Финансы и статистика», 2010

Интернет ресурсы:

1. www.exponenta.ru – Образовательный математический сайт