Аналитическое моделирование

1.

АНАЛИТИЧЕСКОЕ МОДЕЛИРОВАНИЕ
Многоканальные СМО с однородным потоком заявок
• СМО содержит N обслуживающих приборов П1,…,ПN;
• заявки поступают в СМО с интенсивностью λ ;
• все приборы идентичны, то есть любая заявка может быть обслужена любым прибором за одно и то же
случайное время;
• обслуживающие приборы не простаивают, если в системе (накопителе) имеется хотя бы одна заявка, причем
после завершения обслуживания очередной заявки мгновенно из накопителя выбирается следующая заявка;
• в системе существует стационарный режим, предполагающий отсутствие перегрузок.

2.

Многоканальная экспоненциальная СМО без накопителя (M/M/N/0)
• Поступающие в систему заявки образуют простейший поток с интенсивностью λ .
• Длительность обслуживания заявок в любом приборе распределена по экспоненциальному закону с
интенсивностью μ = 1/ b , где b – средняя длительность обслуживания.
• Перед приборами не предусмотрены места для ожидания заявок, то есть в системе отсутствует накопитель.
• Дисциплина буферизации – с отказами: заявка, поступившая в систему и заставшая все приборы занятыми
обслуживанием других заявок, теряется.
• Дисциплина обслуживания – в естественном порядке: заявка, поступившая в систему принимается на
обслуживание, если есть хотя бы один свободный прибор. Если заявка застала свободными несколько
приборов, то она направляется в один из них случайным образом.
Замечание: в СМО с отказами всегда будет существовать установившийся режим, поскольку даже при больших
значениях нагрузки ( y >> 1) число заявок в системе не может вырасти до бесконечности (с ростом нагрузки
увеличивается доля заявок, получающих отказ в обслуживании).

3.

В качестве параметра, описывающего состояние случайного процесса, будем рассматривать
количество заявок k, находящихся в СМО. При этом система в любой момент времени может
находиться в одном из (N +1) состояний:
S0 : k = 0 – в системе нет ни одной заявки;
S1: k = 1 – в системе находится 1 заявка (один прибор работает, остальные – простаивают);
S2: k = 2 – в системе находятся 2 заявки (два прибора работают, остальные – простаивают);
…
SN: k =N в системе находятся N заявок (все приборы работают).
В один и тот же момент времени в системе может произойти только одно из двух событий, которые
приводят к изменению состояния случайного процесса.
1. Поступление заявки в систему с интенсивностью λ . При этом:
• если случайный процесс находится в состоянии Sk, причем k < N , то произойдет переход в
состояние Sk+1, причем интенсивность перехода равна интенсивности поступления λ ;
• если случайный процесс находится в состоянии SN, то состояние случайного процесса не
изменится, что будет соответствовать отказу в обслуживании поступившей заявки.
2. Завершение обслуживания заявки в одном из приборов с интенсивностью μ . Это событие может
наступить только в том случае, если в системе на обслуживании находится хотя бы одна заявка. Если
в СМО на обслуживании находится k =1,2,..., N заявок (случайный процесс находится в состоянии Sk),
то интенсивность перехода в состояние Sk-1 будет равна kμ .

4.

Система уравнений для определения стационарных вероятностей:
Финальные вероятности (формулы Эрланга):
Замечание. Формулы Эрланга остаются справедливыми и тогда, когда поток заявок — простейший, а время
обслуживания имеет произвольное распределение с математическим ожиданием 1 /μ.

5.

Характеристики СМО M/M/N/0
• нагрузка y =λ /μ = λb ;
• загрузка
учитывающая долю k/N работающих приборов;
• коэффициент простоя системы
• вероятность потери заявок, вероятность отказа в обслуживании πп =
вероятность обслуживания заявки (относительная пропускная способность СМО): π0 =1- πп
• производительность системы λ' =λ(1- πп );
• интенсивность потока потерянных заявок λ'' =λπп ;
• среднее число заявок в системе (среднее число работающих приборов):
или m= λ' /μ=yπ0 ;
(среднее число простаивающих приборов: Nˆ = N –m);
• среднее время пребывания заявки в системе: u=b

6.

