Моделирование и оптимизация workflow-процессов тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Горбунов, Олег Евгеньевич

• Горбунов, Олег Евгеньевич
• кандидат физико-математических наук
• 2006

Оглавление диссертации кандидат физико-математических наук Горбунов, Олег Евгеньевич

Введение

1 Моделирование workflow-процессов специальными классами сетей Петри

1.1 Сети Петри.

1.2 Моделирование workflow-процессов

W F- сетями.

1.3 Моделирование workflow-процессов

RCW F-сешш.

1.4 Моделирование workflow-процессов вложенными сетями Петри.

1.5 Моделирование workflow-процессов

SRCWFe-сетями.

2 Анализ и оптимизация моделей workflow-процессов в виде SRC'WFe-c&reik

2.1 Анализ SRCWFel-ceTe%

2.2 Применение теории массового обслуживания для анализа SRCWFcl-сетей.

2.3 Экспериментальные результаты.

Введение диссертации (часть автореферата) на тему «Моделирование и оптимизация 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-npo-цессов в диссертации введен новый подкласс сетей Петри

SRCWF'-cffrti.

Классические сети Петри были изобретены К.А. Петри в шестидесятых годах 20 в. С тех пор было создано множество их модификаций (раскрашенные сети Петри [74], вложенные сети Петри [16], стохастические сети Петри [104, 85] и т.д.) и найдены приложения в самых разных областях. В диссертации для моделирования workflow-процессов используется несколько подклассов сетей Петри, позволяющих учитывать различные аспекты процесса. Перечислим эти подклассы, заодно делая краткий обзор работ других авторов.

Первым подклассом являются ИЛР-сети. WF-сети позволяют моделировать структуру workflow-процесса и проверять его свойства. WF-сети были введенны W.M.P. van der Aalst, одним из первых исследователей, использовавших сети Петри для моделирования workflow-процессов [32, 33, 35, 36, 37, 38]. Им же было сформулировано свойство надежности модели workflow-процесса в виде WF-сети и доказан способ его проверки исходя из структуры сети. M.Voorhoeve, N.Sidorova, К. van Нее [65, 66] и др. рассмотрели это свойство для модели, в которой участвуют несколько экземпляров workflow-процесса. Ими была доказана разрешимость задачи проверки надежности для этого случая и приведен соответствующий алгоритм.

Для моделирования workflow-процессов с учетом ресурсов организации (машины, персонал и так далее), способных выполнять задачи процесса, в диссертации используются ROW F-сети. Эти сети были выделены в отдельный подкласс M.Voorhoeve, N.Sidorova, К. van Нее [69].

Следующим подклассом являются вложенные сети Петри. Они позволяют компактно представлять workflow-процессы со сложной многоуровневой структурой, где объекты, участвующие в workflow-процессе, имеют некоторую структуру, могут проявлять активность и изменять свои состояния. Вложенные сети Петри были введены и исследованы И.А. Ломазовой [16].

В диссертации для того, чтобы учитывать время, необходимое для выполнения задач workflow-процесса, и вероятности различных альтернатив, введен новый подкласс сетей Петри - SRCWFe-сети. Он обобщает WF- и RCWF-сети. Для введенных SRCWFe-сетей предлагаются методы оценки производительности и оптимизации их работы.

Таким образом, направление моделирования и анализа workflow-npo-цессов получает дальнейшее развитие.

В SRCWFe-сетях с точки зрения временного поведения синтезируются некоторые возможности интервальных [34, 92] и стохастических сетей Петри (GSPNs) [41, 81]. Однако они обладают рядом уникальных особенностей, являясь новым средством моделирования и анализа workflow-процессов.

Напомним, что введение концепции времени в формализм сетей Петри было предложено C.Ramchandani [91], P.Merlin и D.Farber [84], J.Sifakis [99]. Множество последующих различных подходов в основном основывалось на использовании детерминированных временных задержек. Сети Петри с вероятностными временными задержками были введены F.Symons [104], G.Florin, S.Natkin и M.Molloy [85]. Эти подходы открыли возможность связи сетей Петри с оценкой производительности, обычно основанной на подходе с помощью вероятностного моделирования. Эти модели и их модификации сейчас называются Stochastic Petri nets (SPNs). Дальнейшее развитие подхода было предложено М. Ajmone Marsan, G. Balbo и G. Conte [82]. Вероятностные задержки сочетались с детерминированными нулевыми задержками. Таким образом, временное и логическое поведение системы могло быть описано в одной модели. G. Balbo исследовал стохастические сети Петри и их применение в различных областях, в том числе и в экономике [41]. В ранних работах W.M.P. van der Aalst также был введен класс сетей Петри со временем - интервальные стохастические сети Петри [34]. Исследовались их свойства и алгоритм мы расчета характеристик сети. Это направление получило дальнейшее развитие в работе Н.А. Reijers [92]. Им был построен ряд практических моделей и проведены численные эксперименты с ними.

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

Для достижения поставленной цели были сформулированы следующие задачи:

1. Изучить разные классы сетей Петри для моделирования workflow-процессов.

2. Определить и исследовать новый класс сетей Петри, позволяющий моделировать workflow-процессы с учетом ресурсов и времени.

3. Исследовать взаимосвязь моделей workflow-процессов с моделями теории массового обслуживания.

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

5. Провести эксперименты с тестовыми моделями workflow-процессов.

6. Проанализировать результаты экспериментов и проверить результаты анализа и эффективность оптимизации.

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

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

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

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

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Горбунов, Олег Евгеньевич

ВЫХОД:

E(WTt), I G Тг - среднее время ожидания срабатывания перехода t из-за занятости ресурса; F - значение функции штрафа; Я - среднее время прохождения фишек через сеть.

ШАГ 1. Инициализация.

Из исходной SRG'WFf-сети N выделим сеть N' = (Pp,TU {U}, F+ U {(U,i)},F~, W, Рг). Все шаги алгоритма будут выполняться на N'.

Обозначим Л = W(U) - интенсивность поступления фишек в позицию г. Применим алгоритм определения интенсивностей поступления фишек в позиции для сети N'.

ШАГ 2. Перебор всех переходов из Т. Для j := 2 до п + 1 Начало

Пусть Nt{t) = j. - если I G Тг, то вычислить E(WTt) по формуле (В.9). Пусть t G Try и имеет обозначение Тогда в (В.9):

- значение приоритетного класса к равно приоритету перехода Pr(t^x))\

- число типов заявок п равно \Тту\ = пу;

- А(,;) равна It{tz), где 1г - переход из Тгу с приоритетом г\

- 4) Равен ^ = W2(l)(x)}, где tg - переход из Тгу с приоритетом г. Здесь используется то, что в SRCWFel-сетях у всех переходов из множества Тгу одно и то же значение функции W().

