Диссертация (1152223), страница 72

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 72)

Везде далее мы будем рассматривать СП только такого вида.Ограниченность — это свойство, лимитирующее максимальное допустимое число маркеров, которое может помещаться в любой позиции СП. Говорят, что сеть является Кограниченной, если максимально в позицию может помещаться не более К маркеров. ПозицияpiP сети C=(P, T, F, M0) является К-ограниченной, если число маркеров в этой позиции m(pi)К для всех маркировок M R(M0), которые могут быть достигнуты из начальной маркировкиM0. Сеть Петри ограничена, если все её позиции ограничены.Безопасность — это частный случай ограниченности, максимальное количество маркеров в позиции не превышает одного. Позиция piP сети C=(P, T, F, M0) является безопасной,если число маркеров в этой позиции m(pi) 1 для любой M R(M0).

Сеть Петри безопасна, еслибезопасна каждая её позиция. Безопасность — важное свойство, если планируется моделировать работу вычислительного устройства. Поскольку безопасная позиция может содержать число меток 0 или 1, она может моделировать работу двоичного триггера280Сохранение — это свойство, характеризующее количество маркеров, циркулирующих посети Петри. Количество маркеров, циркулирующих в сети, может изменяться.

Некоторые конфигурации СП могут генерировать маркеры в сети или уничтожать их. Сеть, которая не изменяет общее количество маркеров, которые присутствовали в начальной маркировке, называютстрого сохраняющей. Иными словами, для всех допустимых маркировок M R(M0) количествомаркеров в позициях сети не меняется, т.е. выполняется условие (5.2):(5.2)Это строгое ограничение, поскольку из него следует, число входящих в переход дуг равночислу исходящих, иначе срабатывание перехода изменит число маркеров |•t| = |t•| [303].Можно ослабить ограничение, потребовав, чтобы сеть целиком не изменяла числа маркеров, накаждое входное воздействие генерировала ровно один отклик.

Сеть, которая имеет одинаковоечисло маркеров в начальной маркировке M0 и некоторой конечной маркировке Mк,, тогда как вдругих маркировках число маркеров может увеличивается или уменьшаться, называется сохраняющей относительно некоторого вектора взвешивания. Вектор взвешивания W это векторстолбец размера (n ×1), где n равняется числу позиций сети. Каждый элемент этого вектора wiсоответствует позиции pi сети и обозначает некоторый весовой коэффициент.

Вес выбираетсятаким образом, чтобы для всех позиций сети произведение числа маркеров в позиции на её весбыли постоянны. Если m0 число маркеров в начальной позиции, а mi — в произвольной достижимой позиции, то произведение числа маркеров на соответствующие веса w 0Tm0 = wiTmi является константой для всех позиций сети, где знак T обозначает операцию транспонированияматрицы, а умножение является матричным. Свойство сохранения очень важно для моделирования диаграмм потоков работ.

Мы ранее показали, что один сигнал на входе генерирует на выходе только один выход. Следовательно, СП, моделирующая бизнес-процесс, должна быть сохраняющей.Сеть называется реверсивной, если начав из начальной маркировки M0, Mi, можно вернуться обратно в начальную маркировку M0. Иными словами, если для любой маркировки, достижимой из начальной ∀Mi ∈ R(M0), начальная маркировка M0 снова достижима из Mi (M0 ∈R(Mi)), то сеть реверсивная, формула (5.3).T, T1T такие, что •T1⊂ T1•(5.3)Абсорбер СП может поглощать маркеры, что может привести к ошибке потеря синхронизации. Это переход, вход которого принадлежит множеству его выходов, формула (5.4).T, T2T такие, что T2• ⊂ •T2(5.4)Сеть называется вполне завершаемой, если всякий раз, когда её выполнение завершается:(1) маркер достигает позиции, обозначенной как конечная, (2) в сети не остаётся других маркеров [303].281Сеть (N,M0) называют консистентной, если существует начальная маркировка M0, и последовательность срабатываний σr = tj1,tj2,,tjr, такая, что в результате их срабатываний снова будет достигнута маркировка M0, причём каждый переход из σr сработает как минимум один раз.Сеть называют частично консистентной, если некоторые из переходов σr сработают один раз.Сеть Петри может содержать ловушки, сифоны и циклы, как показано на рисунке 5.10.Рисунок 5.10 - Ошибки в модели процесса: (а) Ловушка, (б) Сифон, (и) ЦиклИсточник: составлено автором.Кластер, это минимально возможная группа улов СП , двух типов:­Переходы вместе с позициями, с которыми они связаны входящими дугами.­Позиции вместе с переходами, с которыми она связана исходящими дугами, а также другими позициями, с которыми последние связаны входящими дугами;Кластером называется позиция сети Петри вместе со всеми переходами, для которых она является входной, как показано на рисунке 5.11, который изображает сеть Петри с тремя кластерами, первый – X1 образован позицией p1 и переходом t1; второй – p2, p3, t2, t3; третий – p5, t4,t5.

