Моделирующие алгоритмы для СМО

Рассмотрим четыре примера построения моделирующего алгоритма для СМО. Первый из них является основным, отражающим идею построения моделирующего алгоритма, Другие три примера можно рассматривать как модификацию основного, показывающую, как приспособить основную схему для конкретной СМО. Еще ряд модификаций можно найти в [1,2] .

Пример 1. Пусть имеется СМО с одним обслуживающим каналом. Заданы описание входного потока заявок и характеристика обслуживающего канала (например, время обслуживания - случайная величина с плотностью распределения f(x:)). Предполагается, что если поступившая заявка застает канал занятым, то она получает отказ. Задача заключается в том, чтобы оттенить долю заявок, получивших отказ, моделируя работу системы на интервале времени [0,.Тмод].

Математическая модель СМО. Дадим список величин, описывающих состояние системы в произвольный момент времени. Для каждой величины укажем закон ее изменения во времени.

1. t_пост- момент поступления очередной заявки в систему Эта вели-чина вычисляется по математическому описанию входного потока заявок. Математические зависимости моделирования входных потоков были рассмотрены в лабораторных работах. Например, если входной поток пуассоновский с параметров А , то моменты времени поступления заявок в систему рассчитываются по формуле

                 ( t⁰_пост = 0 , i= 1,2,.. ).

2. t - время обслуживания заявки. Это случайная величина, значения которой формируются стандартным способом по заданному закону распределения f(x) (например, методом обратной функции). Методы и алгоритмы формирования случайных величин рассматривались в лабораторных работах.

3. tс_в – момент освобождения канала. Если заявка, пришедшая в момент времени t_пост , принимается на обслуживание, то

                               t_св = tпост + t .

4. N – счетчик поступивших заявок; увеличивается на единицу при поступлении очередной заявки.

5. N_отк – счетчик числа отказов. Он увеличивается на единицу, если поступившая заявка не обслуживается.

Схема моделирующего алгоритма для рассматриваемого примера показана на рис. 8.

Рис. 8. Схема алгоритма моделирования СМО с одним обслуживающим каналом

Пример 2. Рассмотрим систему, описанную в примере 1, но предположим, что заявки могут ожидать обслуживания неограниченное время. Целью моделирования является оценка среднего времени ожидания обслуживания. Для описания текущего состояния системы используем те же самые величины, за исключением N_отк . Кроме того, добавляются новые величины:

t_н – момент начала обслуживания заявки;

Т_ож – суммарное время ожидания обслуживания по всем заявкам.

Схема моделирующего алгоритма для этого случая показана на рис. 9.

Рис. 9. Схема алгоритма моделирования СМО  с неограниченным временем ожидания

Пример 3. В условиях предыдущего примера дополнительно предположим, что заявки поступают двумя потоками: заявки 1-го типа и заявки 2-го типа. Вероятностные характеристики каждого потока заданы и на их основе разработаны способы имитации каждого потока. Пусть в результате моделирования требуется оценить среднее время ожидания для заявок каждого типа.

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

                                            t⁽¹⁾_пост, N⁽¹⁾, Т⁽¹⁾_ож, t⁽¹⁾ ;

                                            t⁽²⁾_пост, N⁽²⁾, Т⁽²⁾_ож, t⁽²⁾ .

Схема моделирующего алгоритма для системы с двумя потоками заявок показана на рис 10.

Рис.10. Схема алгоритма моделирования СМО с различными типами заявок

Пример 4. Пусть теперь при сделанных предположениях в системе имеется три потока заявок. Заявки первого типа имеют приоритет при обслуживании. Это означает, что если к моменту освобождения канала поступило несколько заявок, то на обслуживание будет поставлена заявка первого типа, поступившая ранее других заявок этого типа. Если же заявок первого типа нет, то обслуживается заявка, пришедшая ранее других. Цель моделирования - оценка среднего времени ожидания обслуживания для каждого типа заявок. Схема моделирующего алгоритма представлена на рис.11.

1. Начало

2. N^(k)=0; T^(k)_ож = 0; (k=1,2,3); t_св = 0;

3. Формирование t⁽¹⁾_пост , t⁽²⁾_пост , t⁽³⁾_пост

4. t_пост = min{ t⁽¹⁾_пост , t⁽²⁾_пост , t⁽³⁾_пост} = t^(k)_пост

5. ЕСЛИ t_пост > T_мод , то T^(k)_ож.ср = T^(k)_ож /N^(k) (k=1,2,3); КОНЕЦ

6. ЕСЛИ t_пост > t_св , то t_н = t_пост ; идти к 9

7. ЕСЛИ t⁽¹⁾_пост < t_св , то k = 1;

8. t_н = t_св ; T^(k)_ож = t_н + T^(k)_ож - t^(k)_пост;

9.  N^(k) = N^(k) + 1;

10.  Формирование t^(k) ;

11. t_св = t_н + t^(k) ;

12.  Формирование t^(k)_пост; ИДТИ К 4

Рис. 11. Схема алгоритма моделирования СМО с приоритетным обслуживанием