F:=F + PF(twx))E(WT4iimy,

H^H + ^f^EiWT^J-, - если t £ Т/Тт и Pr(t) = 0, то

Я ■= Я 4- /i(-t(y)(x)'> 1 а ЩЧм,))' Конец.

КОНЕЦ.

Легко убедиться, что приведенный алгоритм вычисляет значения среднего времени ожидания срабатывания перехода t из-за занятости ресурса (E(WTt), t £ Тг), функции штрафа F и среднего время Я прохождения фишек через сеть и для исходной SRCWFpl-сети N.

Численные эксперименты, приведенные в разделе 2.3, показали следующее. Для SRCWFf1-сети JV5 (см. таблицу 2.4) среднее время прохождения фишек через сеть примерно на 0,1333 временных единиц (порядка 1,3 %) меньше значения, полученного с помощью приведенного выше алгоритма, а средний штраф примерно на 0,5023 (порядка 1,1%) больше.

2.2.7 Оптимизация SRCWF^-сетей

Критерий оптимизации сети приведен в (2.1). Для удобства выпишем его еще раз:

F=Y, E{WTt)PF(t) min. texr

На величину E(WTt), t G Tr{ в SRCWF^1-сети можно влиять изменением приоритетов у переходов из Tri.

В разделе В приводится тот факт (из [24]), что минимум линейной функции от средних времен ожидания заявок в системе Mn\Gn\l достигается при дисциплине обслуживания с относительными приоритетами, и приводится метод определения ее параметров (перестановки а - (ci'i,. ,ап)).

Таким образом, для оптимизации (2.1) необходимо найти соответствующую расстановку приоритетов в каждой из систем систем </?ь </?2, • • •, </V

Приведем алгоритм, оптимизирующий функцию (2.1). Пусть дана сеть SR.CWF;l-ceTb N = {РриРМ)д,Ти{и,1;},Р+иР7+и{(и, г), (th рд)}, F~U F~ U {{рд,и), (/,£/)}, W,Pr). В результате работы алгоритма находятся оптимальные перестановки а в каждой из систем </?], </?2, • • •, </V

Алгоритм оптимизации функции F (2.1) S НС W Ff-сети. ВХОД: SRCWFf-сеть N. ВЫХОД:

SRCWFf-сеть с модифицированными приоритетами (значением функции PrQ) у переходов из Тг.

ШАГ 1. Инициализация.

Применим алгоритм определения интенсивностей поступления фишек в позиции для сети N. В результате будет построен список ItQ: lt(t) - интенсивность потребления фишек переходом t е Т.

Найдем множества Тг1,. ,Trs; \Тг1\ — щ,., |Tr,s| = ns, и соответствующие системы массового обслуживания • • •, типа МЩ\М\1 с дисциплинами обслуживания в порядке приоритета. Таким образом, в каждой системе щ типов заявок, интенсивности поступления равны h(t{j)(i)), параметр показательного распределения времени обслуживания равен W((t(j^) (см. раздел 2.2).

ШАГ 2.

Для каждого множества Trj выполнить следующее. Упорядочим все переходы i'(j)(i),., t{j){nj) в порядке убывания значения •)(.))■ ® результате каждый переход получит некоторый номер V{tfj){i)). Присвоим переходу ty)^ приоритет равный V(t^)(i)):

Рг(*ш) = у(Чт)

КОНЕЦ.

Приведенный алгоритм в каждой системе ^ устанавливает относительные приоритеты у заявок разных типов, что соответствует изменению функции Рг() у переходов из Trj SRCWFf -сети N. Приведенный алгоритм минимизирует функцию (2.1).

Численные эксперименты, приведенные в разделе 2.3, показали следующее. Для SRCWFf-сети No, (см. рисунок 2.1 и таблицу 2.1) с приоритетами, полученными по приведенному выше алгоритму оптимизации, среднее время прохождения фишек через сеть примерно на 0,7141 временных единиц (порядка 6,6 %) меньше соответствующего значения для сети SRCWFf-ceTttN3. Полученные данные штрафа у SRCWFf-сети Ns примерно на 8,7562 (порядка 15,6 %) меньше соответствующего значения для SRCW Ff- сети N3.

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,6 %) по сравнению с аналогичной сетью без приоритетов. Средний штраф сократился примерно на 8,7562 (порядка 15,6 %).

Использование приоритетов, полученных с помощью алгоритма из раздела 2.2.7, дает сокращение среднего времени прохождения фишек через тестовую сеть примерно на 0,8357 временных единиц (порядка 7,6 %) по сравнению с аналогичной сетью с приоритетами, выбранными случайным образом. Средний штраф сократился примерно на 26,2195 (порядка 35,7 %).

В диссертации для симуляции использовался пакет ExSpect. Приведем необходимые сведения про этот пакет.

2.3.1 Пакет ExSpect

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

Есть возможность создания библиотек компонентов из модулей для специфических предметных областей. Уже существуют модули для work-flow-процессов, процессов логистики, административных процессов и других. Это позволяет в графической оболочке быстро строить модели из соответствующих компонентов, проводить анализ их производительности и симуляцию. Анализ workflow-процессов с помощью ExSpect позволяет определять узкие места в процессах организации, принимать управленческие решения по реорганизации предприятия, проводить оптимизацию процессов и распределять кадровые n машинные ресурсы. Можно импортировать модели процессов, созданных в других пакетах и системах управления workflow, таких, как COSA Workflow (Ley GmbH, COSA Solutions) и Protos (Pallas Athena).

Модели могут быть проверены на синтаксическую корректность. Симуляция может проводиться по шагам, непрерывно или с точками останова.

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

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

Язык ExSpect состоит из двух частей.

Первая часть используется для описания типов и функций. Имеется несколько примитивных типов и несколько конструкций для определения новых типов на основе базовых. По аналогии имеется несколько базовых функций и конструкции для определения новых. Допускается полиморфизм функций. ExSpect перед выполнением производит проверку типов.

Другая часть ExSpect используется для описания сети процессоров и каналов.

В ExSpect есть пять примитивных типов: void, bool, num, real, str. Операторы типов следующие: оператор множества ($), декартова произведения (><) и отображения (->). Из примитивных типов с помощью этих операторов формируются новые типы, которым присваиваются новые имена. Например: type weight from real with [x] x >= 0.0; type volume from real with [x] x >= 0.0; type manufacturer from str; type truck from manufacturer >< (weight >< volume); type truckid from num; type fleetoftrucks from truckid -> truck; type cargo from weight >< volume;

В ExSpect довольно обширный список базовых функций, из которых строятся новые функции. Например: transportablebytruck[c: cargo, t: truck] := pil(c) <= pil(pi2(t))) and (pi2(c) <= pi2(pi2(t))): bool; transportablebyfleet[c: cargo, f: fleetoftrucks]:= if f = О then false else transportablebytruck(c,pi2(pick(f))) or transportablebyfleet(c,frest(f)) fi: bool;

Функции pil, pi2 (проекции), pick и frest (соответственно взятие и удаление элемента из отображения) являются примерами базовых функций.

Определения процессоров разделены на заголовок и содержимое. Заголовок содержит имя процессора, его связи с входными и выходными каналами и параметры. Содержимое содержит выражения для выходных каналов. Например: proc transportfunction[in leave: truck, out arrive: truck, val d: time]:= arrive <- leave delay d;

Этот процессор может использоваться для моделирования транспортировки с временной задержкой. Время между прибытием и отправлением задается параметром d.

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

2.3.2 Результаты экспериментов

В разделе приведены результаты экспериментов с моделями workflow-процессов в виде SRCWFf- и SRCWFf -сетей в пакете ExSpect. Для этого в пакете была разработана библиотека для удобного моделирования задач workflow-процесса. Эксперименты проводились с тремя сетями: SRCWFf-сетью jV3j полученной из нее S-RCWFp1-сетью JV4 со случайно выбранными приоритетами из Тг и сетью N5 с приоритетами, полученными с помощью алгоритма из пункта 2.2.7. Результаты экспериментов с моделью N5 показали, что среднее время прохождения фишек через сеть примерно на 0,1333 временных единиц (порядка 1,3 %) меньше значения, полученного с помощью алгоритма из раздела 2.2.6. Средний штраф примерно на 0,5023 (порядка 1,1 %) больше значения, полученного с помощью этого алгоритма.

Для симуляции была создана библиотека в пакете ExSpect, позволяющая строить модели workflow-процессов в виде SRCWFf и SRCWЯ®1-сетей.

Исследуем SRCWFf-сеть 7V3, приведенную на рисунке 2.1. С помощью преобразования из раздела 2.2 получим SRCWF^1-сеть N3. Для определенности обозначим ее Л/4. Приоритеты добавленных в результате этого преобразования переходов выбраны произвольно. Параметры сети vV4 приведены в таблице 2.3.

С помощью алгоритма определения интенсивностей поступления фишек в позиции SRCWFf-сети, найдем соответствующие интенсивности для //4. Заметим, что It{tf) = It{k)

Применим алгоритм оптимизации функции F (2.1) для нахождения оптимальных приоритетов у переходов £ {1,2,., 5} и е

1,2}. Полученную сеть обозначим jV5.

Используя алгоритм определения значений E(WTt), F и Я, найдем соответствующие значения для сети Л/5.

Полученные значения интенсивностей /t(), приоритетов Рг() и средних времен ожидания E(WTt) приведены в таблице 2.4.

Значение функции штрафа F « 46,7393.

Среднее время прохождения фишек через сеть Я 10,2589 временных единиц.

Эксперименты проводились с тремя моделями: SRCWFf-сетью N3, SRCWFf-сетью N4 и SRCW F^-сетъю Nb. Выполнялось 1000 запусков системы (серий). Длительность каждой серии - 480 временных единиц. Если в качестве временной единицы считать минуту, то длительность эксперимента соответствует около 3,9 годам, если продолжительность рабочего дня считать равной 480 минутам, а количество рабочих дней в году равным 255.

В каждой серии с получались выборочные значения следующих величин:

• WT™. Измерения проводились по каждому переходу t £ Тт при прохождении через него фишки;

Переход Pr() wo PF{) к 0 0,5 к 6 7,0 к 6 3,0 к 6 2,0 к 6 8,0 к 0 15,0 к 0 5,0

Ь 6 1,0 km 0 2,0 3,0 km 2) 0 2,0 1,0 km 0 2,0 1,5 km 0 2,0 4,0 km) 0 2,0 5,0

2)(1) 0 0,75 7,0

2)(2) 0 0,75 5,0 ь{т 3 2,0 3,0

1)(2) 5 2,0 1,0

1)(3) 1 2,0 1,5 t'cm 2 2,0 4,0 f! W) 4 2,0 5,0

2 0,75 7,0 42) (2) 1 0,75 5,0

Заключение

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

1. Изучены разные классы сетей Петри для моделирования workflow-процессов.

2. Определен и исследован новый класс стохастических сетей Петри (.SRCWFe-ceTit), позволяющий моделировать workflow-процессы с учетом ресурсов и времени. SRCW Fe-сети позволяют в рамках одной модели использовать методы анализа обычных сетей Петри (например, исследование дерева достижимости) и вычислять производительность на основе статистических методов и проводить оптимизацию.

3. Исследована взаимосвязь SRCWFel-сетей с моделями теории массового обслуживания.

4. Предложены методы анализа SRCWFel-ceTeft на основе теории массового обслуживания.

5. Разработан алгоритм нахождения параметров SRCWFel-ceTn для оптимизации ее работы.

6. Построены модели и выполнена симуляция workflow-процессов в виде Si?CW-Ре1-сетей в программе ExSpect.

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Горбунов, Олег Евгеньевич, 2006 год

1. Ачасова С.М., Бандман О.Л. Корректность параллельных вычислительных процессов. Новосибирск: Наука, 1990. - 253 с.

