Сети Петри. Способы представления. Маркировка, правила выполнения и пространство состояний сетей Петри.

ВСС=(Р,Т,Е) – связный биограф, где Р – конечное непустое множество позиций, Т – конечное непустое множество переходов, Е - отображение вида Т→Ф(Р); Ф(Р) – множество всех подмножеств Р. Позиции сети ,  отображают в модели все основные состояния процессов. Переходы ,  соответствуют событиям. Отображение  находит все смежные с t_j позиции из множества Р. Состояние ВСС определяется маркировкой позиций М: Р→N – функция маркировки  - разметка сети. Применяемые в ВСС метки имеют атрибуты:  - вектор атрибутов метки в позиции . Значения некоторых атрибутов могут быть функциями времени. Например, если позиция  моделирует в сети состояние “Идёт обработка детали”, то атрибут  в списке атрибутов метки  может означать время, оставшееся до конца обработки.

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

Механизм изменения состояний ВСС связан с выполнением переходов . Каждый переход можно записать в виде тройки . Здесь  - условия возбуждения,  - схема выполнения,  - процедура перехода. Условие возбуждения  - это предикат, определённый на множестве позиций из , истинный только в том случае, когда реализуется некоторая заданная разметка позиций множества . Кроме того, условие возбуждения, может включать ещё проверку значений атрибутов меток. Если значение какого-то атрибута является функцией времени, то обеспечивается соответствующая значению данной функции времени задержка. Схема выполнения определяет изменение разметки позиций сети при срабатывании перехода. Пусть  - упорядоченное множество позиций, смежных с . Тогда схема  - это вектор, элементы которого образуют биекцию с элементами множества . Любое положительное целое число в  означает число меток, помещённых в соответствующую позицию после выполнения перехода. Целые отрицательные числа в  указывают число удалённых меток из соответствующих позиций. Нулевые значения компонент отмечают изменяемые позиции (каждая изменяемая позиция не обязательно имеет единственную метку и образует с переходом  цикл длины 2). Не изменяемые в результате срабатывания перехода позиции отмечаются в  символом (*). Процедура перехода  представляет собой правила вычисления атрибутов (для позиций, отмеченных в  нулём) или добавления (удаления) меток.

Графическое изображение ВСС имеет некоторые отличительные особенности. Каждая позиция ВСС обозначатся кружком, каждый переход - барьером, позиции и переходы соединяются ориентированными или неориентированными рёбрами в соответствии с отображением Е и схемой выполнения перехода . Ребро не ориентируется, если в схеме  для соответствующей позиции указывается символ (*). Ребро ориентируется от позиции к переходу, если в  для этой позиции задано отрицательное число, от перехода к позиции – если положительнее число. Ребро будет двунаправленным, если задан 0.

 

 

Билет №27

Обобщение сетей Петри.

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

Сети Петри со сдерживающими дугами. Сдерживающая дуга из позиции p_i в переход tj имеет маленький кружок (а не стрелку). Кружок означает отрицание (“не”). Правила запуска изменяются следующим образом: переход является разрешённым, когда фишки присутствуют во всех его (обычных) входах и отсутствуют в сдерживающих входах. Переход запускается удалением фишек из всех его (обычных) входов. Так можно описывать переходы, «исключающее ИЛИ». В обычных СП переход запускается, когда все его входы имеют фишки (логика И). Переход “исключающее ИЛИ” запускается тогда и только тогда, когда только один из его входов имеет фишки, а все другие фишек не имеют. Когда переход запускается, он удаляет фишку только из входа с фишками.

Имеются ещё два других важных расширений СП. Переходам могут быть поставлены в соответствие приоритеты так, что если t_i и t_k оба допустимы, то переход с высшим приоритетом будет запущен первым. Механизм назначения приоритетов может устанавливать порядок срабатывания переходов при возникновении конфликтов. Во-вторых, используют временные сети Петри. Во временных сетях Петри каждому переходу t_j сопоставляются два момента времени τ_1,j и τ_2,j. Переход t_j может быть запущен, только если он был разрешён к моменту времени τ_1,j. Если он является разрешённым, то должен быть запущен до наступления момента времени τ_2,j. Рассмотрим временные сети более подробно.

Формально временные сети задаются набором (P, T, I, O, μ°, Z), где P, T, I, O, μ имеют обычный смысл, а Z: P→R⁺ функция времени задержки меток в позициях сети. Работа временных сетей подчиняется следующим правилам:

▪ метки в позициях могут быть доступными или же недоступными;

▪ переходы считаются возбуждёнными, если все их входные позиции имеют метки и эти метки доступные;

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

▪ каждая метка, совершившая переход из  в , будет недоступной в  в течении времени , начиная с момента её появления в . По истечению времени  метка становится доступной.

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

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

Билет №28

⇐ Предыдущая567891011121314Следующая ⇒

Поделиться: