Задачи анализа сетей Петри

 

Безопасность. Позиция p_iÎ Pсети Петри С = (P, Т, I, О) с начальной маркировкой μявляется безопасной, если μ' (p_i) ≤ 1 для любой μ' Î R(C, μ). Сеть Петри безопасна, если безопасна каждая ее позиция. Безопасность — очень важное свойство для устройств аппаратного обеспечения. Если позиция безопасна, то число фишек в ней равно 0 или 1. Следовательно, позицию можно реализовать одним триггером.

Ограниченность. Безопасность — это частный случай более общего свойства ограниченности. Позиция p_i Î Pсети Петри С — (Р, Т, I, О) с начальной маркировкой μявляется k-безопасной, если μ'(р _i) ≤ kдля всех μ' Î R(C, μ). 1-безопасная позиция называется просто безопасной. Заметим, что граница kпо числу фишек, которые могут находиться в позиции, может быть функцией от позиции (например, позиция p₁может быть 3-безопасной, тогда как позиция p₂ — 8-безопасной). Однако, если позиция p_ik-безопасна, то она также и k'-безопасна для всех k' ³ k. Поскольку число позиций конечно, можно выбрать k^*, равное максимуму из границ каждой позиции, и определить сеть Петри k^*-безопасной, если каждая позиция сети k^*-безопасна.

Иногда интересуются только тем, является число фишек в позиции ограниченным или нет, а не конкретным значением границы. Позиция называется ограниченной, если она k-безопасна для некоторого k; сеть Петри ограниченна, если все ее позиции ограниченны. Ограниченную сеть Петри можно реализовать аппаратно, тогда как сеть Петри с неограниченными позициями в общем случае реализовать аппаратно нельзя.

Сохранение. Сети Петри можно использовать для моделирования систем распределения ресурсов. В этом случае некоторые фишки могут представлять собой ресурсы. Для сетей Петри такого типа важным свойством является сохранение.

Сеть Петри С = (Р, Т, I, О) с начальной маркировкой называется строго сохраняющей, если для всех μ' Î R(C, μ)

.

Строгое сохранение — это очень сильное ограничение. Например, из него немедленно следует, что число входов в каждый переход должно равняться числу выходов, |I(t_j)| = |O(t_j)|. Если бы это было не так, запуск перехода изменил бы число фишек в сети.

Сеть Петри должна сохранять ресурсы, которые она моделирует. Однако взаимно однозначного соответствия между фишками и ресурсами нет. Фишка может представлять и один программный счетчик или какой-нибудь другой элемент и может представлять несколько ресурсов сразу. Во втором случае фишка позже используется для создания кратных фишек (по одной на ресурс) путем запуска перехода с большим числом выходов, чем входов. В общем, следует определить взвешивание фишек. Взвешенная сумма для всех достижимых маркировок должна быть постоянной. Фишкам, не являющимся важными, можно присвоить вес 0; другим фишкам можно присвоить веса 1, 2, 3 или любое другое целое. Фишка определяется ее позицией в сети, все фишки в позиции неразличимы. Следовательно, веса связываются с каждой позицией сети. Вектор взвешивания w= (w₁, w₂,..., w_n) определяет вес w_i для каждой позиции p_iÎ P.

Сеть Петри С = (Р, Т, I, О) с начальной маркировкой μ называется сохраняющей по отношению к вектору взвешивания w = (w₁, w₂,..., w_n), n= |P|, w_i ³ 0, если для всех μ' Î R(С, μ)

.

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

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

Тупик в сети Петри — это переход (или множество переходов), которые не могут быть запущены. Переход называется активным, если он не заблокирован (нетупиковый). Это не означает, что переход разрешен, скорее он может быть разрешенным. Переход t_j сети Петри С называется потенциально запустимым в маркировке μ, если существует маркировка μ' Î R(C, μ), в которой t_j разрешен. Переход активен в маркировке μ, если потенциально запустим во всякой маркировке из R(С, μ). Следовательно, если переход активен, то всегда возможно перевести сеть Петри из ее текущей маркировки в маркировку, в которой запуск перехода станет разрешенным.