2. Бандман О.Л. Корректность асинхронных параллельно-потоковых систем обработки данных. // Программирование. 1986. - № 1. - С. 13-22.

3. Бандман О.Л. Синтез асинхронного управления параллельными процессами. // Кибернетика. 1980. - № 1. - С. 42-49.

4. Белов Ю.А. Элементы теории множеств и математической логики. Учебное пособие. - Ярославль: Ярославский государственный университет, 2002. - 60 с.

5. Виленкин С.Я., Гольденберг Р.И., Розенблит С.И. Язык управления заданиями для вычислительных комплексов с централизованным управлением. // Программирование. 1982. - № 2. - С. 35-44.

6. Горбунов О.Е., Соколов В.А. Об использовании вложенных сетей Петри для моделирования бизнес-процессов. // Проблемы экономики, финансов и управления производством. Иваново: Ивановский гос. хим.-тех. университет, 2003. - № 14. - С. 253-263.

7. Горбунов О.Е., Соколов В.А. Использование вложенных сетей Петри для моделирования бизнес-процессов. // Международная научнопрактическая конференция «Актуальные проблемы развития экономики». Иваново, 2003. - С. 112-114.

8. Горбунов О.Е. Оптимизация выполнения workflow-процессов. // Моделирование и анализ информационных систем. Ярославль: ЯрГУ, 2005. - Т. 12, № 1. - С. 45-51.

9. Громов Александр, Каменнова Мария, Старыгин Александр. Управление бизнес-процессами на основе технологии Workflow. // Открытые системы. 1997. - № 1.

10. Карлин С. Основы теории случайных процессов. М.: Мир, 1971. -536 с.

11. Клейнрок JI. Теория массового обслуживания. Пер. с англ. / Пер. И.И. Грушко; ред. В.И.Нейман. - М.: Машиностроение, 1979. - 432 с.

12. Клейнрок Л. Вычислительные системы с очередями. Пер. с англ. под ред. Б.С.Цыбакова. - М.: Мир, 1979. - 600 с.

13. Котов В.Е. Сети Петри. М.: Наука, 1984. - 160 с.

14. Ломазова И.А. Вложенные сети Петри: моделирование и анализ распределенных систем с объектной структурой. Ярославль: ЯрГУ, 2002. - 151 с.

15. Ломазова И.А. Дискретная математика. Математические основы обработки информации: Учебное пособие. Ярославль: ЯрГУ, 2000. -80 с.

16. Минский М. Вычисления и автоматы. М.: Мир, 1971.

17. Мурата Т. Сети Петри: свойства, анализ, приложения. // ТИИЭР. 1989. - Т. 77, № 4.

18. Питерсон Дж. Теория сетей Петри и моделирование систем. М.: Мир, 1984. - 264 с.

19. Соколов В.А., Горбунов О.Е. Новые информационные технологии управления бизнес-процессами. // 6-я всероссийская научно-практическая конференция «Стратегия бизнеса и социально-экономическое развитие региона». Ярославль, 2003. - С. 23-26.

