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

Ни одно вспомогательное  событие, очевидно, не приводит к изменению  состояния системы. Таким образом, процесс функционирования системы, будучи процессом перехода из состояния в состояние, можно представить как упорядоченную во времени последовательность основных событий, происходящих в системе и переводящих ее из одного состояния в другое. Для поддержания этой хронологической последовательности основных событий в модели используется время.

 

 

 

 

 

3. Модельное время

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

При имитационном моделировании различают три  вида времени.

1. Время реальной системы  — это время, в котором "живет", функционирует моделируемая система.

2. Модельное время — это "искусственное" время, в котором "живет" модель или другими словами это время, которое является имитацией, прообразом (моделью) времени реальной системы.

3. Реальное время —  это время, в котором живет  исследователь, компьютер или  другими словами это время  необходимое для моделирования  (затратное время).

Для нас наибольший интерес представляет модельное  время. Для того чтобы вести отсчет модельного времени и обеспечить правильную хронологическую последовательность наступления основных событий в имитационной модели используется так называемый таймер модельного времени, которая представляет собой переменную для хранения (фиксации) текущего значения модельного времени.

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

1) коррекция с постоянным  шагом (принцип Dt);

2) коррекция с переменным  шагом (принцип dz).

В первом случае при каждой коррекции модельное  время увеличивается на одно и  то же значение Dt, выбираемое перед началом моделирования, а во втором случае значение приращения таймера каждый раз является случайной, а, значит, переменной величиной.

Проиллюстрируем оба принципа коррекции  таймера на примере. Пусть С₁, С₂, С₃, ... – основные события, происходящие в системе, а t₁, t₂, t₃,...- моменты появления этих событий. Отметим эти события и соответствующие моменты на оси времени реальной системы, причем полагаем, что события С₄ и С₅ происходят одновременно (рис.3.1, а)

Рис. 3.1. Моменты возникновения  и обработки событий.

В модели, где  время корректируется с постоянным шагом по принципу Dt (рис.3.1, б) модельное время t_M будет последовательно принимать значения t₁' = Dt, t₂' = 2Dt, t₃' = 3Dt и т.д. Эти моменты модельного времени никак не связаны с моментами t₁, t₂, t₃... появления событий в реальной системе. При этом подходе после очередного приращения таймера на величину Dt проверяется, не произошли ли на этом интервале в системе какие-нибудь события. Если есть такие события, то они обрабатываются, считая, что они якобы произошли в текущий момент модельного времени (правая граница интервала приращения), хотя реально события появились в другие моменты времени из интервала Dt. Очевидно, что при этом обработка событий может производиться группами. Выбор значения Dt оказывает существенное влияние на результаты моделирования с точки зрения адекватности отражения реальных событий в модели и затрат ресурсов компьютера на моделирование. Если Dt задать большим, то результаты моделирования могут быть недостоверными, т.к. все большее число событий группируется и обрабатывается в одной точке модельного времени. С другой стороны, уменьшение Dt для того, чтобы два неодновременных события не попали в один и тот же интервал Dt, а, следовательно, обрабатывались в разные моменты модельного времени, приводит к увеличению затрат на моделирование, т.к. значительная часть ресурсов будет тратиться на коррекцию таймера и на отслеживание событий, которых в большинстве интервалов Dt при этом могут и не быть. При любом уменьшении Dt всегда остается возможность попадания двух неодновременных событий в один и тот же временной интервал Dt.

В модели, где  время корректируется с переменным шагом или по принципу dz, значения, принимаемые модельным временем, совпадают, а значит, непосредственно связаны с моментами возникновения событий в реальной системе: t₁" = t₁, t₂" = t₂, t₃" = t₃. Достигается это тем, что при очередном приращении (после отработки события в текущий момент времени) модельное время сдвигается вперед до момента наступления следующего (ближайшего по времени) события. Отсюда, каждый раз модельное время получает переменное приращение, равное интервалу между двумя последовательными основными событиями. Очевидно, что при таком подходе, события отрабатываются в той последовательности, в те моменты времени, в которые они возникают в реальной системе. При этом одновременная обработка событий в модели имеет место только тогда, когда эти события появляются одновременно и в реальной системе (события С₅ и С₆ на рис.3.1).

При любом  способе коррекции таймера модельного времени, в начале моделирования, таймер, как правило, устанавливается на нулевое значение (t_M = 0). При этом разработчик сам решает вопрос о том, какое значение времени реальной системы принять за точку нулевого отсчета. Например, если необходимо моделировать процесс функционирования некоторой системы в течение суток, то началу отсчета модельного времени может соответствовать 8 часов утра, 12 часов дня и т.д. Кроме того, разработчик самостоятельно решает и вопрос о выборе единицы модельного времени и все значения времени, входящие в модель или получаемые при моделировании, должны быть выражены через выбранную единицу.

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

Однако, на практике, как правило, поступают гораздо  проще, а именно, в начале моделирования  задается время моделирования Т и по достижению модельным временем этого значения, т.е. когда t_M ³ Т, принимается решение о завершении моделирования и модель переходит к обработке полученных результатов. Иногда это условие дополняется другими условиями завершения моделирования. Например, дополнительным условием может быть условие дообслуживания тех заявок, которые оказались в СМО в момент времени t_M = Т.