Существуют другие, связанные с активностью понятия, которые рассматривались при изучении тупиков. Их можно разбить на категории по уровню активности и определить для сети Петри Cс маркировкой μ следующим образом:

Уровень 0:Переход t_j обладает активностью уровня 0 и называется пассивным или мертвым, если он никогда не может быть запущен.

Уровень 1: Переход t_j обладает активностью уровня 1 и называется потенциально активным или живым, если он потенциально запустим, т. е. если существует такая μ' Î R(C, μ), что t_j разрешен в μ'.

Уровень 2: Переход t_j обладает активностью уровня 2, если для всякого целого nсуществует последовательность запусков, в которой t_j присутствует по крайней мере nраз.

Уровень 3:Переход t_j обладает активностью уровня 3, если существует бесконечная последовательность запусков, в которой t_j присутствует неограниченно часто.

Уровень 4:Переход t_j обладает активностью уровня 4 и называется активным или живым, если для всякой μ' Î R(C, μ) существует такая последовательность запусков σ, что t_j разрешен в δ (μ', σ).

Сеть Петри обладает активностью уровня i, если каждый ее переход обладает активностью уровня i.

Устойчивость переходов и СП. Переход t_i СП С = (Р, Т, I, О) с маркировкой μ называется устойчивым, если он активен при данной маркировке и никакой другой переход t_k, тоже активный при маркировке μ, не может, сработав, сделать переход t_i неактивным, т.е. лишив его возможности срабатывания. СП С = (Р, Т, I, О) с маркировкой μ называется устойчивой, если все ее переходы являются устойчивыми.

Достижимость и покрываемость. Большинство задач, к которым мы до сих пор обращались, касаются достижимых маркировок.

Задача достижимости. Для данной сети Петри С с маркировкой μ и маркировки μ' определить: μ' Î R(C, μ)? Задача достижимости, быть может, основная задача анализа сетей Петри; многие другие задачи анализа можно сформулировать в терминах задачи достижимости.

Задача покрываемости. Эта задача аналогична достижимости, но несколько отличается. Для данной сети Петри С с начальной маркировкой μи маркировки μ’ определить, существует ли такая достижимая маркировка
μ" Î R(C, μ), что μ" ³ μ '.

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

Последовательности запусков. Другой предложенный к анализу подход основан не на позициях, а на последовательностях запусков переходов, т. е. связан с активностью, поскольку уместен вопрос: может ли переход быть запущен (иначе, не является ли он пассивным)? В более общем случае можно потребовать определить, возможна ли заданная последовательность запусков переходов или возможна ли какая-либо последовательность из множества последовательностей запусков.

Задачи эквивалентности и подмножества. Последний класс задач порожден соображениями оптимизации. Пусть сети Петри присуще некоторое поведение, определяемое ее множеством последовательностей запусков переходов или ее множеством достижимости. Можно ли изменить (оптимизировать) сеть Петри, не изменяя ее поведения? Изменение означает удаление пассивных переходов (которые никогда нельзя запустить) или пассивных позиций {которые никогда не могут быть маркированы), или переопределение некоторых переходов. Можно ли показать, что две различные маркированные сети Петри с одинаковым числом переходов (но с различным числом позиций) будут порождать одинаковые последовательности запусков переходов или что две различные маркированные сети Петри с одинаковым числом позиций (но с различным числом переходов) будут порождать одно множество достижимости? Это позволило бы модифицировать сети Петри для увеличения параллелизма, уменьшения стоимости реализации или улучшения других оптимизируемых функционалов. В этих случаях затрагивается проблема определения того, являются ли две сети Петри эквивалентными или является ли одна из них подмножеством другой. Для точного определения понятия эквивалентности или включения необходимо быть особенно внимательным. Если определить эквивалентность как равенство множеств достижимости, тогда нельзя будет изменять число позиций, если потребовать равенства множеств последовательностей — нельзя будет изменять переходы. Поэтому определение задачи, которое дается, исключительно важно.

 

 

Методы анализа

 

Существуют два основных метода анализа сетей Петри, которые описывают механизмы решения некоторых из уже перечисленных задач. Первый метод анализа, используемый для сетей Петри, — это дерево достижимости, второй метод связан с матричными уравнениями. Обсудим подробнее первый из них.