20. Тимофеев Е.А. Вероятностно разделительная дисциплина обслуживания и многогранник средних времен ожидания в системе GI\Gn\l. // Автоматика и телемеханика. - 1991. - № 10. - С. 121125.

21. Тимофеев Е.А. Оптимальные приоритеты в системе GI\Gn\l. // Кибернетика. 1990. - № 6. - С. 36-43.

22. Тимофеев Е.А. Оптимизация средних длин очередей в системе обслуживания с ветвящимися потоками вторичных требований. // Автоматика и телемеханика. 1995. - № 3. - С. 60-67.

23. Угланов А.В. Об оптимизации одной системы обслуживания. //5 международная вильнюсская конференция по теории вероятностей и математической статистике. Вильнюс, 1989. - Т.4. - С. 299.

24. Угланов А.В., Цыпленкова Е.В. Об оптимальной организации одной системы массового обслуживания. // Отраслевая научно-техническая конференция «Интегральные оптические сети связи».- Ленинград, 1989. Т.1. - С. 28-29.

25. Феллер В. Введение в теорию вероятностей и ее приложения, Том1. М.: Мир, 1964. - 498 с.

26. Феллер В. Введение в теорию вероятностей и ее приложения, Том2. М.: Мир, 1964. - 752 с.

27. Хинчин А.Я. Работы по математической теории массового обслуживания. М.: Физматгиз, 1963. - 236 с.

28. Шеер Август-Вильгельм. Бизнес-процессы. Основные понятия. Теория. Методы. 2-е издание. Пер. с англ. - М.: Весть - МетаТехноло-гия, 1999. - 152 с.

29. Яглом A.M., Яглом И.М. Вероятность и информация. 3-е издание.- М.: Наука, 1973. 512 с.

30. W. М. P. van der Aalst. The application of Petri Nets to Workflow Management. // The Journal of Circuits, Systems and Computers. -1998. № 8 (1). - P. 21-66.

31. W. M. P. vail der Aalst and К. M. van Нее. Workflow Management: Models, Methods, and Systems. MIT Press, 2002. - 359 p.

32. W. M. P. van der Aalst. Interval Timed Petri Nets and their analysis. // Computing Science Notes. Netherlands, Eindhoven: Eindhoven University of Technology, 1991. - № 91/09.

33. W. M. P. van der Aalst. Verification of workflow nets. // LNCS. -Springer-Velag, Berlin, 1997. Vol. 1248. - P. 407-426. (Conference Aplication and Thery of Petri Nets 1997, ICATPM'1997. In P.Azema and G.Balbo, editors).

34. W.M.P. van der Aalst. Structural Characterizations of Sound Workflow Nets. // Computing Science Reports. Eindhoven: Eindhoven University of Technology, 1996. - № 96/23.

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

36. W.M.P, van der Aalst. Modeling logistic systems with ExSpect. // Proc. of Dynamic modelling of Information Systems. In H.G. Sol and K.M. van Нее, editors. Amsterdam: Elsevier Science Publishers, 1991. - P. 269-288.

37. Rob Allen. Workflow: An Introduction. // http://wfmc.org/information/Workflow-AnIntroduction.pdf.

38. Gianfranco Balbo. Introduction to Stochastic Petri Nets. // LNCS.- Springer-Verlag, 2001. Vol. 2090. (Conference FMPA2000. In E. Brinksma, H. Hermanns, and J.-P. Katoen, editors). - P. 84-155.

39. Berthomieu B. and Diaz M. Modeling and verification of time dependent systems using time Petri nets. // IEEE Trans. Softw. Eng. 1991. - № 17(3). - P. 259-273.

40. Buy U. and Sloan R. A Petri-net-based approach to real-time program analysis. // Seventh Intrnat. Workshop on Software Specification and Design. Dec 1993. - P. 56-60.

41. J. A. Buzacott and J.G. Shanthikumar. Stochastic Models of Manufacturing Systems. Prentice Hall, 1993.

42. Casanave. Business-Object Architectures and Standards. 1997.

43. Cooper R. B. Introduction to queueing theory. Second edition. -Elsevier North Holland, Inc., 1981. - 347 p.

44. Corbett J.C. and Avrunin G.S. A practical technique for bounding the time between events in concurrent real-time systems. // Internat. Sympos. On Software Testing and Analysis. ACM, June 1993. - P.110-116.

