автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Задачи моделирования потоков работ при помощи сетей Петри

На правах рукописи

ТОЛСТОЕ ЕВГЕНИЙ ВИКТОРОВИЧ

ЗАДАЧИ МОДЕЛИРОВАНИЯ ПОТОКОВ РАБОТ ПРИ ПОМОЩИ СЕТЕЙ ПЕТРИ

Специальность 05.13.18 - математическое моделирование, численные методы и комплексы

программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Москва-2006

Работа выполнена на кафедре математических основ управления Московского физико-технического института (государственного университета)

Научный руководитель:

Ведущая организация:

Институт прикладной математики им. М.В. Келдыша РАН

Защита состоится « 77- » о&цир? 2006 года в // 20 час. на заседании диссертационного совета К212.156.02 в Московском физико-техническом институте по адресу: 141700, г. Долгопрудный Московской обл., Институтский пер., д. 9.

С диссертацией можно ознакомиться в библиотеке МФТИ.

Автореферат разослан « ¿Г"» сентября 2006 г.

доктор физ.-мат. наук, профессор, член-корреспондент РАН Флёров Юрий Арсениевич

Официальные оппоненты:

доктор физ.-мат. наук, профессор Белолипецкий Александр Алексеевич

доктор физ.-мат. наук, профессор Столяров Лев Николаевич

Ученый секретарь диссертационного совета

Федько О.С.

US S3

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы

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

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

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

РОС. НАЦИОНАЛЬНАЯ 3 БИБЛИОТЕКА

С.-Петербург

ОЭ 2о4акт/-60

и содержит большое количество нерешенных или решенных не полностью задач.

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

Цель работы

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

В работе исследованы и решены следующие задачи:

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

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

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

4. Разработана эффективная система управления потоков работ с использованием сетей Петри в качестве модели определения схем потоков работ и механизма их исполнения.

Научная новизна

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

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

2. Создана возможность описывать и реализовывать в понятиях модели большинство шаблонов потоков работ (всех, за исключением тех, которые нецелесообразно использовать, чтобы исключить ошибки проектирования). Это обеспечивает высокую выразительную мощность языка моделирования потока работ.

3. Предложен подход для формализации процессов, представленных в распространенном стандарте ЮЕРО.

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

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

2. Позволяет во многих случаях локализовать точку графа, в которой находится структурный конфликт, и, следовательно, быстро его устранить.

3. Алгоритм способен анализировать графы, содержащие простые циклы. Известные решения работают лишь с ацикличными графами.

Практическая ценность

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

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

Апробация работы

Основные результаты работы докладывались и обсуждались на научных конференциях МФТИ (Долгопрудный, 2003, 2004, 2005), научных семинарах кафедры математических основ управления МФТИ и Центра сетевых образовательных технологий и систем МФТИ, научном семинаре Вычислительного Центра РАН, на X Всероссийской научно-методической конференции «Телематика-2003».

Публикации

По теме диссертации опубликовано 11 печатных работ. Структура н объем работы

Диссертация состоит из введения, четырех глав, заключения, списка использованных источников, двух приложений, содержит 52 иллюстрации.

СОДЕРЖАНИЕ РАБОТЫ

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

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

ния потоками работ. Этот документ предложен международной коалицией Workflow Management Coalition, занимающейся разработкой стандартов в этой области. Большинство существующих систем имеют архитектуру, удовлетворяющую этому стандарту. Эталонная модель определяет какие компоненты и интерфейсы должна иметь типичная система (рис. 1). _

Инструменты администировани я и мониторинга

Инструменты определения процессов

Интерфейс 1

Интерфейс 4

Workflow API и форматы обмена

Сервис потоков работ потоков работ

Другие сервисы исполнения

J ;л л .]

"Мехвнкзм(Ы) , J дето ков м>бот'|

Интерфейс 2

Интерфейс 3

Клиентские приложения потоков работ

Вызываемые приложения

Рис. 1. Эталонная модель Также, в главе 1 затронуты проблемы моделирования структуры потоков работ. Рассмотрены существующие подходы к моделированию, описываются их преимущества и недостатки. Одной из наиболее подходящих моделей является модель сетей потоков работ (\vorkflow-nets), которая основана на классической теории сетей Петри. Формализм сетей Петри отлично подходит для этой задачи. Приводятся очевидные преимущества этой модели перед другими:

• Сети Петри - формальная математическая модель, которая в то же время имеет удобное графическое представление,

• Сети Петри предлагают огромное количество наработанных методов анализа и исследования (более 45 лет исследований в данной области),

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

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

типичных конструкций бизнес-процессов - шаблонов потоков работ.

Всего было выделено 20 шаблонов потоков работ, которые делятся на несколько групп: базовые шаблоны маршрутизации, расширенные шаблоны маршрутизации, структурные шаблоны, шаблоны с множественными экземплярами, шаблоны состояния и шаблоны отмены.

Приведена сравнительная таблица пятнадцати распространенных коммерческих и бесплатных продуктов управления потоками работ. Даже такой серьезный продукт, как система управления потоками работ и автоматизации бизнес-процессов БАР/КЗ включает в себя поддержку только десяти шаблонов и один шаблон поддерживается не полностью. Дополнительно рассмотрены стандартные языки композиции \уеЬ-сервисов, которые используются для построения распределенных потоков работ и координации бизнес-процессов между несколькими системами. Приведено сравнение выра-^ зительной мощности пяти таких языков, и показано, что даже

