1.3. Основы дискретно-событийного моделированияCmo
Определим основные понятия и термины, используемые в моделировании.
Система – множество объектов (например, людей и машин), которые взаимодействуют одновременно для достижения одной или большего количества целей.
Модель – абстрактное представление системы, обычно содержит структурные, логические или математические отношения, которые описывают систему в терминах состояний, объектов и их свойств, множеств, процессов, событий, действий и задержек.
Состояние системы – множество переменных, которые содержат всю информацию, необходимую для описания свойств системы в любое время.
Объект – любой элемент или компонент в системе, который должен быть представлен в модели в явном виде (например, обслуживающее устройство, клиент, машина).
Свойство или атрибут – свойства данного объекта (например, приоритет ожидающего клиента, маршрут процесса выполнения работ в цеху).
Список множество (постоянное или временное) связанных объектов, упорядоченное некоторым логическим способом (например, все клиенты, находящиеся в настоящее время в очереди ожидания, упорядочены по принципу «раньше прибыл, раньше обслужился» или по приоритету).
Событие – мгновенно возникающее изменение состояние системы (например, прибытие нового требования).
Уведомление о событии – запись события, которое произойдет в потоке событий или в некотором будущем времени нарядуcлюбыми связанными данными, необходимыми для обработки события (запись всегда включает тип события и время события).
Список событий – список намеченных будущих событий, упорядоченных по времени возникновения, известный также как список будущих событий (СБС).
Действие – продолжительность времени указанного промежутка (например, время обслуживания или время между поступлениями заявок), для которого известно, когда оно начинается и заканчивается (хотя оно может быть определено в терминах статистического распределения).
Задержка – продолжительность времени неопределенного промежутка, для которого неизвестно заранее, когда он заканчивается (например, задержка клиента в очереди по правилу «последний пришел – первый обслужился», так как начало обслуживания зависит от будущих поступлений).
Модельное время неотрицательная возрастающая величина, отражающая течение времени в имитационной модели.
Часы – переменная, отражающая протекание времени моделирования, называется в примерах ЧАСЫ (CLOCK).
Дискретно-событийное моделирование – моделирование системы в дискретные моменты времени, когда происходят события, отражающие последовательность изменения состояний системы во времени. В дальнейшем такое моделирование будем называтьимитационным. Рассматриваемые здесь системы динамические, то есть изменяются во времени. Поэтому состояние системы, свойства объекта и число активных объектов, параметров, действий и задержек – все они функции времени и постоянно изменяются в процессе моделирования.
Для CMOcодним устройством обслуживания событиями будут поступление требования и конец его обслуживания устройством. Начало обслуживания – это условное событие, которое зависит от состояния прибора (занят или свободен) и числа требований, находящихся в очереди. Задержку иногда называютусловным ожиданием, в то время как действие называютбезусловным ожиданием. Действиями будут время между поступлениями требований и время обслуживания прибором. Завершение действия – событие, часто называемоепервичным событием, для управления которым в СБС помещается уведомление о событии. Напротив, управление задержками связаноcпомещением объекта в другой список, возможно представляющий очередь ожидания до такого времени, когда системные условия разрешат обработку требования. Окончание задержки иногда называютусловным иливторичным событием, но такие события не представлены в соответствующих уведомлениях о событиях и не появляются в СБС.
Пример. Представим себе, что есть магазин, в котором один продавец и он же кассир. Если пришедший покупатель застает продавца свободным, то продавец немедленно приступает к его обслуживанию. Продавец переходит в состояние «занятый». Если продавец занят обслуживанием покупателя и в это время приходит другой (другие) покупатели, то они становятся в конец очереди к продавцу. Когда продавец закончил обслуживание, то он переходит в состояние свободный.
Если в очереди есть покупатели, то продавец «выбирает» для обслуживания первого покупателя из очереди. Очередь уменьшается на единицу. Все остальные покупатели в очереди, если они есть, продвигаются на одну позицию вперед. Если в очереди нет покупателей, то продавец остается в состоянии «свободный» до прихода следующего покупателя.
В табл. 1.1 представлены интервалы времени между приходами покупателей в магазин н требуемыми временами их обслуживания продавцом, А на рис. 1.3 проведено графическим методом «ручное» моделированиеCMOcодним устройством.
Cточки зрения объектного подхода имеются динамические объекты –требования (ПОКУПАТЕЛИ) и некоторый ресурс – устройство обслуживания (статический объект ПРОДАВЕЦ), которое они используют. Если требование претендует на ресурс, А он занят, то оно становится в ОЧЕРЕДЬ к ресурсу. ОЧЕРЕДЬ может быть отдельным объектом или просто списком, связаннымcресурсом. Примем за правило обслуживания –FIFO.
Таблица 1.1
№ покупателя | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
Время поступления, | 2 | 2 | 7 | 3 | 2 | 3 | 1 | 2 |
Время обслуживания, | 4 | 3 | 6 | 5 | 4 | з | з | 2 |
Для каждой пары «требование – ресурс» мы хотим определить, как долго требование jбудет использовать ресурсR, т.е. необходимо определить интервал времени, когда требованиюjназначен ресурсR и когда оноосвободит этот ресурс. Однако, прежде чем ресурс будет назначен требованиюj, он должен бытьзапрошен. В общем случае требование может ожидать в очереди до назначения ресурса.
Рис. 1.3
Опишем алгоритм работы системы cточки зрения «жизненного цикла» ПОКУПАТЕЛЯ, т.е. от момента его прихода в магазин до момента выхода из магазина. Так как покупатели непрерывно приходят в магазин на протяжении некоторого периода времени наблюдения за системой (время, в течении которого моделируется система), то необходимо обеспечить поток ПОКУПАТЕЛЕЙ путем их создания в модели (генерации в некоторые моменты времени – моменты их прихода в магазин). Для генерации ПОКУПАТЕЛЕЙ используем специальную подпрограмму ГЕНЕРАТОР (в языкеGPSSэтой подпрограмме соответствует блокGENERATE). Алгоритм ее работы следующий:
1. Создать динамический объект ПОКУПАТЕЛЬ в виде структуры данных, включающей в себя поля: номер покупателя – j, момент его прихода –, А также при необходимости свойства покупателя или его атрибуты (например, его приоритет). Запланировать событие – приход покупателяjна момент времени– т.е. создать уведомление о событии в СБС.
2. Запланировать следующее событие для покупателя j – ЗАПРОС-НАЗНАЧЕНИЕ ресурсаR (ПРОДАВЦА) на момент времени. Запланировать приход следующего динамического объекта ПОКУПАТЕЛЬj+ 1, т.е. определить событие прихода следующего покупателя: =+ .
Описание процесса использования ресурса требованием целесообразно разбить на три подпрограммы.
Первая – это ЗАПРОС-НАЗНАЧЕНИЕ ресурса R требованиюj(в языкеGPSSэтой подпрограмме соответствует блокSEIZE). Алгоритм ее работы следующий:
1. Если ресурс R (ПРОДАВЕЦ) может быть сразу назначен требованиюj, то изменить состояние ресурсаR на «занятый». Запомнить момент начала обслуживания требованияti+lн. Передать управление подпрограмме ОБСЛУЖИВАНИЕ требованияj.
2. Если ресурс R занятый, то поставить требованиеjв ОЧЕРЕДЬ к ресурсуR.
Вторая подпрограмма – ОБСЛУЖИВАНИЕ требования j(в языкеGPSSэтой подпрограмме соответствует блокADVANCE).Eeалгоритм работы очень простой – определить событие «конец обслуживания требованияNjкакtjк = tjн + tjоб(гдеtjоб – время обслуживания в устройстве). Т.е. создается уведомление о событии в СБС для передачи управления подпрограмме освобождения ресурсаR требованиемj.
Третья подпрограмма – ОСВОБОЖДЕНИЕ ресурса R требованиемj(в языкеGPSSэтой подпрограмме соответствует блокRELEASE). Алгоритм ее работы следующий.
1. Изменить состояние ресурса R (ПРОДАВЕЦ) на «свободный». Передать управление подпрограмме УНИЧТОЖЕНИЕ требования.
2. Проверить, есть ли требования в ОЧЕРЕДИ к ресурсу R? Если есть, то выбрать требование из ОЧЕРЕДИ и запланировать для него событие ЗАПРОС-НАЗНАЧЕНИЕ ресурсаR.
Подпрограмма УНИЧТОЖЕНИЕ требования (в языке GPSSэтой подпрограмме соответствует блокTERMINATE) необходима для уничтожения структуры данных каждого требования. Если требования не уничтожать, то со временем они переполнят память компьютера.
Кроме перечисленных подпрограмм необходима программа управления процессом моделирования (ПУМ), которая запускает процесс моделирования и отслеживает движение каждого требования по модели путем вызова названных подпрограмм обработки событий. Другое назначение этой программы – вести список упорядоченных во времени событий СБС и продвигать ЧАСЫ модельного времени от события к событию. В языке GPSSфункции ПУМ выполняет программа-интерпретатор (транслятор).
Список будущих событий содержит все уведомления для событий, которые были намечены, чтобы произойти в будущем времени. Механизм продвижения времени моделирования, гарантирующий, что все события происходят в правильном хронологическом порядке, основан на СБС.
Планирование будущего события означает, что в момент начала действия его продолжительность вычисляется или определяется (например, из заданного статистического распределения), чтобы установить время конца действия и занести это событие вместе cего временем в СБС. В реальном мире большинство будущих событий не намечено, они просто происходят (как, например, случайные поломки оборудования или случайные поступления покупателей). В модели такие случайные события представлены концом некоторого действия, которое запланировано на будущее модельное время.
В любое данное время моделирования t1мСБС содержит все предварительно намеченные будущие события и связанныеcэтими событиями временаt1м,t2м.....В СБС события упорядочены в хронологическом порядке по времени, то есть времена событий удовлетворяют условиям
Время tмзначения ЧАСОВ – текущее значение времени моделирования. Событие, связанное со временемt1м, называется предстоящим событием, то есть это следующее событие, которое произойдет. После того, как отображающие состояния системы ЧАСЫ =tм во время моделирования были модифицированы, ЧАСЫ продвигаются ко времени моделирования ЧАСЫ =t1м, предстоящее намеченное событие удаляется из СБС и выполняется подпрограмма события. Выполнение подпрограммы предстоящего события означает, что отображено новое состояние системы в течение времениt1м, которое создано на основании старого состояния модели во времяtм и характера предстоящего события. Во времяtм новые будущие события могут произойти или не произойти, но если любые из них намечены, то создаются намеченные события и помещаются в соответствующие позиции в СБС. После того, как новое отображение состояния системы в течение времениt1мбыло модифицировано, ЧАСЫ продвигаются ко времени нового предстоящего события, и выполняется подпрограмма этого события. Такой процесс повторяется до окончания имитации. На рис. 1.4 показана структурная схема имитационной модели.
В момент начала моделирования (время моделирования t0м=о) ПУМ передает управление подпрограмме ГЕНЕРАТОР, которая определяет момент прихода первого покупателя и намечает событие ЗАПРОС-НАЗНАЧЕНИЕ ресурсаR в СБС на времяt1м=t1вх. Так как больше событий в системе нет, то ЧАСЫ переводятся на значение времениt1м, вызывается подпрограмма ГЕНЕРАТОР и подпрограмма ЗАПРОС-НАЗНАЧЕНИЕ ресурсаR.
Подпрограмма ГЕНЕРАТОР определяет будущее событие (момент прихода второго покупателя t2вх) и намечает это событие в СБС на времяt2вх.
Подпрограмма ЗАПРОС-НАЗНАЧЕНИЕ проверяет состояние ресурса (ПРОДАВЦА). Так как ресурс R свободный, то он назначается первому покупателю и состояние ресурсаR изменяется на «занятый». Запоминается момент начала обслуживания требованияt1н. Передается управление подпрограмме ОБСЛУЖИВАНИЕ покупателя 1.
Подпрограмма ОБСЛУЖИВАНИЕ определяет событие конца обслуживания покупателя 1, как t1к= t1н + t1°б, т.е. создается уведомление о будущем событии в СБС для передачи управления подпрограмме ОСВОБОЖДЕНИЯ ресурсаR требованием 1 на времяt1к.
Рис. 1.4
Таким образом, в СБС имеется два элемента – один cнамеченным событием появления покупателя 2 на времяt2вх, А второйcнамеченным событием окончания обслуживания покупателя 1 на времяt1К. Если времяt2вх< t1к, то ЧАСЫ будут переведены на времяt2м=t2вх, т.e. снова будет вызвана подпрограмма ГЕНЕРАТОР и сгенерировано появление покупателя 2. В этот же момент времениt2м произойдет вызов подпрограммы ГЕНЕРАТОР, которая наметит в СБС появление покупателя 3 на времяt3вхи вызов подпрограммы ЗАПРОС-НАЗНАЧЕНИЕ ресурсаR, но так как ресурс занят обслуживанием покупателя 1, то покупатель 2 будет поставлен в очередь к ресурсуR.
В СБС снова окажутся два элемента – один для намеченного события появления покупателя 3 на время t3вх, А второйcнамеченным событием окончания обслуживания покупателя 1 на время t1r. Если времяt3вх>t1r, то ЧАСЫ будут переведены на времяt3м=t1к , т.е. – будет вызвана подпрограмма ОСВОБОЖДЕНИЕ ресурсаR покупателем 1. Она изменить состояние ресурсаR (ПРОДАВЕЦ) на «свободный» и передаст управление подпрограмме УНИЧТОЖЕНИЕ требования. Затем проверит, есть ли требования в ОЧЕРЕДИ к ресурсуR, и выберет покупателя 2 из ОЧЕРЕДИ, наметив для него событие для подпрограммы ЗАПРОС-НАЗНАЧЕНИЕ ресурсаR.
Вызванная в это же модельное время t3м подпрограмма УНИЧТОЖЕНИЕ разрушит структуру данных (удалит ссылку на адрес) для покупателя 1. Эта же подпрограмма при необходимости могла бы вычислить время пребывания покупателя 1 в системе, какt3пр =t3м –t1вх, для дальнейшей статистической оценки времени пребывания покупателей в системе.
В дальнейшем жизненный цикл других покупателей в системе будет происходить по описанному выше алгоритму.
Остается открытым вопрос об окончании процесса моделирования. Возможны три варианта:
1. Через модель пройдут все покупатели, сгенерированные ГЕНЕРАТОРОМ, например, 100 покупателей. В этом случае в СБС после обслуживания последнего, сотого, покупателя не будет ни одного намеченного события.
2. Если поток покупателей от генератора не ограничен (например, генерируется неограниченный пуассоновский поток), то моделирование можно закончить после прохождения через модель определенного количества покупателей, например, 1000. Для этого в подпрограмме УНИЧТОЖЕНИЕ надо поставить счетчик покупателей и прекратить моделирование после 1000 покупателей. В языке GPSSтакой счетчик организуется в командеSTART, которая начинает процесс моделирования.
3. Необходимо промоделировать работу системы в течение заданного периода времени, например, 480 мин. В этом случае можно при каждом продвижении ЧАСОВ модельного времени t проводить сравнение текущего времени со значением 480. Как только значение модельного времени будет больше или равно 480, необходимо прекратить моделирование. Однако такой способ неудачный, так как может сильно замедлить работу модели из-за проверки условия. Поэтому обычно поступают следующим образом. Генерируют специальное требование-таймерcпомощью еще одной подпрограммы ГЕНЕРАТОРcнамеченным временем входа в модельtm = 480. Требование-таймер после генерации сразу же направляется в еще одну подпрограмму УНИЧТОЖЕНИЯ, в которой ставят счетчик требований на единицу. По этому счетчику прекращают моделирование. В этом случае в СБС будет все время находиться элемент для требования-таймера со временем наступления события 480. Как только это событие станет предстоящим намеченным, ЧАСЫ будут переведены на время 480 и моделирование прекратится.
В процессе моделирования обычно собирается статистическая информация о работе модели при каждом продвижении ЧАСОВ модельного времени. Такой информацией может быть величина очереди, время пребывания в очереди и устройстве обслуживания, загрузка устройства, состояние прибора и другие параметры. Для сбора этой информации обычно создается подпрограмма ВЫБОРОЧНЫЙ ИЗМЕРИТЕЛЬ, которая накапливает ее и по окончании моделирования выдает стандартный статистический отчет. В языке GPSSтакая статистическая информация накапливается в системных числовых атрибутах (СЧА) и доступна в процессе моделирования только на считывание. Доступ к СЧА дает возможность управлять процессом движения требований, например, ограничивать размер или время нахождения в очереди.
В этой главе даны основы организации моделирования на примере простой CMO. В языкеGPSSобычно используются более сложные алгоритмы, описанные в параграфе 4.22.
- Предисловие
- Введение
- Глава 1. Модели массового обслуживания
- 1.1. Системы массового обслуживания и их характеристики
- 1.2. Системыcодним устройством обслуживания
- 1.3. Основы дискретно-событийного моделированияCmo
- 1.4. Многоканальные системы массового обслуживания
- Переменная vаr1, экспоненциальное распределение
- Глава 2. Вероятностные сети систем массового обслуживания
- 2.1. Общие сведения о сетях
- 2.2. Операционный анализ вероятностных сетей
- 2.3. Операционные зависимости
- 2.4. Анализ узких мест в сети
- Глава 3. Вероятностное моделирование
- 3.1. Метод статистических испытаний
- 3.2. Моделирование дискретных случайных величин
- 3.3. Моделирование непрерывных случайных величин
- 3.4. Сбор статистических данных для получения оценок характеристик случайных величин
- 3.5. Определение количества реализаций при моделировании случайных величин
- Глава 4. Система моделированияgpss
- 4.1. Объекты
- 4.2. Часы модельного времени
- 4.3. Типы операторов
- 4.4. Внесение транзактов в модель. БлокGenerate
- 4.5. Удаление транзактов из модели. БлокTerminate
- 4.6. Элементы, отображающие одноканальные обслуживающие устройства
- 4.7. Реализация задержки во времени. БлокAdvance
- 4.8. Сбор статистики об ожидании. БлокиQueue,depart
- 4.9. Переход транзакта в блок, отличный от последующего. БлокTransfer
- 4.10. Моделирование многоканальных устройств
- 4.11. Примеры построенияGpss-моделей
- 4.12. Переменные
- 4.13. Определение функции вGpss
- 4.14. Стандартные числовые атрибуты, параметры транзактов. Блоки assign, mark, loop
- Примеры фрагментов gpss-моделейcиспользованием сча и параметров гранзактов
- 4.15. Изменение приоритета транзактов. БлокPriority
- 4.16. Организация обслуживанияcпрерыванием. Блоки preempt и return
- 4.17. Сохраняемые величины
- 4.18. Проверка числовых выражений. БлокTest
- 4.19. Определение и использование таблиц
- 4.20. Косвенная адресация
- 4.21. Обработка транзактов, принадлежащих одному семейству
- 4.22. Управление процессом моделирования в системеGpss
- 4.23. Списки пользователей
- 4.24. Блоки управления потоками транзактовLogic,gatelr,gatelSиGate
- 4.25. Организация вывода временных рядов изGpss-модели
- 4.26. Краткая характеристика языкаPlus
- 4.27. КомандыGpssWorId
- 4.28. Диалоговые возможностиGpssWorld
- 4.29. Отличия междуGpssWorldиGpss/pc
- Глава 5. Моделирование вычислительных и операционных систем
- 5.1. Операционные системы компьютеров
- 5.2. Сети и системы передачи данных
- 5.3. Проблемы моделирования компьютеров и сетей
- Глава 6. Основы моделирования процессов
- 6.1. Производственные процессы
- 6.2. Распределительные процессы
- 6.3. Процессы обслуживания клиентов
- 6.4. Процессы управления разработками проектов
- Глава 7. Задания для самостоятельной работы Задание 1. Моделирование разливной линии
- Задание 2 [10]. Моделирование контроля и настройки телевизоров
- Задание 3. Моделирование работы кафе
- Задание 4. Моделирование работы обрабатывающего цеха
- Задание 5. Моделирование работы обрабатывающего цеха
- Задание 6. Моделирование работы обрабатывающего цеха
- Задание 7. Моделирование работыCmo
- Задание 8. Моделирование функций
- Задание 9 [10]. Моделирование системы обслуживания
- Задание 10 [16]. Моделирование системы автоматизации проектирования
- Задание 11 [16]. Моделирование работы транспортного цеха
- Задание 12 [16]. Моделирование системы передачи разговора
- Задание 13 [16]. Моделирование системы передачи данных
- Задание 14 [16]. Моделирование узла коммутации сообщений
- Задание 15 [16]. Моделирование процесса сборки
- Задание 16 [16]. Моделирование работы цеха
- Задание 17 [16]. Моделирование системы управления производством
- Задание 18. Моделирование производственного процесса
- Задание 19. Моделирование работы заправочной станции
- Задание 20. Моделированиеработы станции технического обслуживания
- Задание 21. Моделирование работы станции скорой помощи
- Задание 22. Моделирование работы госпиталя
- Задание 23. Моделирование работы маршрутных такси
- Задание 24. Моделирование работы печатной системы
- Задание 25. Моделирование процесса сборки пк
- Глава8. Проектирование имитационных моделей c помощью интерактивной системы имитационного моделирования
- 8.1. Структура интерактивной системы имитационного моделирования
- 8.2. Построение концептуальной схемы модели
- 8.3. Параметрическая настройка модели
- 8.4. Генератор формул
- 8.5. Управление экспериментом
- 8.6. Запуск эксперимента и обработка результатов моделирования
- 8.7. Управление проектами и общей настройкой системы
- 8.8. Пример построения модели средствамиIss2000
- Глава 9. Технология имитационного моделирования
- 9.1. Имитационные проекты
- 9.2. Организация экспериментов
- 9.3. Проблемы организации имитационных экспериментов
- 9.4. Оценка точности результатов моделирования
- 9.5. Факторный план
- 9.6. Дисперсионный анализAnovAв планировании экспериментов
- 9.7. Библиотечная процедураAnova
- 9.8. Технология проведение дисперсионного анализа в системеGpssWorld
- 9.9. Особенности планирования экспериментов
- 9.10. Нахождение экстремальных значений на поверхности отклика
- 9.11. Организация экспериментов вGpssWorId
- 9.L2. Выбор наилучшего варианта структуры системы
- Глава 10. Примеры принятия решенийcпомощью имитационного моделирования
- 10.1. Моделирование производственного участка
- 10.2. Моделирование технологического процесса ремонта и замены оборудования
- Приложение Системные сча
- Сча транзактов
- Сча блоков:
- Сча одноканальных устройств:
- Сча очередей
- Сча таблиц
- Сча ячеек и матриц ячеек сохраняемых величин:
- Сча вычислительных объектов
- Список литературы
- Срдержание
- Глава 5. Моделирование вычислительных и операционных систем 132
- Глава 10. Примеры принятия решений c помощью имитационного моделирования 201