45. Cormen Т.Н., Leiserson C.E., and Rivest R.L. Introduction to Algorithms. MIT Press / McGraw-Hill, 1990.

46. Hans Daduna. Queueing Networks with Discrete Time Scale. // LNCS.- Springer-Verlag, 2001. Vol.2046. - 138 p.http://www.daimi.au.dk/designCPN

47. J. Desel and J. Esparza. Free Choice Petri Nets. // Cambridge tracts in theoretical computer science. Cambridge: Cambridge University Press, 1995. - Vol. 40.http://www.exspect.com

48. ExSpect User Manual. // http://www.exspect.com. Fingar. Blueprint for Business Objects. 1996.

49. Fischer, Layna. Excellence in Practice Volume III. Future Strategies Inc., Lighthouse Point, 1999.

50. Peter J.Haas. Stochastic Petri Nets for modelling and simulation. // Proceedings of the 2004 Winter Simulation Conference. In R.Ingalls, M.Rossetti, J.Smith, B.Peters, editors. 2004.

51. Hack M. Petri Net Languages. Cambridge: MIT, 1976.

52. Hack M. Decidability Questions for Petri Nets, MIT Lab. // Computer Science. Springer-Verlag, 1980. - № 84.

53. Hammer M., Champy J. Re-engineering the corporation. London: Nicolas Brealey Publishing, 1995.

54. Hammer M., Champy J. Business Reengineering. 1995.

55. Harrington. Business Process Improvement. 1991.

56. Hauschildt D., Verbeek H.M.W., van der Aalst W.M.P. WOFLAN: a Petri-net-based Workflow Analyzer. // Computing Science Reports. -Eindhoven: Eindhoven University of Technology, 1997. № 97/12.

57. K. van Нее, Somers L. J., Vorhoeve M. A Formal Framework for Dynamic Modelling of Information Systems. // Dyn. Mod. Inf. Sys. North Holland, 1991. - P. 227-236.

58. Van Нее К., Sidorova N., Voorhoeve M. Resource-Constrained Workflow Nets. // Proc. of Concurrency Specification and Programming, CS&P'2004, Caputh, 2004. Informatik-Bericht Nr. 170, Humboldt-Universitet zu Berlin. - P. 166-177.

59. Heitmeyer C., Jeffords R., and Labaw M. A benchmark for comparing different approaches for specifying and verifying real-time systems. //

60. Proc. Tenth Internat. Workshop on real-time Operation Systems and Software, May 1993. 1993.

61. Hoare C.A.R. Commucication and Sequantial Processes. London.: Prentice Hall, 1985.

62. Jacobsen. Object-Oriented Software Engineering. 1996

63. Jancar P. and Moller F. Checking regular properties of Petri nets. // LNCS. Springer-Verlag, 1995. - Vol. 962. (Conference CONCUR'95).- P. 348-362.

64. Jensen K. Coloured Petri Nets. Vol.1: Basic Concepts. EATCS Monograph 28. - Springer-Verlag, 1992.

65. Jones N.D., Landweber L.H., and Lien Y.E. Complexity of some problems in Petri nets. // Theoretical Comput. Sci. 1977. - № 4. P. 277-299.

66. Johnsonbaugh R. and Murata T. Analysis of rsource requirements in marked graph computation models. // Procs. of the 1980 IEEE International Symposium on circuits and Systems, April 1980. 1980.- P. 342-345.

67. Kelly F.P. Reversibility and Stochastic Networks. England, Chichester: John Wiley and Sons Ltd., 1979. - 230 p.

68. Korenjak A. and Hopcroft J. Simple deterministic languages. // Procs. of 7th IEEE Switching and Automata Theory conference, 1966. -1966.- P. 36-46.

69. Zhen Liu, Don Towsley. Stochastic scheduling in in-forest networks. -Juillet, 1992. 34 p.1.mazova I. On Proving Large Distributed Systems: Petri Net Modules Verification. // LNCS. Springer-Verlag. - Vol. 1277 . - P. 70-75.

70. M. Ajmone Marsan, G. Balbo, G. Conte, S. Donatelli and G. Franceschinis. Modelling with generalised stochastic Petri nets. Wiley Series in Parallel Computing. - England: John Wiley and Sons, 1994. -316 p.

71. M. Ajmone Marsan, G. Balbo, G. Conte. A class of generalized stochastic Petri nets for the performance analysis of multiprocessor systems. // ACM Transactions on Computer Systems. May 1984. - № 2(1).