самый «выразительный» из них - язык ВРЕЬ^^Б поддерживает лишь 13 шаблонов.

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

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

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

В главе 2 приводен подробный каталог всех шаблонов потоков. При моделировании процесса потоков работ сетями Петри активность в процессе моделируется переходом. Текущее состояние процесса моделируется состоянием сети Петри (множество позиций, содержащих метки). Для иллюстраций использована следующая нотация: темным переходом моделируется реальная активность (за выполнение такой активности отвечает какой-либо ресурс в процессе - человек или устройство), светлым переходом отмечен искусственный переход, который используется во вспомогательных целях и срабатывает автоматически, когда становится активным (enabled) - без участия ресурса.

Для демонстрации реализации наиболее сложных шаблонов, рассмотрим, например, шаблон 14 «Множественные экземпляры с априорным знанием во время выполнения». Из

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

Трудность заключается в невозможности определить количество экземпляров данной активности в момент разработки -это число становится известным лишь в момент выполнения. Рис. 2 демонстрирует реализацию шаблоны при помощи сетей Петри.

Рис. 2. Множественные экземпляры с априорным знанием во время выполнения Активность, которая должна быть выполнена несколько раз, обозначена переходом А. Переход В является конструкцией

типа AND-paзвeтвлeния. После его выполнения одна метка попадает в позицию рз другая вновь в р|. В позиции рз будет происходить «накопление» меток. Ни переход Э, ни переход Е не сработают, пока пуста позиция р4. В позиции р] происходит проверка условия - совпал ли счетчик выполнений перехода А с заданным количеством. Как только это условие становится выполнимым, срабатывает переход С. Тем самым становится активными переходы Б и Е, но у перехода Е меньший приоритет (он будет срабатывать только, когда не будет возможности сработать переходу Б). После каждого срабатывания перехода Т) количество меток в позиции рз будет уменьшаться на одну, пока их количество не уменьшится до одной. После этого сработает переход Е, который является следующей выполняемой активностью после активности А.

В главе 3 рассмотрена задача поиска структурных конфликтов в графах потоков работ. Приведена формальная постановка задачи.

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

Разветвители и синхронизаторы используются для построения параллельных конструкций. Разветвитель порождает несколько параллельных потоков выполнения из одного потока, а синхронизатор объединяет их в один поток (выполняя синхронизацию). Координатор выбора используется для определения альтернативного выбора - новые потоки при этом не порождаются.

Обычно задача рассматривается на подмножестве графов потоков работ - непротиворечивых графах. Эти графы являются ацикличными и каждая его вершина лежит на каком-либо. Далее определяются экземплярные подграфы - подграфы графа потоков работ, которые содержат задачи и переходы конкретного экземпляра потока работ.

На рис. 3 показаны примеры графа потоков работ и его эк-земплярных подграфов.

Рис. 3. Граф потоков работ и его экземплярные подграфы

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

1. Отсутствие тупиков: граф потоков работ не содержит структурного конфликта типа тупик, если он не порождает экземплярного подграфа, который содержит собственное подмножество входящих переходов для узлов типа И-соединения (т.е. синхронизатора).

2. Отсутствие недостатков синхронизации: граф потоков работ не содержит структурного конфликта типа недостаток синхронизации, если он не порождает экземплярного подграфа, который содержит более одного входящего перехода для узлов типа исключающее ИЛИ-соединение (т.е. координатор слияния).

На рис. 4 приведены примеры структурных конфликтов: ту-

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

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

1. При последовательном выполнении кратности входящего и исходящего перехода совпадают.

2. В разветвителе кратности входящего и каждого исходящего перехода совпадают.

3. В синхронизаторе кратности исходящего и каждого входящего перехода совпадают.

4. В координаторе выбора с е С, таком что с| = 1 и

|с*|>1, кратность входящего перехода равна сумме кратностей исходящих переходов.

5. В координаторе слияния се С, таком что |*с|>1 и

\с в| = 1, кратность исходящего перехода равна сумме

кратностей исходящего перехода. Здесь используются обозначения: «с - множество входящих переходов в синхронизатор с, с* - множество исходящих переходов. Символ \А\ обозначает количество элементов множества А.

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

15

Приведено доказательство полноты и корректности. Доказана теорема: если граф не содержит структурных конфликтов, то алгоритм завершается на последнем этапе. Это утверждение следует из построения алгоритма. Обратная теорема утверждает, что если алгоритм завершается на последнем этапе, то граф не содержит структурных конфликтов. Далее приводится оценка сложности алгоритма. В худшем случае один обход модифицированным методом поиска в ширину занимает 0(\У\2), где - количество вершин в графе. Производится четыре обхода таким способом, в некоторых узлах производится до дополнительных операций, таким образом, общая сложность работы составляет 0(\У]3). Алгоритм редукции в худшем случае работает за время 0(|V}6), а алгоритм петрификации за 0(\У\4). Таким образом, новый алгоритм, основанный на экземплярном подходе, в самом худшем случае работает не медленнее, чем существующие алгоритмы, в других же ситуациях он обладает производительностью не менее на порядок более высокой, чем известные алгоритмы.