Многоканальная экспоненциальная СМО с накопителем ограниченной емкости (M/M/n/r)
• Поступающие в систему заявки образуют простейший поток с интенсивностью λ .
• Длительность обслуживания заявок в любом приборе распределена по экспоненциальному закону
с интенсивностью μ = 1/ b , где b – средняя длительность обслуживания.
• Все n приборов – идентичны, и любая заявка может быть обслужена любым прибором;
• В системе имеется накопитель ёмкости r.
• Дисциплина буферизации – с потерями: заявка, поступившая в систему и заставшая накопитель
заполненным, теряется.
• Дисциплина обслуживания – в порядке поступления по правилу «первым пришел – первым
обслужен» (FIFO).
Замечание: в СМО с накопителем ограниченной ёмкости всегда существует установившийся режим,
поскольку длина очереди не будет расти до бесконечности даже при больших значениях нагрузки.

7.

S0 : в системе нет ни одной заявки;
S1: в системе находится 1 заявка (занят 1 канал);
S2: в системе находятся 2 заявки (заняты 2 канала);
…
Sj: в системе находятся j≤ n заявок (заняты j каналов);
……
Sn+r: в системе находятся n+r заявок (заняты n каналов и r заявок – в накопителе).
Финальные вероятности существуют для всех λ и μ:
При χ=y/n≠1
При χ=y/n=1

8.

Характеристики СМО M/M/n/r
• нагрузка: y=λ /μ= λb;
• вероятность потери заявок: πп = pr+n ;
• загрузка: ρ= y(1- πп )/n;
• коэффициент простоя системы: η =1-ρ ;
• производительность системы λ' =λ(1- πп );
• интенсивность потока потерянных заявок λ'' =λπп ;
• среднее число занятых каналов:
• среднее число заявок в очереди:
• среднее число заявок в системе: m=l+k;
• среднее время ожидания заявок в очереди w = l /λ' ;
• среднее время пребывания заявок в системе u = m/λ' = w + b

9.

Многоканальная простейшая СМО с неограниченной очередью (M/M/n/∞)
• Поступающие в систему заявки образуют простейший поток с интенсивностью λ .
• Длительность обслуживания заявок в любом приборе распределена по экспоненциальному закону с
интенсивностью μ = 1/ b , где b – средняя длительность обслуживания.
• Все n приборов – идентичны, и любая заявка может быть обслужена любым прибором;
• В системе имеется накопитель неограниченной ёмкости: r = ∞, то есть любая заявка, поступившая в систему,
найдет место для ожидания в очереди и не будет потеряна.
• Дисциплина буферизации отсутствует, поскольку накопитель имеет неограниченную ёмкость.
• Дисциплина обслуживания – в порядке поступления по правилу «первым пришел – первым обслужен» (FIFO).
• В системе отсутствуют перегрузки, то есть загрузка системы ρ = λb/n<1.

10.

S0 : в системе нет ни одной заявки;
S1: в системе находится 1 заявка (занят 1 канал);
S2: в системе находятся 2 заявки (заняты 2 канала);
…
Sj: в системе находятся j≤ n заявок (заняты j каналов);
……
Sn+r: в системе находятся n+r заявок (заняты n каналов и r заявок – в накопителе).
……
Финальные вероятности существуют только при ρ =y/n < 1:

11.

Характеристики СМО M/M/n/∞
• нагрузка y =λ /μ = λb ;
• загрузка ρ = y/n = λb/n;
• коэффициент простоя системы η = 1- ρ;
• вероятность потери заявок πп = 0 ;
• производительность системы при отсутствии потерь совпадает с интенсивностью поступления заявок в систему:
λ' =λ ;
• интенсивность потерянных заявок λ'' = 0 ;
• среднее время ожидания заявок в очереди:
приборов заняты обслуживанием заявок
• среднее время пребывания заявок в системе: u = w + b ;
• среднее число заявок в очереди: l = λ'w или
• среднее число заявок в системе: m = λ' u .
, где
– вероятность того, что все n

12.

Выводы (M/M/n)
1. Зависимость среднего времени ожидания w и среднего
времени пребывания u заявок в системе от числа
обслуживающих приборов K: с увеличением числа
обслуживающих приборов времена ожидания и
пребывания заявок уменьшаются, при этом в пределе
при K → ∞ время ожидания стремится к нулю, а время
пребывания достигает своего наименьшего значения,
равного длительности обслуживания заявок.
2. Среднее время ожидания заявок, как и для одноканальных систем, существенно зависит от
нагрузки y (загрузки ρ ) системы. При y ≥ K (ρ →1) время ожидания заявок возрастает
неограниченно: w → ∞, то есть заявки могут ожидать обслуживания сколь угодно долго.
Пример. Рассматривается простейшая СМО с практически неограниченным числом каналов
(n→∞). На вход СМО поступает поток заявок с интенсивностью λ; интенсивность потока
обслуживаний (для одного канала) равна μ. Найти финальные вероятности состояний СМО и
среднее число занятых каналов k.

