Основные понятия моделирования СМО

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

Объект –любой элемент или компонент СМО, который должен быть заданным явно в модели СМО (например, устройство для обслуживания, машина).

Список – множество (постоянное или временное) связанных между собой объектов, упорядоченное согласно с определенным логичным правилом (например, все требования, которые находятся в определенное время в очереди, упорядочены по принципу «первым пришел – первым обслужили» или по приоритету).

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

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

Список событий – перечень намеченных будущих событий, упорядоченных по времени их возникновения, известный также как список будущих событий (СБС).

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

Задержка – протяженность неопределенного промежутка времени, для которого неизвестно загодя, когда он оканчивается (например, задержка требования в очереди по правилу «последний пришел – первым обслужили», для которого начало обслуживания зависит от будущих поступлений).

Модельное время – положительная возрастающая величина, которая отображает течение времени в имитационной модели.

Часы – переменная, которая отображает переменную модельного времени, в примерах – часы (CLOCK).

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

Пространство состояний СМО

Рассмотрим диаграмму состояний СМО с одним устройством для обслуживания. На вход системы в моменты времени ( ) поступают требования. Момент начала обслуживания требования устройством обозначим как , а момент завершения – . Момент выхода требования из системы совпадает с моментом завершения обслуживания требования устройством . Если в момент поступления требования в систему устройство для обслуживания занято, то оно должно ожидать обслуживания в очереди, как, например, требования под номерами 2, 4,5,6,7,8. Состояние очереди определяется количеством требований и позицией каждого из них в очереди. Во время освобождения устройства первое требование из очереди поступает для обслуживания. Таким образом, пространство состояний СМО определяется состояниями устройства для обслуживания и очереди. Изменение состояний системы связано с событиями поступления нового требования и занятости или освобождения устройства для обслуживания. Состояние очереди также зависит от состояния устройства для обслуживания. С каждым требованием j ассоциировано несколько событий: появление требования – , начало обслуживания – , конец обслуживания – . Тогда упорядоченное множество событий в модельном времени t описывает поведение СМО.

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

Если во время изменения модельного времени каждый раз проверять множество условий

для каждого требования j, чтобы начать некоторое действие из множества

то пары также будут описывать поведение СМО.

Пример построения модели СМО

Рассмотрим магазин с одним продавцом, который одновременно является и кассиром. Покупателя, который пришел в магазин и застал продавца свободным, немедленно обслуживают. Продавец переходит в состояние «занятый». Если во время обслуживания приходит другой покупатель (покупатели), то он становится в очередь. Закончив обслуживание, продавец переходит в состояние «свободный».

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

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

Название параметра	Значение по номеру покупателя
	1	2	3	4	5	6	7	8
Время поступления	2	2	7	3	2	3	1	1,5
Время обслуживания	4	2	6	5	3	2	2	1

Параметры СМО

Алгоритм моделирования СМО

Основой построения модели является объектный подход, который предусматривает создание модели системы как множества объектов, которые взаимодействуют между собой. В этой модели можно выделить объекты – требования (покупатели) и некоторый ресурс (R) – устройство для обслуживания (продавец).

Объекты	Опис ание
требования	покупатели
устройство обслуживания	продавец
очередь	“первым пришел – первым обслужили”

Если требование претендует на ресурс, занятый в данный момент времени, то оно становится в очередь. Очередь также является отдельным объектом – списком, связанным с ресурсом. Для системы обслуживания введем также правило обслуживания “первым пришел – первым обслужили”.

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

Для создания модели воспользуемся системой GPSS World – универсальной средой моделирования как дискретных, так и непрерывных процессов.

Объекты языка GPSS	Опис ание
блок GENERATE	создание объектов (“покупатель”)
блок SEIZE	запрос и назначение ресурса
блок ADVANCE	обслуживание требования
блок RELEASE	освобождение ресурса
блок TERMINATE	уничтожение требования
ПКМ	запускает процесс моделирования и контролирует перемещение каждого требования

Для создания объектов покупатель используется специальная подпрограмма (GENERATE) в языке GPSS. Алгоритм её работы.

1. Создать динамический объект покупатель. (Это структура данных, яка включает в себя такие поля: номер покупателя - , момент его прихода - , а также, если необходимо, свойства покупателя или его атрибуты, например, приоритет). Нужно также запланировать событие прихода, т.е. сообщение о событии.

2. Запланировать следующее событие для покупателя – запрос-назначение ресурса (продавец) на момент времени . Запланировать приход следующего объекта – покупатель +1.

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

Первая – это подпрограмма запроса и назначения ресурса требованию (SEIZE) в языке GPSS. Алгоритм её работы:

1. Если ресурс (объект продавец) может быть сразу предназначенным для требования , то изменить состояние ресурса на «занятый». Запомнить момент начала обслуживания требования .

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

Вторая – это подпрограмма обслуживания требования (ADVANSE) в языке GPSS. Алгоритм её работы очень простой. Она должна определить событие, которое наступает после завершения обслуживания требования : (где время обслуживания в устройстве), т.е. создание сообщения о событии в СБС, для того, чтобы передать руководство подпрограмме освобождения ресурса требованием .

Третья – подпрограмма освобождения ресурса требованием (RELEASE) в языке GPSS. Алгоритм её работы:

1. Изменить состояние ресурса на «свободный». Передать руководство подпрограмме уничтожения требования.

2. Передать наличие в очереди требования к ресурсу . Если они имеются, то выбрать требование из очереди и запланировать для неё событие запроса и назначения ресурса .

Подпрограмма уничтожения требования (TERMINATE в языке GPSS ) нужна для уничтожения структуры данных, которая создается для каждого требования.

Также нужна программа руководства всем процессом моделирования (ПКМ), которая запускает процесс моделирования и контролирует передвижение каждого требования («жизненный цикл») во время моделирования путем вызова подпрограмм обработки отдельных событий. Другое назначение этой программы – вести список упорядоченных во времени событий – СБС и продвигать часы модельного времени от события к событию. В языке GPSS функции ПКМ выполняет программа интерпретатор.

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

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

Дата добавления: 2021-07-19; просмотров: 65; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 12

Мы поможем в написании ваших работ!