В заключение главы рассмотрен случай графа с простыми циклами. Для этого при помощи алгоритма поиска в глубину производится поиск обратных ребер и затем производится их классификация. На рис. 5 представлены четыре возможных вида обратных ребер.

Рис. 5 Виды обратных ребер 16

Показано, что лишь последний вариант обратного ребра не порождает структурного конфликта.

В главе 4 описана архитектура и реализация модуля управления потоками работ, разработанного в рамках платформы Competentum, предназначенной для построения корпоративных информационных систем.

В начале главы описана общая архитектура самой платформы Competentum, построенной с использованием технологии Java 2 Enterprise Edition. Описание включает в себя уровень серверного представления, уровень бизнес логики и уровень бизнес объектов.

Далее описана общая архитектура модуля управления потоками работ (рис. 6) и каждый блок более подробно.

Обработчик списка _ работ

Организационная

Модель (структура и роли)

Ш

База данных Competentum XML База данных

Рис. 6. Архитектура модуля потоков работ

Схема процесса задается при помощи специального языка описания схем в формате XML (XML-схема этого формата приведена в Приложении 1).

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

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

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

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

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

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

Блок обработчика списка работ выполняет для каждого пользователя поиск процессов, которые находятся в состоянии, за которое отвечает данный пользователь (интерфейс 2 эталонной модели). Информация о списке работ доступна пользователям через стандартный интерфейс, реализованный в Сотре1епШт. Этот интерфейс может меняться в зависимости от предназначения и требований конкретной системы, но стандартно он представляет собой схожий с почтовыми программами интерфейс (папки с входящими, исходящими и контролируемыми процессами).

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

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

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

1. Система Protrac для компании «Thomson Learning» (США). Эта система предназначена для отслеживания состояний работ над элементами продуктов, выпускаемых в дополнении к печатным учебникам.

2. Система РМ Tool для компании «Pearson Education» (США). Назначение этой системы также заключается в управлении процессом разработки иллюстраций и интерактивных моделей для крупнейшего американского издателя учебной литературы.

3. Система консолидации финансовой отчетности для компании «ГЕК» (Россия). Модуль потоков работ используется для автоматизации процессов обработки отчетов.

4. Корпоративная информационная система для мебельной компании «А&А» (Россия). Модуль потоков работ используется для управления процессами подписания контрактов.

5. Автоматизация бизнес-процессов компании «ФИЗИКОН» в рамках сертификации на соответствие стандарту ISO 9001:2000. Модуль потоков работ используется для формализации неформальных описаний процессов в формате IDEF0 и их автоматизации.

В заключении приведены основные результаты диссертационной работы.

Основные результаты работы:

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

мым значительно увеличить выразительную мощность языка, построенного на основе сетей Петри.

2. Разработан быстрый и эффективный алгоритм поиска структурных конфликтов в графах потоков работ. Приведено доказательство корректности и полноты этого алгоритма, a faraKe анализ его сложности.

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

4. Разработан комплекс программ для реализации различных конфигураций потоков работ. Данный модуль интегрирован в платформу для разработки корпоративных информационных систем компании Competentum компании «ФИЗИКОН» и включает в себя все основные составляющие систем управления потоками работ, согласно эталонной модели подобных систем. Более того, процессная составляющая содержит в себе модель, построенную на основе сетей Петри.

5. Предложена программная реализация моделирования схем потоков работ и их анализа.

6. Разработан механизм формализации бизнес-процессов, заданных при помощи стандарта IDEF0.

По теме диссертации опубликованы следующие работы:

1. Е. В. Толстов. Хранение XML документов в базах данных. //Современные проблемы фундаментальных и прикладных наук. Часть VII. Прикладная математика и экономика: Труды XLVI научной конференции. /Моск. физ. - техн. ин-т. - М. - Долгопрудный, 2003. - С. 6061.

2. Д. Мамонтов, Д. Береснев, Е. Толстов. Интерактивное средство построения графиков //Телематика'2003. -СПб: 2003.-С. 331.

3. Е.В. Толстов. Использование объектно-реляционного отображения для связи DTD с базами данных. // Моделирование процессов управления: сб.ст./Моск.физ.-тех. ин-т. - М., 2004. - С. 109-115.

4. Е.В. Толстов. Системы управления технологическим потоком. //Современные проблемы фундаментальных и прикладных наук. Часть VII. Прикладная математика и экономика: Труды XLVII научной конференции. /Моск. физ. - техн. ин-т. - М. - Долгопрудный, 2004. -С. 102-103.

5. Е.В. Толстов. Анализ графов потоков управления работами при помощи сетей Петри. //Процессы и методы обработки информации: Сб.ст./Моск.физ.-тех. ин-т. -М., 2005.-С. 15-21.

6. Е.В. Толстов. Новый алгоритм поиска структурных ошибок в непротиворечивых графах потоков работ. //Современные проблемы фундаментальных и прикладных наук. Часть VII. Прикладная математика и экономика: Труды XLVIII научной конференции. /Моск. физ. - техн. ин-т. - М. - Долгопрудный, 2005. -С.86-87.

7. Е. В. Толстов, Ю.А. Флеров. Экземплярный подход в задаче поиска структурных конфликтов в графах потоков работ. Препринт / ВЦ РАН. - М„ 2006. - 36 с.

