Проблемы достижимости во временных сетях Петри

Учитывая вышеуказанное, проблема достижимости в синхронизированных сетях Петри заключается в нахождении осуществимого контролирования операций для перехода от начального состояния тц, erq) на дату vQ к конечному состоянию (emf, е^) на дату ту.

Как уже упоминалось во введении, очень просто провести параллель между задачей календарного планирования и задачей достижимости временной сети Петри. Для примера рассмотрим сеть Петри на рисунке 5.6. На нем видно, что задача достижимости между маркировками

и

Моделирование продуктивности временных сетей Петри в таблице 5.1

Рисунок 5.6. Моделирование продуктивности временных сетей Петри в таблице 5.1

является аналогичной задаче планирования, приведенной в таблице 5.1.

Моделирование железнодорожного узла при помощи сетей Петри

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

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

Моделирование железнодорожного узла временной сети Петри в таблице 5.2

Рисунок 5.7. Моделирование железнодорожного узла временной сети Петри в таблице 5.2

Данный пример демонстрирует классическое явление, которое увеличивает сложность проводимых исследований: существование «мертвых маркировок» в достижимых состояниях сети Петри соответствует системным тупикам, возникающим за счет потребления общих ресурсов в частном порядке. Например, если рассматривать срабатывание переходов /1? t2, Ц и /8, то в данном случае будут использоваться все ресурсы, связанные с блоками. Система блокируется потому, что для возвращения ресурсов контролирующие переходы /3 и Ц должны сначала иметь дополнительный ресурс.

Данный вид вопроса не рассматривает «причину» комбинаторного взрыва (стремительного роста числа вариантов при переборе), а является фактором, который ограничивает применение некоторых алгоритмов анализа, например, тех, которые вызывают множественные ложные решения. Это особенно негативно сказывается на методах, основанных на построении и пересечении достижимости графа, который может возникнуть позднее в последовательности выполнения сети. Данное явление имеет особенно сильные ограничения для классических алгоритмов планирования [DAM 99].

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >