Финаев В.И. Аналитические и имитационные модели

Подождите немного. Документ загружается.

161

разделим обе части уравнения (7.9) на

N, вычтем из обеих

частей

Р(ω,t), разделим на Δt и, перейдя к предельным

выражениям, получим

−

ω∂

∂

ω∂

)t,(P

)w(B)t,0(Pdx)xw(B

)t,x(P

λ−−

∂

λ−

∫

Решение данного интегродифференциального уравнения

должно удовлетворять условиям:

Р(ω,0)=1 для всех ω;

Р(∞,t)=1 для всех t. Интегрируем по частям:

∫

−ωλ+ωλ−

ω∂

∂

)v(dB)t,u(P)t,(P

)t,(P

Если

B(t)=1-B

(t), то

∫

−ωλ+ωλ−

ω∂

∂

ω∂

).t,x(Pd)x(P)t,(P

)t,(P

(7.10)

Уравнение (7.10) носит название уравнения Линди-

Такача-Севастьянова, и оно является моделью для

описания времени ожидания в СМО. Для стационарного

режима уравнение (7.10) примет вид

∫

−λ−ωλ=

ω∂

)x(dP)xw(P)(P

)(P

. (7.11)

Математическая модель может быть представлена в виде

характеристической функции, если применить к

уравнениям (7.9) и (7.11) преобразование Лапласа-

Стилтьеса, которое имеет вид

∫

−

ω=ω

)t(de)s(

Характеристическая функция распределения

Р(ω,t) из

решения уравнения (5.9) определится

)])s(1(s1[1

)t,0(P

)t,s(

β−λ−

=ω

162

где

β(s) - характеристическая функция распределения B(t).

Характеристическая функция распределения

Р(ω) из

решения уравнения (7.11) определится как

)s(1

)s(

β−

λ−

ρ−

=ω

7.6. Имитационное моделирование

одноканальной СМО

Алгоритмизация может осуществляться с применением

способа

Δt-моделирования, который позволяет определить

состояния СМО через интервал времени

Δt.

7.6.1. Алгоритм имитационной модели

одноканальной СМО.

Одноканальная СМО самая простая

модель (см. рис. 7.1,а) при условии пуассоновского

входного потока заявок и экспоненциального

распределения времени обслуживания. Если поток заявок

пуассоновский, то СМО определена шифром

M/G/1/PM.

Одноканальную СМО следует рассматривать как

элемент, т.е. предел членения СМО сложной структуры.

Рассмотрим задачу построения имитационной модели

одноканальной СМО с пуассоновским потоком заявок,

характеризующимся интенсивностью

α и функцией

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

B(t).

Для понимания процесса функционирования

одноканальной СМО следует построить временные

диаграммы, на которых отображают время задержки

ω(t)

заявок, а также определяют интервалы периода занятости

π(t). На рис. 7.2 приведены временные диаграммы,

отображающие процесс функционирования СМО.

163

Поток заявок

П(t) описывается стохастическим

распределением вероятностей длин интервалов между

соседними заявками (показаны точками). Время задержки в

момент поступления заявки скачком увеличивается на

величину, равную времени обслуживания поступившей

заявки, а затем убывает с угловым коэффициентом, равным

единице. Интервалы периода занятости

π(t) на нижней оси

показаны выделенными отрезками (толстые линии).

М=0

М=0М=1М=0М=0М=0

П(t)

ω(t)

М=1 М=1 М=1

М=1 М=0

Рис. 7.2

При пуассоновском потоке заявок длины интервалов

времени между соседними заявками описываются

экспоненциальным распределением

A(t)=1-e

-αt

На рис. 7.2 имеются идентификаторы:

I=1, если за такт моделирования Т=Δt поступила заявка

с вероятностью

, I=0, если заявка в систему не

поступила;

М=1, если в СМО есть очередь на обслуживание, М=0,

если очередь отсутствует;

L=1, если прибор занят обслуживанием (в СМО одна и

более заявок ),

L=0, если прибор от обслуживания свободен

(в СМО нет заявок);

164

К=1, если обслуживание окончено и заявка покидает

СМО;

JPM - максимально возможная длина очереди.

На рис. 7.3 приведена структурная схемя алгоритма

имитационной модели СМО

M/G/I/JPM, полученная

исходя из модульного принципа построения программ.

165

16,17

JP<JPM

Начало

WWOD

T=T+1

GEN

OSTH

STATT

STATP

I=1

L=0

L=1

M=1

WIB

STATO

OBS

L=1

B>0

STATB

PZ=0

M=1

STATPZ

K=1

0 21

STATW

T<TZ

WIW

Конец

Рис.7.3

Алгоритм имитационной модели построен в

соответствии с процедурами поступления заявок в систему,

постановки их в очередь при занятом приборе,

166

обслуживания заявок. Структура алгоритма имитационной

модели состоит из подпрограмм, имитирующих

конкретные операции в СМО. «Движение» по

подпрограммам осуществляется с помощью ключей.

Работает алгоритм имитационной модели следующим

образом.

Вначале происходит обращение к подпрограмме

WWOD – ввод исходных данных, в которой описываются

необходимые массивы, общие области, задаются начальные

значения. В начальный такт моделирования необходимо

определить:

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

Т=0;

- идентификаторы

М=0, L=0, так как нет очереди и

прибор свободен от обслуживания;

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

ВТ=0, так как в

СМО нет заявок;

- число заявок в очереди

JP=0;

- момент времени начала интервала до следующей

заявки

ТН=0;

- длительность периода занятости

PZ=0;

- память под все массивы:

N[J] – массив времен

поступления

J-х заявок в очередь; массивы чисел для

сравнения получаемых случайных величин (интервалов

времени между соседними заявками, времени ожидания

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

периода занятости и т.д.) с их оценками;

- и ввести значение вероятности

РР=Р

;

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

TZ, значение

JPМ и т.д.

Затем наращивается такт моделирования (см. блок 2 на

рис. 7.3) и за данный отрезок времени

Δt=1

просматриваются изменения в СМО, для чего и

предусмотрены подпрограммы.

167

Далее по алгоритму следует обращение к подпрограмме

GEN – генерация заявок входного потока (см. блок 3 на

рис. 7.3). Алгоритм подпрограммы

GEN будет рассмотрен

ниже. В подпрограмме

GEN на основе анализа полной

группы событий – поступления и непоступления заявок за

рассматриваемый такт

Т определяется факт появления

заявки (идентификатор

I=1) либо непоявления заявки

(идентификатор

I=0).

Зная такт моделирования

Т, результат работы

подпрограммы

GEN, при I=1 (см. блок 4 на рис. 7.3) и

числе заявок в очереди, меньшем максимально возможного

(см. блок 5 на рис. 7.3), обращаемся к подпрограмме набора

статистических данных потока заявок

STATP. Это

происходит потому, что заявка будет поставлена в очередь

на обслуживание. Переход к подпрограмме

STATP

возможен также и в том случае, если в данном такте

моделирования

Т заявка поступила в СМО и в этом же

такте СМО покидает заявка, обслуживание которой

завершено, т.е. идентификатор

L=0 (см. блок 6 на рис. 7.3).

В подпрограмме

STATP набираются статистические

данные для построения эмпирической кумулятивной

функции распределения

(t) длин интервалов между

двумя любыми соседними заявками. Алгоритм

подпрограммы

STATP будет рассмотрен ниже.

Затем следует постановка поступившей заявки в

очередь, что осуществляется в подпрограмме

OSTH.

Анализ очереди на обслуживание состоит из анализа

следующих событий:

а1) есть очередь и за такт Т поступила заявка;

а2) есть очередь и за такт Т не поступила заявка;

а3) нет очереди и за такт Т поступила заявка;

