• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Моделирование, анализ и улучшение качества процессов в информационных системах

Приоритетные направления развития: математика
2015

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

Используемые методы: Для разработки новых методов анализа процессов используются дискретная математика, математическая логика, теория алгоритмов, теория автоматов, абстрактные алгебры. Также в проекте используются и расширяются техники process mining (методы извлечения моделей процессов из журналов событий, проверки соответствия моделей процессов и журналов событий, усовершенствования моделей процессов с использованием дополнительной информации).

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

Результаты работы:

Следующие результаты были получены в области формального анализа информационных систем.

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

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

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

Следующие результаты были получены в области process mining (извлечение и анализ процессов).

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

Стандарт BPMN 2.0 (Business Process Model and Notation) широко используется и позволяет конструировать удобные и простые для восприятия модели процессов. В дополнение к простой перспективе потока управления BPMN-диаграмма может включать подпроцессы, потоки данных, ресурсы. В данном проекте были описаны и обоснованы робастные алгоритмы конвертации потока управления, обеспечивающие основу для более продвинутых методов извлечения и проверки соответствия с журналами события для BPMN-моделей. Более того, с целью адаптации существующих алгоритмов проверки соответствия и анализа производительности установлено соответствие между поведенческими свойствами сетей Петри и BPMN-моделей, что обеспечило возможность визуализации информации о соответствии и производительности на BPMN-диаграммах. Также предложены метрики для оценки BPMN-структур перед и после конвертации. Выявлены случаи, в которых алгоритмы конвертации производят более компактные или более запутанные BPMN-диаграммы.

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

Автоматическое сравнение бизнес-процессов играет важную роль в их анализе и оптимизации. Предложены новые техники сравнения процессов.

Предложен общий алгоритм сравнения, применимый к моделям бизнес-процессов в XML-представлении. Разработан инструмент, реализующий предложенный подход. Инструмент поддерживает стандарт BPMN 2.0, но может быть расширен для поддержки других стандартов моделирования.

Разработано веб-приложение BPMNDiffViz, предназначенное для поиска и визуализации различий в моделях бизнес-процессов. Для представления моделей был использован один из самых широко используемых стандартов BPMN 2.0. Инструмент реализует алгоритм A* в применении к структурному сравнению графов.

Предложен новый метод проверки соответствия модели процесса и журнала событий. Проверка соответствия – один из важнейших разделов process mining. Тем не менее, существовавшие ранее методы требовали от журналов событий и моделей одинаковой степени детализации. Представлен и обоснован новый метод проверки соответствия между абстрактной моделью (например, построенной экспертом) и низкоуровневым журналом событий (сгенерированным системой).

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

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

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

Степень внедрения, рекомендации по внедрению или итоги внедрения результатов НИР

Теоретические результаты, представленные в рамках данного проекта, реализованы и протестированы как расширения сред ProM, DPMine, а также в виде приложения Carassius. Большинство теоретических результатов могут служить основой для дальнейших исследований. В свою очередь прикладные результаты выявили некоторые интересные зависимости в реальных процессах, которые могут служить основой для дальнейших фундаментальных исследований.

Публикации по проекту:


Begicheva A., Lomazova I. A. Does your event log fit the high-level process model? // Моделирование и анализ информационных систем. 2015. Vol. 22. No. 3. P. 392-403. doi
I. S. Shugurov, A. A. Mitsyuk. Iskra: A Tool for Process Model Repair, in: Preliminary Proceedings of the 9th Spring/Summer Young Researchers' Colloquium on Software Engineering (SYRCoSE 2015) / Ed. by A. Kamkin, A. Petrenko, A. Terekhov. M. : , 2015. P. 137-143.
N. M. Nikitina, A. A. Mitsyuk. Carassius: A Simple Process Model Editor, in: Preliminary Proceedings of the 9th Spring/Summer Young Researchers' Colloquium on Software Engineering (SYRCoSE 2015) / Ed. by A. Kamkin, A. Petrenko, A. Terekhov. M. : , 2015. P. 129-136.
Ivanov S. Y., Kalenkova A. A. Comparing process models in the BPMN 2.0 XML format, in: Preliminary Proceedings of the 9th Spring/Summer Young Researchers' Colloquium on Software Engineering (SYRCoSE 2015) / Ed. by A. Kamkin, A. Petrenko, A. Terekhov. M. : , 2015. P. 144-148.
Sergey Andreevich Shershakov. VTMine Framework as Applied to Process Mining Modeling // International Journal of Computer and Communication Engineering. 2015. Vol. 4. No. 3. P. 166-179.
Zakharov V.A. Equivalence Checking Problem for Finite State Transducers // Lecture Notes in Computer Science. 2015. Vol. 9270. P. 208-221.
Ivanov S. Y., Kalenkova A. A., van der Aalst W. BPMNDiffViz: A Tool for BPMN Models Comparison, in: Proceedings of the BPM Demo Session 2015. Co-located with the 13th International Conference on Business Process Management (BPM 2015) Vol. 1418. Innsbruck : CEUR-WS.org, 2015. Ch. 8. P. 35-39.
Захаров В. А. Моделирование и анализ поведения последовательных реагирующих программ // Труды Института системного программирования РАН. 2015. Т. 27. № 2. С. 221-250.
Vladislav Podymov. An efficient equivalence-checking algorithm for a model of programs with commutative and absorptive statements, in: Concurrency, Specification & Programming. 24th International Workshop, CS&P 2015. Rzeszow, Poland, September 28-30, 2015. Proceedings Vol. 2. University of Rzeszow, 2015. P. 85-96.
Ivanov S. Y., Kalenkova A. A. Comparing process models in the BPMN 2.0 XML format // Proceedings of the Institute for System Programming of the RAS. 2015. Vol. 27. No. 3. P. 255-266.
Zakharov V., Подымов В. В., Алтухов В. С., Чемерицкий Е. В. VERMONT - a toolset for checking SDN packet forwarding policies on-line, in: Proceedings of 2014 International Science and Technology Conference "Modern Networking Technologies (MoNeTec): SDN&NFV Next Generation of Computational Infrastructure", Moscow, Russia, October 27-29, 2014. M. : Max press, 2014. P. 7-12.
Lomazova I. A., Popova-Zeugmann L. Controlling Petri Net Behavior Using Time Constraints, in: Concurrency, Specification & Programming. 24th International Workshop, CS&P 2015. Rzeszow, Poland, September 28-30, 2015. Proceedings Vol. 2. University of Rzeszow, 2015. P. 19-35.
N. Nikitina, A. Mitsyuk. Carassius: A Simple Process Model Editor // Proceedings of the Institute for System Programming of the RAS. 2015. Vol. 27. No. 3. P. 219-236. doi
Shershakov S. A., Rubin V. A. System Runs Analysis with Process Mining // Моделирование и анализ информационных систем. 2015. Vol. 22. No. 6. P. 818-833. doi
Захаров В. А., Подымов В. В. Применение алгоритмов проверки эквивалентности для оптимизации программ // Труды Института системного программирования РАН. 2015. Т. 27. № 4
van der Aalst W., Kalenkova A. A., Verbeek H., Rubin V. Process Discovery Using Localized Events, in: Application and Theory of Petri Nets and Concurrency. 36th International Conference, PETRI NETS 2015, Brussels, Belgium, June 21-26, 2015, Proceedings Issue 9115. Switzerland : Springer, 2015. P. 287-308.
I. Shugurov, A. Mitsyuk. Iskra: A Tool for Process Model Repair // Proceedings of the Institute for System Programming of the RAS. 2015. Vol. 27. No. 3. P. 237-254. doi