Содержание к диссертации
Введение
1 Моделирование workflow-процессов специальными классами сетей Петри 9
1.1 Сети Петри 10
1.2 Моделирование workflow-процессов-сетями 30
1.3 Моделирование workflow-процессов RCWF-сепжя 38
1.4 Моделирование workflow-процессов вложенными сетями Петри 42
1.5 Моделирование workflow-процессов SRCWР-сетями 46
2 Анализ и оптимизация моделей workflow-процессов в виде SRCWF cejen 52
2.1 Анализ SRCW-ceie» 53
2.2 Применение теории массового обслуживания для анализа сетей 58
2.3 Экспериментальные результаты 67
Заключение 82
Литература 83
А Workflow-процессы 93
- Моделирование workflow-процессов RCWF-сепжя
- Моделирование workflow-процессов вложенными сетями Петри
- Применение теории массового обслуживания для анализа сетей
- Экспериментальные результаты
Введение к работе
Современные подходы к решению задач повышения эффективности систем управления в значительной мере основаны на новых информационных технологиях, важнейшей из которых является технология управления и оптимизации бизнес-процессов.
В настоящее время благодаря появлению мощной вычислительной техники, распространению сетевых технологий и развитию новых концепций в сфере ведения бизнеса (ERP - Enterprise Resource Planning, CRP - Capacity Requirements Planning, ...) растет интерес к электронным средствам поддержки ведения бизнеса. Об этом свидетельствует, в частности, появление нескольких стандартов на языки описания бизнес-процессов и на автоматическое взаимодействие приложений через Web-сервисы от таких компаний, как SAP AG, Sun Microsystems, IBM, Microsoft
До недавнего времени не существовало специального средства поддержки управления workflow-процессами. Поэтому отдельные части бизнес-процесса реализовывались в разных прикладных программах и были относительно разрозненны. Взаимосвязь этих частей осуществлялась в самих программах, что нежелательно, так как при изменении бизнес-процесса приходится изменять программное обеспечение. Это трудоемко и негибко. Более того, похожие программные блоки необходимо реали-зовывать в нескольких программах и невозможно осуществлять мониторинг и контроль всего workflow-процесса как единого целого. Управление workflow-процессами предлагает новый подход к контролю, мониторингу, оптимизации и сопровождению бизнес-процессов. В настоящее время, с развитием вычислительных средств и коммуникаций, возникла, возможность охватить всю систему целиком, рассмотрев составляющие ее процессы как единое целое, и выводя контур исполнительного управления на передний план [30].
Появились электронные системы управления бизнес-процессами. Многочисленные примерзл внедрения подобных систем и значительного улучшения экономических показателей на предприятиях за рубежом [55] говорят об очередном прорыве в сфере ведения бизнеса. Выделение бизнес-
процессов, их анализ, совершенствование и управление ими - колоссальный резерв для повышения конкурентоспособности компаний и эффективности их работы.
Идея представления организации в виде набора бизнес-процессов, а управления ее деятельностью - как управление бизнес-процессами стала распространяться в конце 80-х годов. Лучшие компании мира на практике доказали важность, эффективность, экономичность и прогрессивность перехода на клиептио-ориеитированное производство и процессно-ориентированную структуру управления производством. Тогда же начали появляться стандарты ИСО серии 900х на деятельность организации, которые предполагают как минимум определение и документирование бизнес-процессов.
Сегодня система управления большинства российских предприятий имеет ярко выраженную функциональную направленность. В основе подобной организации управления лежит принцип разделения и специализации труда, описанный в работе А. Смита «Достояние народа», опубликованной еще в конце XVIII века. Однако в нынешних условиях этот подход к управлению оказывается неэффективным. Реальная деятельность не осуществляется в соответствии с линейно-функциональной иерархией - она пронизывает предприятие в виде набора бизнес-процессов, которые в большинстве своем никем ие управляются, не описаны и не документированы. Пятьдесят лет назад и ранее, когда вычислительные средства поддержки информационной деятельности не были доступны, существование функционалы-!о-ориентироваиного подхода к управлению было не только оправданным, но и единственно возможным решением в управлении сложными объектами.
В настоящее время компании мирового уровня используют методы управления процессами в рамках реализации стратегии всеобщего управления качеством (TQM, Total Quality Management).
Переход на процессную ориентацию - та неизбежность, с которой придется столкнуться практически каждому среднему и крупному российскому предприятию, если оно хочет не только выжить, но и успешно развиваться. Для обеспечения конкурентоспособности российских предприятий необходимо учитывать не только технологии вчерашнего дня, ио и развивающиеся в текущий момент, разрабатывать новые.
В диссертации для управления бизнес-процессами предлагается применять различные классы сетей Петри. Такой подход позволяет использовать наглядные и математически строгие модели в качестве языка описания workflow-процессов. С другой стороны, теория сетей Петри предоставляет мощные средства анализа. Они позволяют проверить корректность моделей workflow-процессов во избежание негативных ситуаций
(блокировок, бесконечно повторяющихся циклов и т.п.).
Для оценки производительности и оптимизации работы workflow-процессов в диссертации введен новый подкласс сетей Петри -SRCWFe-cem.
Классические сети Петри были изобретены К.А. Петри в шестидесятых годах 20 в. С тех пор было создано множество их модификаций (раскрашенные сети Петри [74], вложенные сети Петри [16], стохастические сети Петри [104, 85] и т.д.) и найдены приложения в самых разных областях.. В диссертации для моделирования workflow-процессов используется несколько подклассов сетей Петри, позволяющих учитывать различные аспекты процесса. Перечислим эти подклассы, заодно делая краткий обзор работ других авторов.
Первым подклассом являются 1Ф; F-сети. WF-сети позволяют моделировать структуру workflow-процесса и проверять его свойства. WF-cem были введенны W.M.P. van cler Aalst, одним из первых исследователей, использовавших сети Петри для моделирования workflow-процессов [32, 33, 35, 36, 37, 38]. Им же было сформулировано свойство надежности модели workflow-процесса в виде VKF-сети и доказан способ его проверки исходя из структуры сети. M.Voorhoeve, N.Siclorova, К. van Нее [65, 66] и др. рассмотрели это свойство для модели, в которой участвуют несколько экземпляров workflow-процесса. Ими была доказана разрешимость задачи проверки надежности для этого случая и приведен соответствующий алгоритм.
Для моделирования workflow-процессов с учетом ресурсов организации (машины, персонал и так далее), способных выполнять задачи процесса, в диссертации используются RCWF-cem. Эти сети были выделены в отдельный подкласс M.Voorhoeve. N.Sidorova, К. van Нее [69].
Следующим подклассом являются вложенные сети Петри. Они позволяют компактно представлять workflow-процессы со сложной многоуровневой структурой, где объекты, участвующие в workflow-процессе, имеют некоторую структуру, могут проявлять активность и изменять свои состояния. Вложенные сети Петри были введены и исследованы И.А. Ломазовой [16].
В диссертации для того, чтобы учитывать время, необходимое для выполнения задач workflow-процесса, и вероятности различных альтернатив, введен новый подкласс сетей Петри - SRCW F^ce-m. Он обобщает WF- и RC'WF-сетш. Для введенных SRCWFe-ce?rePL предлагаются методы оценки производительности и оптимизации их работы.
Таким образом, направление моделирования и анализа workflow-процессов получает дальнейшее развитие.
В ,5'Ж'И/Те-сетях с точки зрения временного поведения синтезиру-
ются некоторые возможности интервальных [34, 92] и стохастических сетей Петри (GSPNs) [41, 81]. Однако они обладают рядом уникальных особенностей, являясь новым средством моделирования и анализа workflow-процессов.
Напомним, что введение концепции времени в формализм сетей Петри было предложено C.Ramchaiidani [91], P.Merlin и D.Farber [84], J.Sifakis [99]. Множество последующих различных подходов в основном основывалось на использовании детерминированных временных задержек. Сети Петри с вероятностными временными задержками были введены F.Symons [104], G,Florin, S.Nat-kin и M.Molloy [85]. Эти подходы открыли возможность связи сетей Петри с оценкой производительности, обычно основанной на подходе с помощью вероятностного моделирования. Эти модели и их модификации сейчас называются Stochastic Petri nets (SPNs). Дальнейшее развитие подхода было предложено М. Ajmone Marsan, G. Balbo и G. Coute [82]. Вероятностные задержки сочетались с детерминированными нулевыми задержками. Таким образом, временное и логическое поведение системы могло быть описано в одной модели. G. Balbo иссле-довал стохастические сети Петри и их применение в различных областях, в том числе и в экономике [41]. В ранних работах W.M.P. van der Aalst также был введен класс сетей Петри со временем - интервальные стохастические сети Петри [34]. Исследовались их свойства и алгоритмы расчета характеристик сети. Это направление получило дальнейшее развитие в работе Н.А. Reijere [92]. Им был построен ряд практических моделей и проведены численные эксперименты с ними.
Цель работы заключается в разработке методов моделирования workflow-процессов с учетом времени, их анализа и оптимизации.
Для достижения поставленной цели были сформулированы следующие задачи:
Изучить разные классы сетей Петри для моделирования workflow-нрол.ессов.
Определить и исследовать новый класс сетей Петри, позволяющий моделировать workflow-процессы с учетом ресурсов и времени.
Исследовать взаимосвязь моделей workflow-процессов с моделями теории массового обслуживания.
Разработать методы анаггиза и оптимизации моделей на основе теории массового обслуживания.
Провести эксперименты с тестовыми моделями workflow-процессов.
6. Проанализировать результаты экспериментов и проверить результаты анализа и эффективность оптимизации.
Методы исследования основаны на использовании аппарата сетей Петри, теории массового обслуживания, стохастических процессов. Исследование моделей workflow-процессов в программе ExSpect опирается на специфический язык программы с одноименным названием.
Научная новизна работы обусловливается тем, что теория бизнес-процессов только развивается. В связи с этим, отсутствует единая универсальная методология по моделированию и анализу бизнес-процессов, а существующие отдельные коммерческие продукты, использующие разные методологические базы наряду с достоинствами обладают и недостатками. В диссертации разработаны новые методы моделирования, анализа и оптимизации workflow-процессов с учетом ресурсов и времени. Получены результаты симуляции некоторых моделей workflow-процессов в программе ExSpect.
Теоретическая и практическая значимость. Работа содержит описания новых формализмов сетей Петри для моделирования worMow-процессов. Проведены исследования по анализу и оптимизации таких моделей. Теоретические выводы подтверждены результатами численных экспериментов. Полученные результаты могут быть использованы для решения прикладных задач при разработке моделей workflow-процессов, а также для разработки блоков распределения ресурсов в системах управления workflow-процессами.
Структура работы. Диссертация состоит из введения, двух глав, заключения, списка литературы и приложений.
В первой главе рассматриваются вопросы моделирования workflow-процессов специальными классами сетей Петри. Перечисляются достоинства подхода к моделированию workflow-процессов на основе сетей Петри . Даются определения, связанные с функционированием и свойствами сетей Петри. Вводятся WF-c&tu, вложенные сети Петри, RCW F-сети. Приводятся многочисленные примеры моделей workflow-процессов. Определяется новый подкласс для моделирования, анализа и оптимизации workflow-процессов -- S'ACWP-ceTH.
Во второй главе вводится специальный подкласс SRCWFe-сетей -SRCWFel-cerm. Приводятся методы анализа и оптимизации этих сетей на основе теории массового обслуживания. Даются соответствующие алгоритмы. /Для иллюстрации разбираются несколько моделей workflow-процессов. Приводятся результаты симуляции этих моделей в пакете ExSpect.
В приложении А приводятся основные понятия и определения в обла-
сти управления workflow-процессами. Описывается концепция архитектуры интегрированных информационных систем (АРИС) как базовой инфраструктуры для методов моделирования информационных систем. Указывается место управления workflow-процессами в этой архитектуре. Определяется понятие workflow-процесса, приводятся характеристики его производительности. Указываются пути улучшения этих характеристик.
В приложении В даются все необходимые сведения из теории массового обслуживания. Определяется общая модель, используемая в теории массового обслуживания, и параметры, необходимые для ее спецификации. Описываются некоторые частные системы, вероятностно-разделительная дисциплина обслуживания заявок нескольких типов.
В приложении С приведены некоторые окна пакета ExSpect с моделями SBCWF^-- и SRCWFp -сетей, на которых проводилась симуляци-онные эксперименты.
Апробация работы. Основные положения и результаты работы докладывались и обсуждались на следующих международных и российских конференциях:
Междисциплинарной (медицина, биология, физика, радиоэлектроника, химия, математика, информатика, педагогика ..,) конференции с международным участием «Новые биокибернетические и телемедицинские технологии 21 века для диагностики и лечения заболеваний человека» («ЫБИТТ-21»), г.Петрозаводск, 23-25 июня 2003 года.
Международной научно-практической конференции «Актуальные проблемы развития экономики», Иваново, 2003.
6-ой всероссийской научно-практической конференции «Стратегия бизнеса и социально-экономическое развитие региона», г.Ярославль, 27 ноября 2003 года.
III научно-практической конференции студентов и аспирантов (с международным участием) «Экономика и бизнес: позиция молодых ученых», г.Барнаул, 28-29 апреля 2004.
Полученные результаты обсуждались на научном семинаре «Моделирование и анализ информационных систем» факультета информатики и вычислительной техники Ярославского государственного университета им. П.Г. Демидова.
Публикации. По теме диссертации опубликовано 7 научных работ. Из них 3 статьи в местных изданиях, 4 доклада на конференциях.
Диссертация выполнена на кафедре теоретической информатики Ярославского государственного университета им. П.Г. Демидова.
Моделирование workflow-процессов RCWF-сепжя
Методы исследования основаны на использовании аппарата сетей Петри, теории массового обслуживания, стохастических процессов. Исследование моделей workflow-процессов в программе ExSpect опирается на специфический язык программы с одноименным названием.
Научная новизна работы обусловливается тем, что теория бизнес-процессов только развивается. В связи с этим, отсутствует единая универсальная методология по моделированию и анализу бизнес-процессов, а существующие отдельные коммерческие продукты, использующие разные методологические базы наряду с достоинствами обладают и недостатками. В диссертации разработаны новые методы моделирования, анализа и оптимизации workflow-процессов с учетом ресурсов и времени. Получены результаты симуляции некоторых моделей workflow-процессов в программе ExSpect.
Теоретическая и практическая значимость. Работа содержит описания новых формализмов сетей Петри для моделирования worMow-процессов. Проведены исследования по анализу и оптимизации таких моделей. Теоретические выводы подтверждены результатами численных экспериментов. Полученные результаты могут быть использованы для решения прикладных задач при разработке моделей workflow-процессов, а также для разработки блоков распределения ресурсов в системах управления workflow-процессами.
Структура работы. Диссертация состоит из введения, двух глав, заключения, списка литературы и приложений.
В первой главе рассматриваются вопросы моделирования workflow-процессов специальными классами сетей Петри. Перечисляются достоинства подхода к моделированию workflow-процессов на основе сетей Петри . Даются определения, связанные с функционированием и свойствами сетей Петри. Вводятся WF-C&TU, вложенные сети Петри, RCW F-сети. Приводятся многочисленные примеры моделей workflow-процессов. Определяется новый подкласс для моделирования, анализа и оптимизации workflow-процессов -ACWP-ceTH.
Во второй главе вводится специальный подкласс SRCWFe-сетей -SRCWFel-cerm. Приводятся методы анализа и оптимизации этих сетей на основе теории массового обслуживания. Даются соответствующие алгоритмы. /Для иллюстрации разбираются несколько моделей workflow-процессов. Приводятся результаты симуляции этих моделей в пакете ExSpect.
В приложении А приводятся основные понятия и определения в области управления workflow-процессами. Описывается концепция архитектуры интегрированных информационных систем (АРИС) как базовой инфраструктуры для методов моделирования информационных систем. Указывается место управления workflow-процессами в этой архитектуре. Определяется понятие workflow-процесса, приводятся характеристики его производительности. Указываются пути улучшения этих характеристик.
В приложении В даются все необходимые сведения из теории массового обслуживания. Определяется общая модель, используемая в теории массового обслуживания, и параметры, необходимые для ее спецификации. Описываются некоторые частные системы, вероятностно-разделительная дисциплина обслуживания заявок нескольких типов. В приложении С приведены некоторые окна пакета ExSpect с моделями SBCWF -- и SRCWFp -сетей, на которых проводилась симуляци-онные эксперименты. Апробация работы. Основные положения и результаты работы докладывались и обсуждались на следующих международных и российских конференциях: Междисциплинарной (медицина, биология, физика, радиоэлектроника, химия, математика, информатика, педагогика ..,) конференции с международным участием «Новые биокибернетические и телемедицинские технологии 21 века для диагностики и лечения заболеваний человека» («ЫБИТТ-21»), г.Петрозаводск, 23-25 июня 2003 года. Международной научно-практической конференции «Актуальные проблемы развития экономики», Иваново, 2003. 6-ой всероссийской научно-практической конференции «Стратегия бизнеса и социально-экономическое развитие региона», г.Ярославль, 27 ноября 2003 года. III научно-практической конференции студентов и аспирантов (с международным участием) «Экономика и бизнес: позиция молодых ученых», г.Барнаул, 28-29 апреля 2004. Полученные результаты обсуждались на научном семинаре «Моделирование и анализ информационных систем» факультета информатики и вычислительной техники Ярославского государственного университета им. П.Г. Демидова. Публикации. По теме диссертации опубликовано 7 научных работ. Из них 3 статьи в местных изданиях, 4 доклада на конференциях. Диссертация выполнена на кафедре теоретической информатики Ярославского государственного университета им. П.Г. Демидова.
Моделирование workflow-процессов вложенными сетями Петри
Таким образом, двухуровневая вложенная сеть Петри состоит из набора обыкновенных сетей Петри, задающих структуру сетевых фишек, и системной сети. Системная сеть представляет собой предикатную сеть Петри с довольно ограниченным языком выражений, которые могут быть приписаны дугам. Охраны при переходах системной сети отсутствуют (т.е. истинны при любых означиваниях переменных). Модель языка U определяется элементными сетями. Носитель модели U наряду с обычными для предикатных сетей индивидуальными элементами содержит сетевые элементы - маркированные элементные сети. Кроме того, некоторые переходы в системной и элементных сетях помечены специальными метками для обеспечения механизма синхронизации этих переходов. Далее автономные срабатывания переходов в системной и элементных сетях будут определены по правилам срабатывания для предикатных и обыкновенных сетей соответственно. Синхронные срабатывания определяются специальными правилами.
Опишем поведение двухуровневой вложенной сети. Пусть NPN — [Atom, Lab. S N\(EЛ ь ... , W;C),A) - некоторая двухуровневая NP-сеть. Как уже говорилось, разметка сети NPN есть отображение М, которое сопоставляет каждой позиции р Є Р системной сети SN некоторое (возможно пустое) мультимножество М(р) над множеством А" кортежей фишек, где п - арность позиции р. Таким образом, разметка вложенной сети определяется как разметка ее системной сети. Будем писать М(р) = 0, если М(р) = 0 , т.е. позиция р не содержит фишек. Множество всех разметок сети NPN будем обозначать через №(NPN).
Пусть - некоторый переход системной сети SN, - множества его пред- и постусловий. Через обозначим множество всех выражений, приписанных инцидентным і дугам.
Означиванием перехода t называется функция Ь, приписывающая каждой переменной и, входящей в некоторое выражение из W(t), значение b(v) из множества Aalom U А„.еЬ Очевидно, что при заданном означивании перехода і можно вычислить значение в(Ь) — Ь{0) любого выражения в Е W(t), поскольку интерпретация операции «+» известна.
Переход і сети 5 ЛГ является активным при некоторой разметке М и означивании Ъ в том и только том случае, если Ур Е і : W(p.t)(b) С М(р), т.е. всякая входная для t позиция р содержит мультимножество, являющееся значением приписанного соответствующей входной дуге выражения W(p t).
При этих условиях срабатывание перехода і порождает новую разметку М1, такую, что для всех позиций p,Af (р) = (M(p)\W(p.t){b))lJW(t,p)(b). Сетевые фишки из Aneti являющиеся значениями переменных во входных выражениях из W(i) при означивании перехода t, будем называть элементными сетями, задействованными при срабатывании . (Эти сети «убираются», возможно, в составе иекоторых кортежей, из входных позиций при срабатывании перехода і).
Определение 1.1.24. Для NP-cemu NPN определяются следующие четыре вида шагов срабатывания: системно-автономный шаг: Пусть t - непомеченный переход системной сети SN (т.е. значение A.(t) не определено). Если і является активным при разметке М и означивании Ъ и М — М , то такое срабатывание перехода і в сети SN называется системно-автономным шагом вложенной сети NPN и обозначается M[t\b])M или просто М[)М . Легко видеть, что при таком срабатывании разметки сетевых фишек не меняются, по некоторые из них перемещаются из одной позиции в другую (копируются, исчезают), а также возможно появление новых сетевых фишек. элементно-автономный шаг: Пусть М - разметка сети NPN, р Е Р - некоторая позиция системной сети SN и («i,... ,«„,) Є М{р) - кортеж, фишек, находящийся в позиции р при разметке М. Пусть далее а; — (EN,m) - сетевая фишка в этом кортеже. Пусть в обыкновенной сети Петри EN имеется переход і, такой, что значение Л(і) не определено и m[t)m!, т.е. і - непомеченный возбужденный при разметке т переход, и его срабатывание по правилам для обыкновенных сетей Петри приводит к разметке . Пусть М - разметка сети NPN, получающаяся из М заменой сетевой фишки а.г = (EN. га) на фишку а -, = (EN, т1), т.е. М - разметка, получающаяся в результате локального срабатывания перехода t в сетевой фишке а,; , при этом сеть EN остается в той оке позиции системной сети SN. Тогда такое срабатывание перехода і в сети EN называется элементно-автономным шагом вложенной сети NPN и обозначается M\t)M или просто М\)М . шаг горизонтальной синхронизации: Пусть М - разметка сети NPN, р & Р - позиция системной сети SN и (cti,..., а,,) Є М(р) - кортеж фишек, находящийся в позиции р при разметке М. Пусть далее а, = (ЕНі.іщ), = (EN2}m2) - две сетевые фишки в этом кортеже. Пусть в обыкновенной сети Петри ENi имеется переход tlt такой что A(- ) = А є Labh и in-i\ti)m\, т.е. ti - активный при разметке чщ переход и его срабатывание по правилам для обыкновенных сетей Петри приводит к разметке ra j. Пусть при этом в сети EN2 имеется переход Ц, такой что Л(-/;2) = Л Є Lohk и m-3[/;2}m,2. Пусть далее М есть разметка сети NPN, получающаяся из М заменой сетевой фишки сц = {ENi,іщ) на фишку а ; = {ЕИу.т ) и заменой фишки щ = [EN2,m2) на фишку а = (ЕАг2,т 2), т.е. М - разметка, получающаяся в результате одновременного локального срабатывания двух переходов t\ и іч в сетевых фишках ( и щ соответственно, при этом сети ENi и EN2 остаются в той оке позиции системной сети SN. Такое синхронное срабатывание переходов t% ut2 в сетях EN\ и EN2 называется шагом горизонтальной синхронизации для вложенной сети NPN и обозначается M\ti]t2)M или просто М[)М .
Если арность позициир равна 1 up содержит не кортежи, а единичные фишки, то для сетевой фишки а — [ENi,mi) парная ей сетевая фишка с возбужденным переходом, помеченным дополнительной меткой \, выбирается среди фишек, находящихся в той оке позиции р при разметке М. Выбор пары фишек из двух разных позиций сети при этом запрещается. шаг вертикальной синхронизации: Пусть і - переход систем ной сети SNtA[t) -- І Є Labv, і является возбужденным при раз метке М и означивании b и М — М1. Пусть далее {аг...., ak} С Ап& есть множество задействованных в этом срабатывании пе рехода і сетевых фишек, где а\ — (EiVj,m,i) ... .( = (ENk rii,), и пусть для каждого I і к в сети EN.j. найдется переход U, такой, что t; возбужден в ENi при разметке т.и щ[Ь)т!± (в соот ветствии с правшами срабатывания для обычных сетей Петри) и A(U) = І Є Labv. Пусть теперь W есть мультимножество кортежей элементов, полученное из множества W(t,p)(b) значений всех выражений на выходных дугах перехода і сети NPN при означивании b путем замены сетевой фишки Oi = (ENi,irii) на фишку а[ = (ЕМ;.,т[) для всех 1 г к. Тогда результатом одновременного срабатывания перехода і в системной сети SN и дополнительных к нему переходов в задействованных в этом срабатывании элементных сетях является состояние М (р) = (М(р) \ W(p, ()(b)) -\- W. Такое синхронное срабатывание перехода I (при означивании Ь) в системной сети и переходов ,..., в сетях ац,..., ак называется шагом вертикальной синхронизации для вложенной сети NPN и обозначается M[i[b\; l\_,..., tk)M или просто М[)М . Исполнением для вложенной сети NPN назовем конечную или бесконечную последовательность шагов Ма[)М [)..., где М0 есть начальная разметка сети NPN. Как обычно, разметку М сети NPN назовем достижимой, если существует исполнение MQ[)MI[) ... \)Мк, где М - Mi-. Перечислим здесь некоторые свойства вложенных сетей Петри [16]: - выразительная мощность вложенных сетей больше, чем у обыкновенных сетей Петри; - для них разрешимы проблемы поддержки управляющего состояния и останова; - неразрешимы проблемы достижимости и ограниченности.
Применение теории массового обслуживания для анализа сетей
В определении workflow-процесса упоминается о ресурсах, необходимых для выполнения задач процесса. Ресурсы - это объекты, запрашиваемые для выполнения задачи и освобождаемые при его завершении. Они являются неизменными: не могут быть созданы или израсходованы в результате выполнения задачи. Примерами ресурсов могут быть: служащий предприятия, компьютер, станок и т.д.
Разными авторами предлагаются различные способы моделирования ресурсов в WF-сетях. Например, в [69] рассматриваются RCWF-c&m (Resource Constrained WF-nets). В них вводится множество ресурсных позиций, в которых фишки соответствуют имеющимся в системе ресурсам, и эти позиции соединяются дугами с переходами, представляющими задачи в № F-ceTH.
Определение 1.3.1 (RCWF-сетъ). RCWF-сетъ есть WF-сетъ с начальной позицией і и финальной позицией f: , / Є РР! множеством Р.р производственных позиций и множеством РТ - ресурсных позиций, удовлетворяющая следующим условиям: Каждая позиция из Р,. определяет тип ресурса. Количество фишек в ресурсной позиции соответствует числу свободных ресурсов данного типа.
Задачи (tasks) и экземпляры workflow-процесса (по используемой терминологии обращайтесь к А.0.5) моделируются аналогично И -сетям. Если некоторой задаче workflow-процесса, представленной переходом і Є Г, необходим некоторый ресурс типа Pj,pj Є Рг, то I; соединяется с p-j входной дугой: (pj,l) Є F . Если после завершения задачи, представленной переходом і є Т, используемый ресурс типа pj. р, Є Рг освобождается, добавляется выходная дуга: (. Ь) Є F7+.
Введение ресурсных позиций позволяет делать различие между элементами работы (work items) и деятельностью (activities) в workflow-процессе (по используемой терминологии обращайтесь к А.0.5). Элемент работы в RCWF-сетях - это переход, соответствующий некоторой задаче workflow-процесса, который активен в некотором состоянии, если не учитывать ресурсные позиции: Ч \PV М. Деятельность (activity), т.е. элемент работы, выполняющийся некоторым ресурсом организации, - представлена активным переходом, который срабатывает в некотором состоянии. Таким образом, чтобы элемент работы стал деятельностью, необходимо, чтобы в ресурсных позициях было необходимое количество фишек и "чтобы этот переход сработал.
Свойство надежности для iGWF-сетей видоизменяется [69, 68]. Определение 1.3.2 (Свойство надежности (soundness) ROW F-сетж). ROWF-сетъ N является (к, П.)-надежной, к Є N,i Є NPr, если и только если Vm Є П(к[і] + Я),т A (k[f] + R), т \РГ R. N является к-надежной, если и только если 3 NPr; N является (h\R)-надежной для №. 1. В WF-сетях и RCWF-сетях происходит абстракция от многих факторов действительности. Во-первых, выполнение задач занимает некоторое время. Оно может быть как детерминированным (например, срок действия некоторых документов изначально задан), так и недетерминированным (например, проверка кредитоспособности заказчика). Недетерминированное время может зависеть как от внутренних факторов организации (характеристики ресурсов их загруженность работой и другие), так и от внешних (расписание работы заказчика, выходные дни и другие). Во-вторых, выполнение многих задач начинается с наступлением определенных событий. Можно выделить три вида событий: - внешние по отношению к организации. Например, поступление заказа, получение счета от поставщика и так далее; - внутренние по отношению к организации. В большинстве современных WfMS на каждом автоматизированном рабочем месте реализованы так называемые корзины. Когда некоторая задача, выполняющаяся ресурсами (сотрудниками, машинами и т.п.) организации, готова к обработке в соответствии с логикой процесса, происходит выбор среди ресурсов организации, которые могут ее выполнить. Далее заявка на выполнение поступает в корзину выбранного ресурса. В какой-то момент времени происходит выбор заявки в корзине и начало выполнения задачи. Этот выбор - внутреннее событие, без которого соответствующая задача не может быть выполнена; - временные. Иногда начало выполнения задачи задерживается на некоторое время. Например, задача «удалить неактуальный счет» запускается через определенное время, когда выписанный счет становится недействительным. Третий фактор касается выбора пути при ветвлении процесса (или способа разрешения конфликта на языке сетей Петри). В сетях Пет ри разрешение конфликтов недетерминировано. В действительно сти может использоваться несколько вариантов: - недетерминированный выбор. Способ разрешения конфликтов не задан; - детерминированный выбор при наличии у конфликтующих переходов дополнительных условий срабатывания (см. предыдущий фактор). Сработает тот переход, у которого быстрее будут выполнены все дополнительные условия, то есть выбор будет сделан не сразу при возникновении конфликта, а при наступлении событий, активизирующих один из конфликтующих переходов; - детерминированный выбор исходя из дополнительной информации. Отличие от предыдущего случая - в том, что для срабатывания не требуется наступления определенных событий, выбор делается мгновенно при возникновении конфликта., ИСХОДЯ из дополнительной информации. Информация может быть изначально присущей экземпляру процесса (например, название организации, от которой поступил заказ), возникшей в результате выполнения предыдущих задач процесса (например, анализ поступившего заказа может дать положительный результат, и будет принято решение о выполнении заказа, так и отрицательный, и заказ будет отклонен), поступившей из различных отделов организации (например, загруженность ресурсов организации работой) или из внешней среды (например, уровень рыночных цен).
Экспериментальные результаты
Легко убедиться, что приведенный алгоритм вычисляет значения среднего времени ожидания срабатывания перехода t из-за занятости ресурса {E(WTi), t Є X,.), функции штрафа F я среднего время И прохождения фишек через сеть и для исходной SRCWFpl-cerm N.
Численные эксперименты, приведенные в разделе 2.3, показали следующее. Для SRCWF -cem N5 (см. таблицу 2.4) среднее время прохождения фишек через сеть примерно на 0,1333 временных единиц (порядка 1,3 %) меньше значения, полученного с помощью приведенного выше алгоритма, а средний штраф примерно на 0,5023 (порядка 1,1 %) больше.
Критерий оптимизации сети приведен в (2.1). Для удобства выпишем его еще раз: min. іетг На величин]7 E(WTt),l Є Тг{ в SRCWР -сети можно влиять изменением приоритетов у переходов из Тті. В разделе В приводится тот факт (из [24]), что минимум линейной функции от средних времен ожидания заявок в системе Mn\Gn\i достигается при дисциплине обслуживания с относительными приоритетами, и приводится метод определения ее параметров (перестановки а-- (а 1,...,а;1)). Таким образом, для оптимизации (2.1) необходимо найти соответствующую расстановку приоритетов в каждой из систем систем 9, tp2,..., ip8. Приведем алгоритм, оптимизирующий функцию (2.1). Пусть дана сеть67? И -сетьЛ ( иііирй,Ти{іьі +и Ни{( ,7;);( ьр }, -и F U {{рдЛі), {f Л і)} І W,Pr). В результате работы алгоритма находятся оптимальные перестановки а в каждой из систем tp-], уз3,..., іря. Алгоритм оптимизации функции F (2.1) S RCW Fl-сети. ВХОД: SRCWFf-сетъ N. ВЫХОД: S ROW F 1-сеть с модифицированными приоритетами (значением функции Рг()) у переходов из Тт. ШАГ 1. Инициализация, Применим алгоритм определения интенсивностей поступления фишек в позиции для сети N. В результате будет построен список It{): It(t) - интенсивность потребления фишек переходом і Є Т. Найдем множества TTi,.... Tr$\ \FTi\ — тіі ... ,\TrJ\ — nSi и соответствующие системы массового обслуживания ф\, -р2типа Д4„..М[1 с дисциплинами обслуживания в порядке приоритета. Таким образом, в каждой системе ір.у. щ типов заявок, интенсивности поступления равны Л(%)(І)); параметр показательного распределения времени обслуживания равен W((t(j){i)) (см. раздел 2.2). ШАГ 2. Для каждого множества TTj выполнить следующее. Упорядочим все переходы %)(i (j)(nj) в порядке убывания значе ния г, ; л у, v В результате каждый переход получит некоторый номер V(tjj)(i)). Присвоим переходу /;(j)(?.) приоритет равный V[t(j)(i)) Fr(4m) = y(;km) КОНЕЦ. Приведенный алгоритм в каждой системе tfj устанавливает относительные приоритеты у заявок разных типов, что соответствует изменению функции Рг() у переходов из Trj SRCWP -ce-m N. Приведенный алгоритм минимизирует функцию (2.1). Численные эксперименты, приведенные в разделе 2.3, показали следующее. Для SRCWF -c&m N?J (см. рисунок 2.1 и таблицу 2.1) с приоритетами, полученными по приведенному выше алгоритму оптимизации, среднее время прохождения фишек через сеть примерно на 0,7141. временных единиц (порядка 6.6 %) меньше соответствующего значения для сети SRCWFf-ce-mNz- Полученные данные штрафа у SRCWF -сети Аз примерно на 8,7562 (порядка 15,6 %) меньше соответствующего значения для SFbCWF -сети JV3. 2.3 Экспериментальные результаты Симуляция заключается в имитации действительности (в данном случае - организации и окружающей среды) на соответствующем программном обеспечении. На вход системы подаются экземпляры workflow-процессов. Далее измеряют все необходимые характеристики работы системы. Эксперименты в диссертации проводились для следующих основных целей: оценить влияние сделанных упрощений для анализа сети массового обслуживания и проверить эффективность алгоритмов из разделов 2.2.6 и 2.2.7. Результаты экспериментов с тестовой моделью показали, что среднее время прохождения фишек через сеть примерно на 0,1333 временных единиц (порядка 1,3 %) меньше значення, полученного с помощью алгоритма из раздела 2.2.6. Средний штраф примерно на 0,5023 (порядка 1,1 %) больше значения, полученного с помощью этого алгоритма. Использование приоритетов, полученных с помощью алгоритма из раздела 2.2.7, дает сокращение среднего времени прохождения фишек через тестовую сеть примерно на 0,7141 временных единиц (порядка б, 6 %) по сравнению с аналогичной сетью без приоритетов. Средний штраф сократился примерно на 8,7562 (порядка 15,6 %). Использование приоритетов, полученных с помощью алгоритма из раздела 2.2.7, дает сокращение среднего времени прохождения фишек через тестовую сеть примерно на 0,8357 временных единиц (порядка 7,6 %) по сравнению с аналогичной сетью с приоритетами, выбранными случайным образом. Средний штраф сократился примерно на 26,2195 (порядка 35,7 %).
В диссертации для симуляции использовался пакет ExSpect. Приведем необходимые сведения про этот пакет.
Пакет ExSpect разработан в техническом университете г.Эйндховен, Нидерланды. Начиная с 1980 года, выпущено несколько версий пакета. В настоящее время актуальна версия 6.41, включающая графическую оболочку, специфический язык описания моделей, синтаксический анализатор и симулятор. В основе языка ExSpect лежит формализм раскрашенных сетей Петри со временем.
Есть возможность создания библиотек компонентов из модулей для специфических предметных областей. Уже существуют модули для workflow-процессов, процессов логистики, административных процессов и других. Это позволяет в графической оболочке быстро строить модели из соответствующих компонентов, проводить анализ их производительности и симуляцию. Анализ workflow-процессов с помощью ExSpect позволяет определять узкие места в процессах организации, принимать управленческие решения по реорганизации предприятия, проводить оптими зацжю процессов и распределять кадровые и машинные ресурсы. Можно импортировать модели процессов, созданных в других пакетах и системах управления workflow, таких, как COSA Workflow (Ley GmbH, COSA Solutions) и Protos (Pallas Athena).
Модели могут быть проверены на синтаксическую корректность. Симуляция может проводиться по шагам, непрерывно или с точками останова.
Проведение верификации модели не предусмотрено в ExSpect. Однако есть возможность экспорта описания модели с последующим анализом в соответствующих программных пакетах.
Основными компонентами модели языка ExSpect являются процессоры и каналы (соответствующие переходам и позициям в сетях Петри), соединенные между собой (аналогично сетям Петри). Как в раскрашенных стохастических сетях Петри, фишки в каналах имеют некоторое значение и временную метку. С каждым каналом связан некоторый тип (определяющий тип фишек, которые могут в нем находиться), с каждым процессором - функция (задающая правило срабатывания процессора). Если не указывать временные задержки, получится модель без времени аналогично раскрашенным сетям Петри.