а4) нет очереди и за такт Т не поступила заявка.

Если поступившую в такт

Т заявку идентифицировать

обозначением

N[J]=T, где J – ее номер в очереди, а N[J]=T

168

– такт поступления заявки в систему, то при событии

а1

поступившая заявка получит значение идентификатора

N[J]=T, где J=JP+1, JP – число заявок в очереди в

предшествующем такте

Т-1. При событии а3 поступившая

заявка получит значение идентификатора

N[1]=T.

Если заявка поступила, а число заявок в очереди равно

JPM, а также при полностью заполненном буфере очереди

в этом такте не окончено обслуживание заявки, то

поступившая заявка теряется. В этом случае происходит

переход к подпрограмме набора статистических данных

потерянных заявок

STAТT.

Если прибор свободен от обслуживания (

L=0) и имеется

очередь на обслуживание (

М=1), то обращаемся к

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

WIB (см. работу блоков 10, 11, 12 на рис. 7.3).

В соответствии с заданной дисциплиной выбора на

обслуживание осуществляется выбор заявки из очереди

при условии, что прибор в такте

Т свободен от

обслуживания. Для заявки, выбранной на обслуживание,

определяется время пребывания в очереди

W и в

подпрограмме набора статистических данных времени

задержки в очереди

STATO величина W фиксируется для

