Computing transition priorities for live Petri nets

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