Для реализации способа завершения моделирования  по выполнению условия t_M ³ Т с тем, чтобы при каждой коррекции таймера не проверять выполнение этого условия, в модель можно ввести основное псевдо-событие "окончание моделирования". Такое событие укладывается в концепцию основных событий как событий, которых можно планировать заранее, т.к. момент наступления события "окончание моделирования" задается заранее в начале моделирования.

На рис. 3.1. введенное псевдо-событие обозначено через С₀ с моментом наступления Т. Если после очередной коррекции модельного времени выяснится, что наступило событие "окончания моделирования", то принимается соответствующее решение.

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

 

 

 

4. Логическая схема имитационной  модели.

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

1. Заданы функции распределения A(t) и B(t) для интервалов поступления и длительностей обслуживания заявок, т.е. СМО полностью формализована.
2. В системе соблюдается условие существования стационарного режима, т.е. условие, что загрузка r = b/a < 0, где а и b – средние значения соответственно интервалов поступления и длительностей обслуживания.
3. В начале моделирования система свободна.
4. Задано время моделирования Т и в общем случае, когда моделирование завершается, система может быть не свободна.
5. Дисциплиной обслуживания является дисциплина FIFO.
6. В результате моделирования определяются следующие характеристики функционирования СМО:

а) загрузка системы r;

б) среднее  время ожидания w;

в) средняя  длина очереди l;

г) среднее  время пребывания u;

д) среднее число заявок в системе m;

е) максимальная длина очереди Nq_max.

4.1. Планирование основных  событий

Для рассматриваемой  системы G/G/1, как отмечалось ранее, основными событиями являются события "прибытие заявки" и "окончание обслуживания", которые "связаны" соответственно с интервалом поступления и длительностью обслуживания заявки. Ранее также отмечалось, что основные события можно планировать заранее. Что означает это утверждение?

Суть этого  утверждения состоит в том, что:

а) зная функцию распределения A(t) интервалов поступления, при имитационном моделировании в момент прихода очередной заявки можно определить момент поступления следующей заявки;

б) аналогично, зная функцию  распределения В(t) длительностей обслуживания, при имитационном моделировании в момент начала обслуживания заявки можно определить момент его окончания.

Планирование основных событий  производится в два этапа. Рассмотрим эти этапы вначале на примере планирования события "прибытие заявки". Пусть в некоторый момент модульного времени (например, t_M = 410) в модель поступила очередная заявка (рис.4.1. а).

а)      б)

 

Рис.4.1. Планирование прихода заявок.

Необходимо  планировать приход следующей заявки. Для этого сначала нужно разыграть (первый этап) случайную величину в соответствии с функцией распределения A(t) интервалов поступления, используя метод обратной функции. Предположим, что выпало значение t_а = 100. Полученное значение принимается за интервал прихода следующей заявки. Тогда (второй этап) момент прихода следующей заявки T_in равны сумме текущего значения модельного времени и разыгранного интервала прихода: T_in = t_M + t_а = 510 (рис.4.1, а).

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

Следует отметить, что планирование прихода следующей  заявки необходимо провести именно в момент прихода текущей заявки, не откладывая на "потом". Если отложить планирование прихода заявки на некоторое время t₀ (рис.4.1, б), а затем реализовать процедуру планирования, то фактическим интервалом прихода следующей заявки окажется величина, равная t₀ + t_a, а не t_а. Случайная величина t₀ + t_а не распределена по закону A(t) и, следовательно, такое отложенное планирование нарушает закон распределения A(t) интервалов поступления заявок.

Таким образом, механизм планирования прихода заявок можно сформулировать следующим  образом: каждый раз в момент прихода  очередной заявки планировать приход следующей заявки, используя соответствующую процедуру планирования. При этом приход первой заявки в модель планируется в начале моделирования.

Очевидно, что  в модели для системы G/G/1 в каждый момент времени будет присутствовать одно запланированное событие "прибытие заявки". Если моделируется СМО с неоднородной нагрузкой, когда в систему поступают заявки Н классов, то, очевидно, что число запланированных в модели событий в каждый момент времени равно количеству классов заявок и моменты прихода заявок можно обозначить через T1_in, T2_in,...,TH_in.

Рассмотрим теперь планирование основного события "окончание  обслуживания", которое полностью  аналогично планированию события "прибытие заявки". На первом этапе разыгрывается  случайное значение длительности обслуживания в соответствии с функцией распределения B(t). Пусть выпало значение t_в = 120, и это значение принимается за время обслуживания заявки. Если предположить, что заявка поступила на обслуживание, когда модельное время t_M  = 790, то в качестве момента T_out  окончания обслуживания этой заявки (второй этап) принимается сумма значений t_M  и t_в :

T_out = t_M + t_в = 910 (рис.4.2).

 

Рис.4.2. Планирование окончания обслуживания.

Таким образом, имитационная модель в момент начала обслуживания заявки точно знает момент его окончания, хотя для реальной системы, безусловно, это несправедливо.

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

Другим очевидным  фактом является то, что в модели системы G/G/1 событие "окончание обслуживания", в отличие от события "прибытие заявки", будет присутствовать не всегда, а только тогда, когда прибор занят обслуживанием.

Если моделируется многоканальная СМО с N обслуживающими приборами, то количество запланированных событий "окончание обслуживания" совпадает с количеством занятых обслуживанием приборов и моменты окончания обслуживания можно задать в общем случае переменными T1_out, T2_out,...,TN _out

4.2. Действия по обработке  основных событий

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