набора статистических данных для дальнейшего

построения кумулятивной эмпирической функции

распределения времени ожидания

(t).

Затем в алгоритме следует переход к подпрограмме

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

OBS (см. блок 14 на

рис. 7.3). При имитации процессов (см. работу блоков 10,

11 на рис. 7.3), обслуживания прибором анализируются

следующие события:

б1) обслуживание предыдущей заявки окончено,

очереди нет и заявка не поступила;

б2) обслуживание окончено, заявка поступила, очередь

из одной поступившей заявки;

169

б3) обслуживание окончено, очередь есть, заявка не

поступила;

б4) обслуживание окончено, очередь есть, заявка

поступила;

б5) обслуживание не окончено, очереди нет, заявка не

поступила;

б6) обслуживание не окончено, очереди нет, заявка

поступила;

б7) обслуживание не окончено, очередь есть, заявка не

поступила;

б8) обслуживание не окончено, очередь есть, заявка

поступила.

При выполнении событий

б2, б3, б4 определяется время

обслуживания

В заявки, которая принята на обслуживание

в соответствии с результатом работы подпрограммы

WIB.

При событиях

б5 – б8 текущая величина времени

обслуживания

ВТ уменьшается на единицу. Текущая

величина времени обслуживания

ВТ введена в

соответствии с динамикой изменения времени

обслуживания, показанной на рис. 7.2.

Затем в подпрограмме набора статистических данных

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

STATB фиксируется величина В

для последующего построения кумулятивной

эмпирической функции распределения времени

обслуживания

(t). К подпрограмме STATB обращение

происходит только в том такте

Т, в котором определено

значение времени обслуживания

В при занятости прибора

обслуживанием (см. блоки 15, 16, 17 на рис. 7.3).

В подпрограмме

STATPZ (см. блок 20 на рис. 7.3)

фиксируется случайная величина

PZ – длительность

периода занятости для набора статистических данных

кумулятивной эмпирической функции распределения

периода занятости

(t). Обращение в подпрограмме

STATPZ происходит в том случае, если заявок в очереди

170

нет (см. блок 19 на рис. 7.3), прибор свободен от

обслуживания (см. блок 15 на рис. 7.3) и подсчитанная

величина

PZ больше нуля.

В подпрограмме

STATW фиксируется случайная

величина

IN – интервал времени между двумя соседними

обслуженными заявками, что позволяет набирать

статистические данные для дальнейшего построения

кумулятивной эмпирической функции распределения длин

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

(t).

7.6.2. Алгоритмы подпрограмм. Рассмотрим

особенности алгоритмов подпрограмм алгоритма

имитационной модели одноканальной СМО. На рис. 7.4

приведена структурная схема алгоритма подпрограммы

GEN.

1 0

Начало

RAN

x≤PP

I=1

Конец

I=0

Рис. 7.4

В программе GEN событие появления заявки I=1 (см.

блок 3 на рис. 7.4) либо событие непоявления заявки

I=0

(см. блок 4 на рис. 7.4) выбираются по известной схеме

моделирования случайных событий. Вероятность

поступления заявки

PP при условии пуассновского

распределения входного потока заявок определится, как

PP=αΔt.