Preview

Труды Института системного программирования РАН

Расширенный поиск

Вычисление приоритетов срабатывания переходов для живых сетей Петри

https://doi.org/10.15514/ISPRAS-2019-31(4)-11

Полный текст:

Аннотация

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

Об авторе

Кирилл Геннадьевич Серебренников
Национальный исследовательский университет «Высшая школа экономики»
Россия


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

1. Lomazova I.A., Popova-Zeugmann L. Controlling Petri Net Behavior using Priorities for Transitions. Fundamenta Informaticae, vol. 143, no. 1-2, 2016, pp. 101-112..

2. Lomazova I.A., Popova-Zeugmann L., Bartels A. Controlling Boundedness for Live Petri Nets. In Proc. of the 4th International Conference on Control, Decision and Information Technologies, 2017, pp. 236-241.

3. Desel J. On Cyclic Behaviour of Unbounded Petri Nets. Application of Concurrency to System Design (ACSD). In Proc. of the 13th International Conference on Application of Concurrency to System Design, 2013, pp. 110-119.

4. Reisig W. Understanding Petri Nets. Springer-Verlag Berlin Heidelberg, 2013, 230 p.

5. Cormen T., Leiserson C., Rivest R., Stein C. Introduction to Algorithms. The MIT Press, 2009, 1312 p.

6. Goetz B., Peierls T., Bloch J., Bowbeer J., Holmes D., Lea D. Java Concurrency in Practice. Addison-Wesley Professional, 2006, 432 p.


Для цитирования:


Серебренников К.Г. Вычисление приоритетов срабатывания переходов для живых сетей Петри. Труды Института системного программирования РАН. 2019;31(4):163-174. https://doi.org/10.15514/ISPRAS-2019-31(4)-11

For citation:


Serebrennikov K.G. Computing Transition Priorities for Live Petri Nets. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2019;31(4):163-174. https://doi.org/10.15514/ISPRAS-2019-31(4)-11

Просмотров: 83


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2079-8156 (Print)
ISSN 2220-6426 (Online)