8. Е.В. Толстов. Реализация шаблонов потоков работ сетями Петри. Электронный журнал «Исследовано в России», 9,521-529,2006. http://zhurnal.ape.relarn.ru/articles/2006/052.pdf.

9. Е.В. Толстов. Использование сетей петри для моделирования графов потоков работ. // Процессы и методы обработки информации: Сб.ст./Моск.физ.-тех. ин-т. -М., 2006.-С. 38-44.

10. Толстов Е.В. Моделирование структурной перспективы в системах управления бизнес-процессами. // Сис-

темы управления и информационные технологии, 2006, №1.1(23), С. 191-195.

Толстов Е.В. Моделирование шаблонов бизнес-процессов сетями Петри. //Информационные технологии моделирования и управления, 2006, №4(29), С. 462-470.

дообА

Толстое Евгений Викторович

ЗАДАЧИ МОДЕЛИРОВАНИЯ ПОТОКОВ РАБОТ ПРИ ПОМОЩИ

СЕТЕЙ ПЕТРИ

Подписано в печать 15.09.06. Формат 60 * 84 '/j6. Печать офсетная. Усл. печ. л. 1,0. Уч.-изд. л. 1,0. Тираж 70 экз. Заказ № ф-141

Государственное образовательное учреждение высшего профессионального образования Московский физико-технический институт (государственный университет) Отдел автоматизированных издательских систем "ФИЗТЕХ-ПОЛИГРАФ" 141700, Московская обл., г. Долгопрудный, Институтский пер., 9

Введение.

Решаемые проблемы.

Работы на данную тематику.

Используемые термины.

Содержание работы.

Глава 1.Опыт разработки систем управления потоками работ в других организациях.

1.1 Тенденции в развитии информационных систем.

1.2 Эволюция систем управления потоками работ.

1.2.1 Технология офисной автоматизации.

1.2.2 Системы управления документами.

1.2.3 Электронная почта.

1.2.4 Управление базами данных.

1.3 Эталонная модель архитектуры системы управления потоками работ.

1.3.1 Определения.

1 1.3.2 Модель реализации продукта.

1.3.3 Описание эталонной модели.

1.4 Способы моделирования потоков работ.

1.5 Сети Петри - краткое напоминание.

Глава 2.Структурные шаблоны в сетях потоков работ.

2.1 Введение.

2.2 Шаблоны потоков работ в коммерческих продуктах.

2.3 Применение сетей Петри для моделирования шаблонов.

2.4 Каталог шаблонов.

2.4.1 Шаблон 1. Последовательность (последовательная маршрутизация).

2.4.2 Шаблон 2. Параллельное расщепление (разветвитель, параллельная маршрутизация, И-расщепление).

2.4.3 Шаблон 3. Синхронизация (И-объединение, рандеву, синхронизатор).

2.4.4 Шаблон 4. Эксклюзивный выбор (XOR-расщепление, условная маршрутизация, выбор, решение).

2.4.5 Шаблон 5. Простое соединение (XOR-объединение, асинхронное объединение, соединение).

2.4.6 Шаблон 6. Множественный выбор (условная маршрутизация, ИЛИ-выбор).

2.4.7 Шаблон 7. Синхронизирующее соединение.

2.4.8 Шаблон 8. Множественное соединение.

2.4.9 Шаблон 9. Дискриминатор.

2.4.10 Шаблон 10. Произвольные циклы (петли, итерация, цикл).

2.4.11 Шаблон 11. Явное завершение.

2.4.12 Шаблон 12. Множественные экземпляры без синхронизации.

2.4.13 Шаблон 13. Множественные экземпляры с априорным знанием во время разработки.

2.4.14 Шаблон 14. Множественные экземпляры с априорным знанием во время выполнения.

2.4.15 Шаблон 15. Множественные экземпляры без априорного знания во время выполнения.

2.4.16 Шаблон 16. Отложенный выбор (внешний выбор, неявный выбор).

2.4.17 Шаблон 17. Чередующаяся параллельная маршрутизация (неупорядоченное выполнение).

2.4.18 Шаблон 18. Веха (этап, тестовая дуга, условное состояние, предельный срок)

2.4.19 Шаблон 19. Отмена активности.

2.4.20 Шаблон 20. Отмена экземпляра.

2.5 Выводы.

Глава 3.Поиск структурных конфликтов в графах потоков работ.

3.1 Введение.

3.2 Постановка задачи.

3.3 Известные решения.

3.4 Экземплярный подход.

3.5 Доказательство корректности и полноты.

3.6 Анализ сложности.

3.7 Случай с простыми циклами.

Глава 4.Архитектура и описание реализации модуля управления потоками работ в платформе Competentum.

4.1 Общая архитектура платформы Competentum.

4.1.1 Уровень серверного представления и библиотека Maverick.

4.1.2 Уровень бизнес-логики.

4.1.3 Уровень бизнес-объектов.

4.2 Архитектура модуля потоков работ.

4.2.1 Общее описание.

4.2.2 Объектная модель схемы процесса.

4.2.3 Ролевая модель и организационная структура.

4.2.4 Иптерпретатор схем.

4.2.5 Данные процесса: пространства и измерения.