Дерево достижимости. Дерево достижимости представляет множество достижимости сети Петри. Рассмотрим, например, маркированную сеть Петри на рис. 1.11. Начальная маркировка ее — (1, 0, 0). В этой начальной маркировке разрешены два перехода: t₁ и t₂. Пусть корнем является вершина, соответствующая начальной маркировке, определим новые вершины в дереве достижимости для (достижимых) маркировок, получающихся в результате запуска каждого из этих двух переходов. Дуга, помеченная запускаемым переходом, приводит из начальной маркировки к каждой из новых маркировок (рис. 1.12). Это (частичное) дерево показывает все маркировки, непосредственно достижимые из начальной маркировки.

Теперь необходимо рассмотреть все маркировки, достижимые из новых маркировок. Из маркировки (1, 1, 0) можно снова запустить t₁ (получая 1, 2, 0) и t₂ (получая (0, 2, 1)); из (0, 1, 1) можно запустить t₃ (получая (0, 0, 1)). Это порождает дерево, изображенное на рис. 1.13. Начиная с трех новых маркировок, необходимо повторить этот процесс, порождая новые маркировки, которые нужно ввести в дерево, как показано на рис. 1.14.

Рис. 1.11. Маркированная сеть Петри, Рис. 1.12. Первый шаг построения

для которой строится дерево достижимости. дерева достижимости

 

Заметим, что маркировка (0, 0, 1) пассивная; никакой переход в ней не является разрешенным, поэтому никакие новые маркировки из этой пассивной маркировки в дереве порождаться не будут. Кроме того, необходимо отметить, что маркировка (0, 1, 1), порождаемая запуском t₃ в (0, 2, 1), была уже порождена непосредственно из начальной маркировки запуском t₂.

Рис. 1.13. Второй шаг построения дерева достижимости.

 

Если эту процедуру повторять снова и снова, каждая достижимая маркировка окажется порожденной. Однако получившееся дерево достижимости может оказаться

Рис. 1.14. Третий шаг построения дерева достижимости.

 

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

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

Приведение к конечному представлению осуществляется несколькими способами. Нам необходимо найти те средства, которые ограничивают введение новых маркировок (называемых граничными вершинами) на каждом шаге. Здесь могут помочь пассивные маркировки — маркировки, в которых нет разрешенных переходов. Эти пассивные маркировки называются терминальными вершинами. Другой класс маркировок — это маркировки, ранее встречавшиеся в дереве. Такие дублирующие маркировки называются дублирующими вершинами; никакие последующие маркировки рассматривать нет нужды — все они будут порождены из места первого появления дублирующей маркировки в дереве. Таким образом, в дереве на рис. 1.14 маркировка (О, 1. 1), получившаяся в результате выполнения последовательности t₁t₂t₃, не будет порождать какие-либо новые вершины в дереве, поскольку она ранее встречалась в дереве в результате выполнения последовательности t₃ из начальной маркировки.

Для сведения дерева достижимости к конечному представлению используется еще одно средство. Рассмотрим последовательность запусков переходов σ, начинающуюся в начальной маркировке μ и кончающуюся в маркировке μ', μ' > μ. Маркировка μ' совпадает с маркировкой μ, за исключением того, что имеет некоторые «дополнительные» фишки в некоторых позициях, т. е. μ' = μ + (μ’ - μ) и (μ’ - μ) > 0. Теперь, поскольку на запуски переходов лишние фишки не влияют, последовательность σ можно запустить снова, начиная с μ', приходя к маркировке μ". Так как действие последовательности переходов σ добавило μ' — μ фишек к маркировке μ, она добавит также μ' — μ фишек и к маркировке μ', поэтому μ" = μ' + (μ' — μ) или μ" ⁼ μ + 2 (μ' — μ). В общем можно запустить последовательность σ n раз, получив в результате маркировку μ + n(μ' — μ). Следовательно, для тех позиций, которые увеличивают число фишек последовательностью σ, можно создать произвольно большое число фишек, просто повторяя последовательность σ столько, сколько это нужно. В сети Петри на рис. 1.11, например, можно запустить переход t₁ столько раз, сколько необходимо для того, чтобы получить произвольное число фишек в р₂.

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

