Подходы для решения задачи временной достижимости

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

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

Другой подход используется для рассмотрения самой ранней семантики срабатывания (переход срабатывает, как только это становится возможным). В данном случае можно приступить к подсчитывающему и структурному анализу [DAV 92]. Тем не менее, следует отметить, что ранняя семантика срабатывания не гарантирует оптимальность планирования.

Для примера рассмотрим временную сеть Петри на рисунке 5.8. После того как переходы /, и /4 срабатывают параллельно друг другу, самая ранняя операция затем пересекает переход t5, что приводит к последовательности срабатывания переходов cjj = 7, + 74^vl=0^, ^5(v2=i)? h + *6(v3=ll)’ *3(v4=l2)для Длительности 22 t.u. Однако оптимальная операция получается путем задержки срабатывания перехода /5 для получения последовательности ст2 = t{ + /4(vl=0), /2(v2=2)> h + *5(уЗ=3)> *6(у4=13) длительностью 14 t.u. Таким образом, для достижения оптимального плана необходимо решить конфликт между переходами t2 и t5 без соблюдения самой ранней стратегии срабатывания.

Временная сеть Петри и самая ранняя семантика срабатывания

Рисунок 5.8. Временная сеть Петри и самая ранняя семантика срабатывания

Семантика самого раннего срабатывания интенсивно изучалась для определенного класса синхронизированных графов событий с использованием алгебры (макс., +) [ВАС 92]. Поскольку структура сама по себе является бесконфликтной, можно получить линейные уравнения, соответствующие полному поведению системы, и обеспечить оптимальность самой ранней семантики срабатывания [С HR 84b].

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

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