4.2.6 Модель экземпляра процесса.

4.2.7 Подсистема действий потоков работ.

4.2.8 Блок выполнения экземпляров процесса.

4.3 Пользовательский интерфейс.

4.3.1 Интерфейс администратора.

4.3.2 Обработчик списка работ - папка «Входящие».

4.3.3 Обработка задания.

4.3.4 Визуальный редактор.

4.4 Практическое применение модуля потоков работ.

4.4.1 Система Protrac для компании Thomson Learning (США).

4.4.2 Система РМ Tool для компании Pearson Education (США).

4.4.3 Система консолидации финансовой отчетности для компании

ГЕК (Россия).

4.4.4 Корпоративная информационная система для мебельной компании

А&А (Россия).

4.4.5 Автоматизация бизнес процессов компании ФИЗИКОН в рамках сертификации на соответствие стандарту ISO 9001:2000.

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

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

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

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

Выходом из этой ситуации может служить активно развивающаяся технология workflow (WF) или технология потоков работ. Она зародилась еще во времена отсутствия информационных систем. На бумаге рисовались схемы производственных процессов и фиксировались этапы выполнения. Одно время проводились активные исследования в этой области. Затем интерес к технологии потоков работ заметно ослаб. В полную силу она начала развиваться в связи со стремительным ростом информационных распределенных систем, развитием вычислительных глобальных сетей. Одно из определений термина workflow, данное в одной из первых работ по данной тематике [GHS95] следующее: «набор заданий, организованных таким образом, чтобы выполнить определенный бизнес-процесс».

Workflow Management Coalition (WfMC), международная организация по стандартизации технологии потоков работ дает следующее определение термину workflow [WMFC]: «workflow - это автоматизация бизнес-процесса, полностью или частично, во время которой документы, информация или задания переходят от одного участника к другому, в соответствии с набором процедурных правил».

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

За последние десять лет на свет появилось очень большое количество систем управления потоками работ (Workflow Management Systems - WfM системы). Это свидетельствует о высокой потребности в таких системах, позволяющих моделировать, координировать бизнес-процессы, а также управлять потоками информации или документов и последовательной обработкой частей документов, таких как изображения. Совсем недавно появилась новая и ставшая уже популярной парадигма построения распределенных информационных систем СОА (сервисно-ориентированная архитектура). Она позволяет интегрировать множество распределенных систем посредством web-служб. Для организации сложных взаимодействий между системами применяются системы автоматизации потоков работ. Поток работ в данном случае распределяется между несколькими системами.

Системы управления потоками работ обычно реализованы в виде отдельного решения для автоматизации именно бизнес-процессов, но также они могут быть представлены в виде отдельных подключаемых библиотек для того, чтобы разработчики могли включать эти модули в свои системы и задавать процессы описательным путем. Многие технологические платформы, которые служат для автоматизации деятельности предприятия и интеграции всех аспектов его работы в одно информационное пространство, дополнились таким модулем. Этот модуль становится неотъемлемой частью любой подобной системы.

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

Решаемые проблемы

Спецификации потоков работ можно рассматривать в широком смысле в нескольких перспективах [JB96]:

• перспектива потока управления или структурная перспектива (control-flow perspective);

• перспектива данных (data perspective);

• перспектива ресурсов (resource perspective);

• операционная перспектива (operational perspective).

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

Операционная перспектива описывает элементарные действия, которые производятся во время выполнения задания и их взаимосвязь с приложением, осуществляющим управление выполнением процесса.

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

Один из вопросов, который остается открытым до сих пор, это выбор метода моделирования структуры процесса. Существует огромное количество формальных и неформальных нотаций, предназначенных для этого (IDEF, ISAC, UML, диаграммы состояний, и т.д.). Во многих коммерческих продуктах предложен свой собственный метод моделирования. Между тем, существуют весьма конкретные требования к модели описания процессов, такие как легкость изучения и использования, формальность, большая выразительная мощность. В этой работе будет рассмотрена система управления потоками работ, основанная на высокоуровневых сетях Петри. Этот формализм в последнее время завоевывает все большую популярность в среде разработчиков систем управления потоками работ (к сожалению, пока только в научных кругах). С появлением большого количества методов моделирования потоков работ и языков их описания [XRL],[SMAWL],[XPDL],[Wf-XML] встает вопрос о сравнении этих языков между собой. Даже без формального определения особенности разных языков описания схем потоков работ указывают на фундаментально разную семантику. Например, некоторые языки позволяют структурировать циклы только с одной входящей и одной исходящей активностью, в то время как в других можно задавать произвольные циклы. Такие различия указывают на различные уровни выразительной мощности языков. Одно из определений выразительной мощности языка, дается при помощи шаблонов потоков работ [АНКВООа] - часто встречающихся структурных блоков в схемах потоков работ. Язык является более выразительным, если он поддерживает реализацию большего числа шаблонов. В этой работе подробно рассматривается возможность реализации шаблонов потоков работ при помощи сетей Петри.

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

Все указанные проблемы рассматриваются в рамках практической реализации системы управления потоками работ, входящей в состав технологической платформы Competentum [Competentum], которая является инструментальным средством создания корпоративных информационных систем. Эта платформа разработана компанией ФИЗИКОН и апробирована во многих коммерческих внедрениях.