ω + а = ω a < ω,

ω – a = ω ω ≤ ω.

Для построения дерева достижимости необходимы только эти операции над ω.

Теперь можно точно сформулировать действительный алгоритм построения дерева достижимости. Каждая вершина i дерева связывается с расширенной маркировкой μ[i]; в расширенной маркировке число фишек в позиции может быть либо неотрицательным целым, либо ω. Каждая вершина классифицируется как граничная вершина, терминальная вершина, дублирующая вершина, или как внутренняя вершина. Граничными являются вершины, которые еще не обработаны алгоритмом; алгоритм превратит их в терминальные, дублирующие или внутренние вершины.

Алгоритм начинает с определения начальной маркировки корнем дерева, т. е. граничной вершиной. До тех пор пока имеются граничные вершины, они обрабатываются алгоритмом.

Пусть х — граничная вершина, которую необходимо обработать.

1. Если в дереве имеется другая вершина у, не являющаяся граничной, и с ней связана та же маркировка, μ [х] = μ [у], то вершина х — дублирующая.

2. Если для маркировки μ [x] ни один из переходов не разрешен (т. е. δ (μ[x], t_j]) не определено для всех t_j Î Т), то х — терминальная вершина.

3. Для всякого перехода t_j Î T, разрешенного в μ [x] (т. е. δ (μ [x], t_j) определено), создать новую вершину z дерева достижимости. Маркировка μ [z], связанная с этой вершиной, определяется для каждой позиции p_i следующим образом:

а) Если μ [x]_i = ω, то μ [z]_i = ω.

б) Если на пути от корневой вершины к х существует вершина у с μ [у] < δ (μ[x] t_j) и μ [y]_i < δ (μ [x], t_j)_i, то μ [z]_i = ω.

в) В противном случае μ [z]_i = δ (μ [х], t_j)_i.

Дуга, помеченная t_j, направлена от вершины х к вершине z. Вершина х переопределяется как внутренняя, вершина z становится граничной.

Когда все вершины дерева — терминальные, дублирующие или внутренние, алгоритм останавливается.

На рис. 1.15 представлено дерево достижимости для сети Петри на рис. 1.11.

 

Рис. 1.15. Дерево достижимости сети Петри, приведенной на рис. 1.11.

 

Дерево достижимости — очень полезный инструмент анализа сетей Петри. Покажем, как его можно использовать для решения некоторых задач, представленных выше.

Безопасность и ограниченность. Сеть Петри безопасна, если число фишек в каждой позиции не может превысить 1; сеть Петри ограниченна, если существует такое целое k, что число фишек в любой позиции не может превысить k. Оба этих свойства можно проверить с помощью дерева достижимости. Сеть Петри ограниченна тогда и только тогда, когда символ ω отсутствует в ее дереве достижимости. Присутствие символа ω в дереве достижимости означает, что число фишек потенциально не ограничено; существует последовательность запусков переходов, которую можно повторить произвольное число раз, увеличивая количество фишек до произвольно большого числа. Таким образом, если имеется символ ω, сеть неограниченна. Кроме того, положение символа ω показывает, какие позиции неограниченны.

Обратное утверждение также является верным, если сеть Петри неограниченна, то число достижимых маркировок бесконечно. Поскольку дерево достижимости конечно, бесконечное число достижимых маркировок отражает присутствие символа ω.

Если сеть Петри ограниченна и символ w отсутствует в дереве достижимости, то сеть Петри представляет систему конечных состояний. Дерево достижимости, по существу, является графом состояний и будет содержать вершину, соответствующую всякой достижимой маркировке. Это позволяет решить вопросы анализа простым перебором и проверкой конечного множества всех достижимых маркировок. Например, чтобы определить границу для заданной позиции, нужно построить дерево достижимости и найти наибольшее значение компоненты маркировки, соответствующей этой позиции.

Найденное значение является границей числа фишек для заданной позиции. Если граница для всех позиций не превышает 1, сеть безопасна.

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