Кластер обозначается [x]. Если узел x принадлежит кластеру [x] (x ∈ [x]), то выполняются условия (5.5 и 5.6):∀t ∈ T : t ∈ [x] ⇒ •t ⊂ [x];(5.5)∀p ∈ P : p ∈ [x] ⇒ p• ⊂ [x];(5.6)x1x2p2t2t1p4p3p1t6t3p5t4p6t5x3Рисунок 5.11 - Кластеры сети ПетриИсточник: составлено автором по материалам [305].282Задачи достижимости и покрываемости сети ПетриЗадача покрываемости формулируется следующим образом: для СП с начальной маркировкой M0 и промежуточной маркировкой M1 R(M0) следует определить, существует ли ещеодна достижимая маркировка M2 R(M0), такая что M2 M1. Задача достижимости формулируется следующим образом: пусть есть СП с начальной маркировкой M0, маркировка M1 называется достижимой, если существует последовательность срабатываний δ, в результате которойСП переходит из начальной маркировки M0 в маркировку M1.Анализ сетей Петри методом графа достижимостиГраф достижимости показывает все возможные маркировки СП.

Пусть есть СП имеющаяначальную маркировку M0. Предположим, из этой маркировки достижимы две: M1 и M2. Каждаяиз них, в свою очередь, имеет достижимые маркировки: M11, M12, M13 и M21, M22. Повторяя этупроцедуру таким же образом, можно построить дерево всех достижимых маркировок. Однакоесть опасность, что полученное дерево окажется бесконечным, поэтому необходимо найтисредство для ограничения его до конечного размера. Принято использовать три метода ограничения размена дерева.

Во-первых, будем искать маркировки, в которых нет разрешённых переходов, иначе называемые терминальными вершинами. Во-вторых, если обнаружится, что некоторая маркировка уже ранее встречалась, то дальнейшее построение дерева можно прекратить— мы снова повторно придём к известной маркировке. Соответствующие вершины называютсядублирующими. В-третьих, если обнаружится такая маркировка M2, которая совпадает с другоймаркировкой M1 (M1 < M2), причём обе имеют маркеры в одноименных позициях, однако количество маркеров в этих одноименных позициях может отличаться, то такая позиция помечаетсяω-позиция, а соответствующая вершина помечается как дублирующая.

Дело в том, что длясрабатывания перехода важно наличие маркера в позиции, а количество маркеров неважно, т.ч.эти дополнительные «лишние» маркеры на запуск переходов не влияют. Таким образом, повторный запуск последовательности срабатываний из M1 в M2 приведёт к увеличению числамаркеров в соответствующей позиции. Наличие в графе достижимости ω-вершин сигнализирует, что свойство ограниченности не выполняется. В результате, любая вершина графа достижимости классифицируется как граничная, терминальная, дублирующая или внутренняя.Из анализа дерева достижимости СП можно сделать следующие выводы:–Сеть ограничена, если в дереве достижимости отсутствует дублирующие вершины.

Вэтом случае сеть описывает систему конечных состояний, что позволяет проводить анализ простым перебором конечного множества всех достижимых маркировок.–Сеть Петри является сохраняющей, если взвешенная сумма для каждой достижимой мар-283кировки не меняется.–Сеть Петри является строго сохраняющей, если она не генерирует и не уничтожает мар-керы, а только передвигает их, что можно проверить путем вычисления суммы меток для каждой маркировки.–Задача покрываемости маркировки М1 маркировкой М2 сводится к поиску на дереве такойвершины, маркировка которой покрывает состояние М1. Если такой вершины не существует,маркировка М1 не покрывается никакой достижимой маркировкой.–Сеть не является активной (содержит тупики), если в ней присутствуют терминальныевершины.–Если некоторая маркировка M’ встречается в дереве достижимости, это означает её достижимость.–Если некоторая маркировка M’ не покрывается ни одной вершиной дерева достижимости,то она недостижима.Таким образом, дерево достижимости помогает решать задачи: безопасности, ограниченности, сохранения и покрываемости, но не позволяет анализировать достижимость и активность, а также определять возможную последовательности срабатываний переходов.

Проблемазаключается в наличии дублирующих вершин, символ ω скрывает точное число маркеров.Поскольку дерево достижимости строится, начиная с начальной маркировки, она зависитот начальной маркировки, следовательно, является поведенческой. Пример СП, её графа достижимости и дерева достижимости показан на рисунке 5.12.(1,0,1,0)p2p0t0А)t0t1p1p3t2(0,1,1,0)t1Б)(0,1,0,1)(1,0,1,0)t1t0(0,1,1,0)(1,0,0,1)t3(0,1,0,1)t1В)(0,1,0,1)t1(1,0,0,1)t3(0,1,0,1)Рисунок 5.12 - Сеть Петри (а), её граф достижимости (б) и дерево достижимости (в)Источник: составлено автором по материалам [306].Фундаментальное уравнение сетей ПетриФундаментальное уравнение СП позволяет вычислить будущее состояние сети, если известно её текущее состояние, оно базируется на матричном подходе.

Сеть представляется матрицей инцидентности A = [aij], которая имеет размер n*m, где n — число столбцов (по одномуна позицию соответствующей СП), а m — число строк (по одной на переход этой сети).Каждый элемент этой матрицы:aij = aij+ — aij- , где:aij+ количество дуг исходящих из перехода j в сторону позиции i;aij- количество дуг входящих в переход j из позиции i;284иными словами, каждый элемент определяет, сколько маркеров потеряет или получит позиция в результате срабатывания соответствующего переходаТекущая маркировка M=[mi] есть вектор-столбец, имеющий n элементов (по одному напозицию этой сети), формула (5.7).m1m 2 , где mi — число маркеров в одной из позиций сети.M(5.7)m3Вектор срабатывания U=[uj] есть вектор-строка, имеющая m элементов (по одному на переход этой сети).

Характеристики

Список файлов диссертации