Работы на данную тематику

За последние десять лет появилось большое количество научных работ, касающихся проблем в области разработки систем управления потоками работ. Огромный вклад в развитие технологии потоков работ и основных принципов реализации разных аспектов систем управления потоками работ внес голландский ученый Вил ван дер Аальст, профессор отдела Информационных Технологий на Факультете Технологического Управления в технологическом университете Эйндховена, Нидерланды. Он также занимает должность профессора в группе управления бизнес-процессами на Факультете Информационных технологий в Квинслендском Технологическом университете в Австралии.

Ван дер Аальст возглавляет подгруппу управления бизнес-процессами (ВРМ subgroup), основными направлениями которой является моделирование и анализ операционных бизнес-процессов [Aalst]. Он опубликовал огромное количество работ (более двухсот) на такие темы как информационные системы, управление потоками работ, сети Петри, исследование процессов (process mining) и языки спецификаций.

Он одним из первых [АНН94], [Аа195], [Аа196а] осознал преимущества моделирования систем управления бизнес-процессами при помощи высокоуровневых сетей Петри. Долгое время занимаясь сетями Петри, профессор ван дер Аальст начал применять наработки в этой области для моделирования и анализа потоков работ. В работе [Аа196Ь] показывается какими преимуществами обладают системы, построенные на основе этого формализма.

Многие работы в начале этого десятилетия были посвящены анализу процессов, так называемой верификации процессов на предмет наличия в них различных конфликтов. Было предложено немало подходов [SOOO], [LZLC02],[АНV02], основанных как на классической теории графов, так и на известных исследованиях в области сетей Петри. Другое направление исследований проводилось ван дер Аальстом совместно с польским исследователем Бартеком Кейпужевским (Bartek Kiepuszewski) и было нацелено на сравнение огромного количества появившихся языков и подходов к моделированию потоков работ. В результате было дано определение выразительной мощности языка моделирования при помощи шаблонов потоков работ [АНКВООа] ,[АНКВ00Ь],[АН02]. В настоящий момент группой управления бизнес-процессами проводится работа в области исследования сути процессов (process mining) [AW04],[MDAW04],[GA05]. Эта задача относится к инженерному анализу процесса. Во время выполнения бизнес-процесса (вне системы управления бизнес-процессами, а в рамках простой работы в информационной системе), после каждого действия пользователя производится запись о действиях пользователя в журнал потока работ (workflow log). После этого проводится анализ данного журнала и построение по нему схемы процесса с целью его дальнейшей автоматизации в системе управления. Данная тема очень интересна с практической точки зрения, так как в реальности процессы обычно выполняются вне контекста системы управления процессами, и корректное моделирование процесса может быть достаточно сложным.

Используемые термины

В русскоязычной литературе терминология управления потоками работ встречается не часто, поэтому употребление многих терминов еще не устоялось. В частности, термин xvortyow в технических статьях обычно не переводится, и употребляется в английском написании. Наряду с этим используется сокращение WF. Если перевод все же встречается, то он обозначается как «бизнес-процесс». На наш взгляд, наиболее подходящее выражение - это поток работ, так как эта технология может применяться и в областях, которые не сопряжены с выполнением каких либо бизнес-процессов. Например, процесс тестирования студента в системах электронного обучения. Также, слово бизнес может внести некую неопределенность, так как часто под этим подразумевается некий результат некой экономической деятельности, a workflow в основном относится к координации работ, а не к их непосредственному выполнению связанных с ними бизнес-целями и другой финансовой составляющей бизнес-процесса. В нашей работе будет использован термин «поток работ», но также иногда и «бизнес-процесс». Там где это не оговорено отдельно, эти фразы означают одно и тоже - английский термин workflow. Дополнительно о терминологии, касающейся термина workflow будет сказано в разделе, посвященному эталонной модели (раздел 1.3).

В России системы управления потоками работ распространены не так широко, как системы управления потоками документов (DocFlow Management Systems), называемые также системами электронного документооборота. Поэтому часто по ошибке термин workflow переводят как документооборот. Следует понимать различия этим систем.

Системы электронного документооборота являются наследниками бумажного документооборота. Отсюда и их естественные ограничения: с документом можно совершить ограниченный набор действий: одобрить/отказать, визировать, удалить, внести правку и т. п. Обычно системы документооборота дополняются системами хранения образов бумажных документов и системами контроля версий. Основным преимуществом систем документооборота является возможность их быстрого внедрения на предприятии, если там уже на хорошем уровне налажен документооборот.

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

Что касается термина workflow patterns, то термин pattern часто переводится как паттерн. Соответственно, в русскоязычных работах на эту тему, можно увидеть термин WF паттерны или workflow паттерны. В этой работе будет использован термин шаблон потока работ, так как на наш взгляд он лучше всех других отражает суть термина. Труднопереводимым также является термин, которым обозначают целое направление в области потоков работ - process mining. Этим термином обозначают метод анализа процесса с целью его более детального изучения и построения формальной спецификации процесса по результатам выполнений экземпляров этого процесса. Мы будем использовать термин исследование процесса.

Содержание работы