Сохранение. Сеть Петри является сохраняющей по отношению к вектору взвешивания, если взвешенная сумма фишек постоянна для всех достижимых маркировок. Свойство сохранения эффективно проверяется с помощью дерева достижимости. Так как дерево достижимости конечно, для каждой маркировки можно вычислить взвешенную сумму. Если сумма одинакова для каждой достижимой маркировки, сеть — сохраняющая по отношению к данному весу. Если суммы не равны, сеть — несохраняющая.

При оценке сохранения необходимо быть внимательным с символом ω. Если маркировка имеет ω в качестве маркировки позиции p_i, тогда для того, чтобы сеть была сохраняющей, вес этой позиции должен быть равным 0. Напомним, что символ ω представляет бесконечное множество значений. Так как все веса неотрицательны, вес должен равняться либо нулю (тем самым означая, что число фишек в данной позиции не важно), либо быть положительным. Если вес положителен, то сумма будет разной для двух маркировок, различающихся в своей ω-компоненте. Следовательно, если какая-либо маркировка с ненулевым весом равна ω, сеть — несохраняющая.

Эти рассуждения относятся к сохранению по отношению к определенному взвешиванию. Сеть Петри является сохраняющей, если она сохраняющая по отношению к некоторому вектору w, w_i > 0. Дерево достижимости можно использовать для определения того, является сеть сохраняющей или нет, путем нахождения вектора весов w (если он существует). Заметим прежде всего, что для того, чтобы сеть Петри была сохраняющей по отношению к положительному вектору весов, она должна быть ограниченной. Как было указано выше, неограниченная позиция должна иметь нулевой вес, что недопустимо в сети с положительным вектором весов. Теперь, если сеть сохраняющая, существуют взвешенная сумма, обозначим ее s, и вектор весов w = (w₁, w₂,..., w_n). Для каждой маркировки μ [x] дерева достижимости имеем

w₁ ∙ μ [х]₁ + w₂ ∙ μ [х]₂ +... + w_n ∙ μ [x]_n = s.

Это равенство определяет для k вершин дерева достижимости совокупность из k линейных уравнений с n + 1 неизвестными. Добавим к ним ограничения: w_i> 0, i = 1,..., n, в результате чего определим ограничения для вектора весов.

Решение этой системы линейных уравнений — хорошо известная задача, имеющая множество алгоритмов решения. Можно рассматривать ее как задачу линейного программирования или просто как систему линейных уравнений. В любом случае, если решение существует, оно будет вычислено. Если ограничения, накладываемые на веса, являются чрезмерно жесткими и, следовательно, вектора взвешиваний не существуeт, это будет определено. В любом случае можно определить, является или нет сеть Петри сохраняющей, и если это так, получить вектор весов.

Покрываемость. Последняя задача, которую можно решить с помощью дерева достижимости, — задача покрываемости. В задаче покрываемости хотят для данной маркировки μ' определить, достижима ли маркировка μ" ³ μ'. Данная задача решается проверкой дерева достижимости. Строим для начальной маркировки μ дерево достижимости. Затем ищем любую вершину х с μ [х] ³ μ'. Если такой вершины не существует, маркировка μ' не покрывается никакой достижимой маркировкой; если она найдена, μ [x] дает достижимую маркировку, покрывающую μ'.

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

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

 

 

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

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

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

Рис. 1.16. Интерпретация перехода “исключающее ИЛИ” с помощью сдерживающих дуг

 

Имеются ещё два других важных расширений СП. Переходам могут быть поставлены в соответствие приоритеты так, что если 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⁺ функция времени задержки меток в позициях сети. Работа временных сетей подчиняется следующим правилам:

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

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

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

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

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

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

 

Список литературы

 

1. Котов В. Е. Сети Петри. – М.: Наука, 1984. – 158 с.

2. Леснин А. А. и др. Сети Петри в моделировании и управлении. – Л.: Наука, 1989.

– 133 с.

3. Питерсон Д. Теория сетей Петри и моделирование систем. – М.: Мир, 1984. – 264

с.

 

Содержание

 

1. Сети Петри

1.1 Основные определения

1.2 Сети Петри для моделирования

1.3 Анализ сетей Петри

1.3.1 Задачи анализа сетей Петри

1.3.2 Методы анализа

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