72. Mayr E. An algorithm for the general Petri net reachability problem. // SIAM Journal of Computing. 1984. - № 13(3). - P. 441-460.

73. P.M.Merlin and D.J.Farber. Recoverability of communication protocols: Implications of theoretical study. // IEEE Transactions of Communications. September 1976. - № 24(9). - P. 1036-1043.

74. Molloy. M.K. On the Integration of Delay and Throughput Measures in Distributed Processing Models: PhD thesis / UCLA. Los Angeles, CA, 1981.

75. Molloy. M.K. Performance analysis using stochastic Petri nets. // IEEE Transaction of Computers. September 1982. - № 31(9). - P. 913-917.

76. Murata T. Petri Nets: Properties, Analysis and Applications. // Procs. of the IEEE. 1989. - № 77(4). - P. 541-580.

77. Myers. Knowledge Management and Organizational Design. 1996.

78. Nain P. Basic elements of queueing theory. Application to the Modelling of Computer Systems. France, Sophia Antipolis, 2004. - 110 p.

79. Charles Plesums. Introduction to Workflow. // http://wfmc.org/information/introductiontoworkflow02.pdf.

80. C.Ramchandani. Analysis of Asynchromous Concurrent Systems by Timed Petri Net: PhD thesis / Cambridge: MIT, MA, 1974.

81. Hajo A.Reijers. Design and Control of Workflow Processes. Business Process Management for the Service Industry. // LNCS. Springer-Verlag, 2003. - Vol. 2617. - 308 p.

82. Reisig W. Petri Nets. Springer-Verlag, 1985.

83. Scheer August-Wilhelm. Business Process Engineering. 1994.

84. Scheer August-Wilhelm. Efficient Information Management. 1991.

85. Schmidt K. Symmetries of Petri Nets. // Petri Net Newsletter. 1993. - № 43. - P. 9-25.

86. Schroder. Business Engineer. 1997.

87. Sebestyen. Management «Geheimnis» Kaizen. 1994.

88. J.Sifakis. Petri nets for performance evaluation. Proc. 3rd Intern. Symp. IFIP. In B.Beilner and E.Gelenbe, editors. 1978. - P. 75-93.

89. Sloun R.H. and Buy U. Reduction rules for time Petri nets. // Information Processing Letters. 1994.

90. Sloun R.H. and Buy U. Analysis of real-time programs with simple-time Petri nets. // ISSTA. Seattle Washington USA, 1994. - № 94-8/94.

91. Starke P.H. Reachability analysis of Petri nets using symmetries. // Syst. Anal. Model. Sirnul., 1991. - .№ 8. - P. 293-303.

92. Suzuki I. and Murata T. A method of stepwise refimenet and abstraction of Petri nets. // Journal of Computer and System Sciences.- 1983. № 27. - P. 51-76.

93. Symons F.J.W. Modeling and Analysis of Communication Protocols Using Numerical Petri Nets: PhD thesis: 05.1978 / Univerity of Essex.- 1978.

94. Sokolov V.A., Tiinofeev E.A. Dynamical Priorities without Time Measurment and Modification of the TCP. //LNCS. Springer-Verlag, 2001. - Vol. 2244. (Conference PSI 2001). - P. 240-245.

95. Uglanov A.V. To optimization of unreliable systems. // Procs. of WSEAS Intern. Conference in Applied Mathematics, 2004. 288, 2004.- P. 488.

96. Uglanov A.V. Optimization of one unrealible system. // Sixth Jordanian Intern. Congress of Mathematics, 2005. Collection of Abstracts. Univ. Of Irbid. (Jordan) Press. - 2005.

97. Valette R. Analysis of Petri nets by stepwise refinements. //Journal of Computer and System Sciences. 1979. - № 18. - P. 35-46.

98. Valk R. and Vidal-Naquet G. Petri Nets and Regular Languages. // Journal of Computer and System Sciences. 1981. - № 23(3). - P. 299325.

99. H.M.W. Verbeek, T. Basten, and W.M.P. van der Aalst. Diagnosing workflow processes using Woflan. // The Computer Journal. 2001. -№ 44(4). - P. 246-279.

100. Vernadat. Enterprise Modeling and Integration. 1996.

101. Voorhoeve M. ExSpect Language Tutorial. Eindhoven: Endhoven University of Technology, 1998.

102. WfMC Glossary. // http://www.wfmc.org.