Работа состоит из пяти глав. В главе 1 приводится исторический обзор развития систем управления потоками работ, как они зарождались и развивались [Толс04Ь]. Также приведено описание эталонной модели таких систем, данное международной коалицией Workflow Management Coalition. В заключение главы приводится обзор подходов и языков, применяемых для моделирования процессов и потоков работ в существующих системах. Показана роль высокоуровневых сетей Петри.

Глава 2 посвящена описанию реализации шаблонов потоков работ при помощи сетей Петри [Толс06Ь],[Толс06е], так как это делается в модуле управления процессами платформы Competentum. Результаты этой главы могут быть использованы в других системах, базирующихся на высокоуровневых сетях Петри. В начале главы приводится сравнение наиболее известных систем и стандартов с точки зрения выразительной мощности их языков моделирования.

Глава 3 посвящена проблемам верификации графов потоков работ [Толс05а]. В частности, описывается новый эффективный алгоритм [Толс05Ь],[Толс06а], позволяющий проводить такой анализ. В главе приводится подробное доказательство и анализ сложности алгоритма.

В главе 4 детально описывается реализация модуля потоков работ в рамках платформы Competentum. Дается описание структурной перспективы, ресурсной перспективы и перспективы данных. Описывается язык моделирования, дается архитектурное описание модуля. Также описываются вспомогательные инструменты, такие как визуальный редактор задания схем, интерфейсы пользователя. В заключение, приводятся описания коммерческих внедрений модуля управления потоками работ. Описываются различные системы, разработанные и внедренные как для американских, так и для русских компаний.

Заключение.

В работе получены следующие основные результаты:

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

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

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

4. Разработан программный модуль исполнения потоков работ. Данный модуль интегрирован в платформу для разработки корпоративных информационных систем Competentum компании ФИЗИКОН и включает в себя все основные составляющие систем управления потоками работ, согласно эталонной модели подобных систем. Более того, процессная составляющая содержит в себе модель, построенную на основе сетей Петри.

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

6. Разработан механизм формализации бизнес-процессов, заданных при помощи неформальной нотации IDEF0.

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

1. Aal95. W.M.P. van der Aalst. A class of Petri net for modeling and analyzing business processes. Computing Science Reports 95/26, Eindhoven University of Technology, Eindhoven, 1995.

2. Aal96a. W.M.P. van der Aalst. Petri-net-based Workflow Management Software. In A. Sheth, editor, Proceedings of the NFS Workshop on Workflow and Process Automation in Information Systems, pages 114-118, Athens, Georgia, May 1996.

3. Aal98. W.M.P. van der Aalst. The Application of Petri Nets to Workflow Management. The Journal of Circuits, Systems and Computers, 8(l):21-66,1998.

4. Aalst. Wil van del Aalst research page, http://is.tm.tue.nl/staff/wvdaalst/.

5. AH02a. W.M.P. van der Aalst and K.M. van Нее. Workflow Management: Models, Methods, and Systems. MIT press, Cambridge, MA 2002.

6. AH02c. W.M.P. van der Aalst and A.H.M. ter Hofstede. YAWL: Yet Another Workflow Language. QUT Technical report, FIT-TR-2002-06, Queensland University of Technology, Brisbane, 2002.

7. AW04. W.M.P. van der Aalst and A.J.M.M. Weijters. Process Mining: A Research Agenda.

8. Computers in Industry, 53(3):231-244,2004. BS. BeanShell lightweight scripting for Java (JSR-274). http://www.beanshell.org/ [Bur97] Burns, J. C.: The evolution of office information systems. In: Datamation, 23 (1977) 4, pp. 60-64

9. Computing Surveys, 12 (1980) 1, pp. 27-60. GA05. C.W. Guenther and W.M.P. van der Aalst. Process Mining in Case Handling Systems. BETA Working Paper Series, WP 150, Eindhoven University of Technology, Eindhoven, 2005.

10. GHJV95. E. Gamma, R. Helm, R. Johnson, and J. Vlissides. Design Patterns: Elements of Reusable Object-Oriented Software. Professional Computing Series. Addison Wesley, Reading, MA, USA, 1995.

11. GHS95. D. Georgakopoulos, M. Hornick, and A. Sheth. An Overview of Workflow Management: From Process Modelling to Workflow Automation Infrastructure. Distributed and Parallel Databases, 3(2):119-153, April 1995.

12. GotzOl. Gotzer, K.; Schneiderath, U.; Maier, В.; Boehmelt, W.; Komke, Т.: Dokumenten-Management. Informationen im Unternehmen effizient nutzen. 2nd edition, Heidelberg 2001.

13. J2EE. Java Platform, Enterprise Edition (Java EE), http://java.sun.com/iavaee/

14. JB96. S. Jablonski and C. Bussler. Workflow Management: Modeling Concepts, Architecture, and Implementation. International Thomson Computer Press, London, United Kingdom, 1996.

15. JSP. JavaServer Pages Technology, http://iava.sun.com/products/isp/

16. Kiep03. B. Kiepuszewski. Expressiveness and Suitability of Languages for Control Flow Modelling in Workflows. Тезисы диссертации, Faculty of Information Technology, Queensland University of Technology, 2003.

17. LC02. H. Lin, Z. Zhao, H. Li, and Z. Chen. A Novel Graph Reduction Algorithm to Identify Structural Conflicts. In Proceedings of the Thirty-Fourth Annual Hawaii International Conference on System Science (HICSS-35). IEEE Computer Society Press, 2002.