13.

3. Зависимость среднего времени ожидания w и среднего времени
пребывания u заявок в системе от числа обслуживающих
приборов K при условии, что при увеличении числа
обслуживающих приборов K их суммарная
производительность (скорость работы) остается
постоянной, т.е. VΣ = KVK = const , где VK –производительность
одного прибора при наличии в системе K обслуживающих
приборов. Среднее время ожидания w заявок, как и в
предыдущем случае, уменьшается с увеличением числа
приборов, однако время пребывания u заявок в системе
увеличивается. Последнее объясняется тем, что с увеличением
числа приборов K производительность каждого из них для
сохранения суммарной производительности системы
уменьшается пропорционально K и, следовательно, линейно увеличивается длительность обслуживания заявки
в приборе. При этом скорость увеличения длительности обслуживания больше скорости уменьшения времени
ожидания, что в сумме приводит к увеличению времени пребывания заявок в системе. В пределе при K → ∞
время пребывания заявок асимптотически стремится к длительности обслуживания заявок.
4. Таким образом, при проектировании систем обслуживания следует иметь в виду, что с точки зрения задержек
(времени пребывания заявок) более эффективной является одноканальная система, чем многоканальная, при
равенстве суммарной производительности. Основным достоинством многоканальной системы является более
высокая надёжность, проявляющаяся в том, что при выходе из строя одного или даже нескольких
обслуживающих приборов система продолжает функционировать, хотя и с меньшей эффективностью, что
заключается в увеличении времени пребывания заявок в системе.

14.

Задачи.
1. Одноканальная СМО с неограниченной очередью — ЭВМ, на которую поступают заявки (требования на
расчеты). Поток заявок — простейший со средним интервалом между заявками t = 10 мин. Время
обслуживания распределено по закону Эрланга 3-го порядка с математическим ожиданием b = 8 мин.
Определить среднее число m заявок в СМО и среднее число l заявок в очереди, а также средние времена
пребывания заявки в системе u и в очереди w.
(формула Поллачека- Хинчина
) Ответ: vb= 0,57735, w= 21.33, l=2.133, u=29.33, m=2.933
2. Условия предыдущей задачи изменены: поток заявок уже не простейший, а пальмовский, причем интервал
между событиями в потоке распределен по обобщенному закону Эрланга 2-го порядка с параметрами λ1 = 1/2;
λ2 = 1/8. Найти приближенно характеристики эффективности СМО.
(формула Поллачека- Хинчина +
Ответ: va=0,82, vb= 0,57735, w=16,14 ……
).

15.

3. Одноканальная СМО с отказами— ЭВМ, на которую поступают заявки (требования на расчеты). Поток
заявок — простейший со средним интервалом между заявками t = 10 мин. Время обслуживания
распределено по закону Эрланга 3-го порядка с математическим ожиданием b = 8 мин. Определить среднее
число m заявок в СМО и среднее число l заявок в очереди, а также средние времена пребывания заявки в
системе u и в очереди w. (Сравнить с задачей 1).
4. Имеется одноканальная СМО с отказами. Поток заявок - простейший с интенсивностью λ. Время
обслуживания — не случайное и в точности равно b=1/μ. Найти относительную и абсолютную пропускную
способность СМО в предельном стационарном режиме. (Сравнить с задачей 1).
5. Рассматривается одноканальная СМО с отказами; на ее вход поступает простейший поток заявок с
интенсивностью λ. Время обслуживания — показательное с параметром μ. Работающий канал может время
от времени выходить из строя (отказывать); поток отказов канала — простейший с интенсивностью v.
Восстановление (ремонт) вышедшего из строя канала начинается мгновенно после его отказа; время
ремонта — показательное с параметром γ. Заявка, которая обслуживалась в момент выхода канала из строя,
покидает СМО необслуженной. Найти относительную и абсолютную пропускную способность СМО.