Механизмы продвижения времени

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

Существует два основных подхода к продвижению модельного времени: продвижение времени от события к событию и продвижение времени с постоянным шагом.

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

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

Рис. 4.2. Механизм продвижения времени от события к событию СМО с одним ОУ

Здесь использованы следующие обозначения:

t ₁ ‑ время поступления требования i (t ₀ = 0);

А_i = t_i – t_{i- 1} ‑ время между поступлениями требований i и i ‑ 1;

S_i, ‑ время, потраченное устройством на обслуживание требования i
(без учета времени задержки требования в очереди);

D_i ‑ время задержки требования i в очереди;

с_i = t_i + D_i, + S_i, ‑ время ухода требования i по завершении обслуживания;

е_i ‑ время возникновения события i любого типа (значение i, принимаемое часами модельного времени без учета значения е ₀ = 0).

Каждый из определенных параметров, как правило, будет случайной величиной. Предположим, что нам известны распределения вероятностей для времени между поступлением требований A ₁ A₂,... и для времени обслуживания S ₁ S ₂,... и что они имеют функции распределения, обозначенные как F_A и F_S соответственно. (F_A и F_S вычисляются путем сбора данных в интересующей нас системе и последующего определения распределений по этим данным).

Алгоритм имитационного моделирования СМО М / М /1 можно описать следующим образом:

1. В момент времени е₀ = 0 устройство находится в состоянии незанятости. Время поступления первого требования определяется путем генерации значения А ₁ из F_A и прибавления его к 0. После этого часы модельного времени переводятся на время возникновения следующего (первого) события e ₁= t ₁. (на рис. 4.2 изогнутые стрелки представляют продвижение часов модельного времени). Поскольку на момент поступления требования t ₁устройство находится в состоянии незанятости, оно немедленно начинает обслуживание с задержкой требования в очереди D ₁=0, и его состояние меняется на занятое.

2. Время c ₁ завершения обслуживания поступившего требования определяется путем генерации значения S ₁ из F_S и прибавления его к t ₁.

3. И наконец, время поступления второго требования t ₂ вычисляется по формуле t ₂ = t ₁ + А ₂, где значение А ₂ генерируется из F_A.

4. Если t ₂ < c ₁, как показано на рис. 4.2, часы модельного времени переводятся с e ₁ на время следующего события е ₂ = t ₂. (Если бы c ₁ было меньше t ₂, часы были бы переведены с e ₁ на c ₁.).Так как требование, поступившее в момент времени t₂, обнаруживает, что устройство обслуживания уже занято, число требований в очереди увеличивается с 0 до 1, а время поступления требования записывается в список событий. Однако в этот раз время обслуживания требования S ₂ не генерируется. Время поступления третьего требования вычисляется по формуле t ₃ = t ₂ + А ₃.

5. Если c ₁< t ₃, как показано на рис. 4.2, часы модельного времени переводятся с е ₂ на время возникновения следующего события е ₃ = c ₁.

6. Когда требование, обслуживание которого завершено, уходит, начинается обслуживание требования в очереди (того, которое поступило в момент времени t ₂): вычисляется время его задержки в очереди D ₂ = c ₁ ‑ t ₂ и с ₂ = с ₁ + S ₂ (теперь S ₂ генерируется из F_S), а число требований в очереди меняется с 1 на 0.

7. Если t ₃< c ₂, часы модельного времени переводятся с е ₃ на время возникновения следующего события е ₄ = t ₃, и т, д.

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

Отметим также, что различают два типа событий, связанных с появлением входных требований: первый тип – это события, приводящие к смене состояния СМО (т.е. УО), с «свободно» на «занято» или обратно, второй – это события, не приводящие к смене состояния УО. На рис. 4.2 типы событий чередуются: к типу 1 относятся нечетные события, к типу 2 – чётные.