18. Maverick. Maverick Web Publishing Framework, http://mav.sourceforge.net/

19. MDAW04. K.A. de Medeiros, B.F. van Dongen, W.M.P. van der Aalst, and A.J.M.M. Weijters. Process Mining: Extending the a-algorithm to Mine Short Loops. BETA Working Paper Series, WP 113, Eindhoven University of Technology, Eindhoven, 2004.

20. MooreOO. Moore, C.: Workflow Goes Mainstream. Planning Assumption. Giga Information Group. Cambridge (MA) 2000. 2000-04-21]

21. Mueh03. Michael zur Muehlen. Process Management Standards Overview. http://www.wfmc.org/standards/docs/Process Management Standards files/frame.htm.

22. Mueh04. Michael zur Muehlen. Workflow-based Process Controlling: Foundation, Design, and Application of Workflow-driven Process Information Systems. Logos Verlag Berlin 2004.

23. NE79. Nutt, G. J.; Ellis, C. A.: Backtalk: an office environment simulator. In: Proceedings of the 1979 International Conference on Communications. 1979, pp. 22.23.21-22.23.25.

24. NLS. P. Freiberger, M. Swaine. Fire in the valley. The Making of Personal Computer. 2nd edition, New York (NY) 2000. p. 303.

25. Petri62. C.A. Petri. Kommunikation mit Automaten. PhD thesis, Institut fur instrumentelle Mathematik, Bonn, 1962.

26. RHEA04. N. Russell, A.H.M. ter Hofstede, D. Edmond, and W.M.P. van der Aalst. Workflow Data Patterns. QUT Technical report, FIT-TR-2004-01, Queensland University of Technology, Brisbane, 2004.

27. RZ96. D. Riehle and H. Z'ullighoven. Understanding and Using Patterns in Software Development. Theory and Practice of Object Systems, 2(1):3-13,1996.

28. SABRE. G.H. Anthes, Sabre Flies to Open Systems. Computerworld, 38 (2004), 22, pp 21-25.

29. Servlet. Java Servlet Technology, http://iava.sun.com/products/servlet/

30. SOOO. Wasim Sadiq and Maria E. Orlowska. Analyzing Process Models Using Graph Reduction Techniques. Information Systems, 2000,25(2): 117-134.

31. SMAWL. SMA11 Workflow Language, http://www.stefansen.dk/smawl.pdf.

32. VELOCITY. Apache Jakarta Velocity Template Engine, http://iakarta.apache.org/velocitv/

33. WfRM. Workflow Reference Model, http://www.wfmc.org/standards/model.htm

34. Wf-XML. Workflow XML Protocol, http://www.wfmc.org/standards/

35. WMFC. Workflow Management Coalition, http://www.wmfc.com

36. XRL. Exchangeable Routing Language http://tmitwww.tm.tue.nl/staff/wvdaalst/workflow/xrl

37. XPDL. XML Process Definition Language, http://www.wfmc.org/standards/

38. Zis77. Zisman, M.: Representation, Specification, and Automation of Office Procedures. PhD Thesis, Wharton Business School, University of Pennsylvania. Philadelphia (PA) 1977.

39. Zis78. Zisman, M.: Office Automation: Revolution of Evolution. In: Sloan Management Review, 19 (1978)3, pp. 1-16.

40. KJIP01. Т. Кормен, Ч. Лейзерсон, P. Рнвест. Алгоритмы: построение и анализ. М.: МЦНМО, 2001, С. 440.

41. МБТ03. Д. Мамонтов, Д. Береснев, Е. Толстов. Интерактивное средство построения графиков //Телематика'2003. СПб: 2003. - С. 331.

42. Толс04а. Е.В. Толстов. Использование объектно-реляционного отображения для связи DTD с базами данных. // Моделирование процессов управления: сб.ст./Моск.физ.-тех. ин-т.-М., 2004.-С. 109-115.

43. Толс05а. Е.В. Толстов. Анализ графов потоков управления работами при помощи сетей Петри. //Процессы и методы обработки информации: Сб.ст./Моск.физ.-тех. ин-т. -М., 2005.-С. 15-21.

44. ТолсОба. Е. В. Толстов, Ю.А. Флеров. Экземплярный подход в задаче поиска структурных конфликтов в графах потоков работ. Препринт / ВЦ РАН. М., 2006. -36 с.

45. ТолсОбЬ. Е.В. Толстов. Реализация шаблонов потоков работ сетями Петри. Электронный журнал «Исследовано в России», 9,521-529,2006. http://zhurnal.ape.relarn.ru/articles/2006/052.pdf.

46. ТолсОбс. Е.В. Толстов. Использование сетей Петри для моделирования графов потоков работ. // Процессы и методы обработки информации: Сб.ст./Моск.физ.-тех. ин-т. -М., 2006. -С. 38-44.

47. ТолсОбё. Толстов Е.В. Моделирование структурной перспективы в системах управления бизнес-процессами. // Системы управления и информационные технологии, 2006, №1.1(23), С. 191-195.

48. ТолсОбе. Толстов Е.В. Моделирование шаблонов бизнес-процессов сетями Петри. //Информационные технологии моделирования и управления, 2006, №4(29), С. 462470.