7.2. Расширения

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

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

задачи о приоритетном совместном использовании канала, которая сформулирована в [159], чтобы показать ограниченность сетей Петри.

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

Рис. 7.5. Расширенная сеть Петри со сдерживающей дугой.

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

7.2.1. Области ограничения

Области ограничения были предложены Патилом [231] для увеличения мощности моделирования сетей Петри. В контексте Патила области ограничения были только средством для того, чтобы сделать процесс моделирования проще, а не для того, чтобы увеличить мощность моделирования, поскольку все позиции в работе Патила были ограниченны. Однако определение областей ограничения не исчерпывается ограниченными сетями Петри, а для более общего класса сетей Петри верно, что они эквивалентны сетям Петри со сдерживающими дугами.

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

(кликните для просмотра скана)

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

Рис. 7.8. Преобразование перехода в переход-НАЧАЛО и переход-КОНЕЦ с позицией, представляющей запуск перехода.

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

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

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

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

Рис. 7.10. Преобразование переключателей в сети Петри со сдерживающими дугами.

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

7.2.2. Переходы исключающее ИЛИ и переключатели

Переход исключающее ИЛИ с входом требует, чтобы один и только один из его входов был не пустым, для того чтобы этот переход был разрешенным. Эта конструкция эквивалентна множеству переходов по одному для каждого элемента в Каждый переход имеет один (обычный) вход, а остальные входы являются сдерживающими дугами. На рис. 7.9 представлен пример. Переключатели также могут быть легко преобразованы в сдерживающие дуги. Это показано на рис. 7.10.

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

7.2.3. Другие расширения

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

запущен первым [115]. Во временных сетях Петри [194] каждому переходу сопоставляются два момента времени Переход может быть запущен, только если он был разрешен к моменту времени Если он является разрешенным, то должен быть запущен до наступления момента времени Оба этих расширения могут использоваться для проверки на нуль.

Рис. 7.11. Использование приоритетов для проверки позиций на нуль. Переход имеет по сравнению с более высокий приоритет.

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