close

Вход

Забыли?

вход по аккаунту

?

Методика вероятностного прогнозирования состояния организационно-технологических систем при помощи формализмов GERT-сетей.

код для вставкиСкачать
На правах рукописи
Зырянов Антон Александрович
МЕТОДИКА ВЕРОЯТНОСТНОГО ПРОГНОЗИРОВАНИЯ
СОСТОЯНИЯ ОРГАНИЗАЦИОННОТЕХНОЛОГИЧЕСКИХ СИСТЕМ ПРИ ПОМОЩИ
ФОРМАЛИЗМОВ GERT-СЕТЕЙ
Специальность: 05.13.06 – Автоматизация и управление
технологическими процессами и производствами (промышленность)
АВТОРЕФЕРАТ
диссертации на соискание ученой степени
кандидата технических наук
Красноярск 2013
Работа выполнена в Федеральном государственном бюджетном
образовательном учреждении высшего профессионального образования
«Сибирском
государственном
технологическом
университете»,
г. Красноярск
Научный руководитель:
кандидат
технических
наук,
Доррер Михаил Георгиевич
доцент
Официальные оппоненты:
Мурыгин Александр Владимирович
доктор технических наук, профессор,
ФГБОУ ВПО «Сибирский государственный
аэрокосмический
университет
имени
академика М. Ф. Решетнева», г. Красноярск
заведующий кафедрой информационноуправляющих систем
Дмитриев Михаил Геннадьевич
доктор
физико-математических
наук,
профессор, «Институт системного анализа
РАН», г. Москва, главный научный
сотрудник
Ведущая организация:
ФГАОУ ВПО «Южный федеральный
университет», г. Ростов-на-Дону
Защита состоится 27 сентября 2013 года в 14:00 на заседании
диссертационного совета Д 212.249.02, созданного на базе Сибирского
государственного аэрокосмического университета имени академика
М. Ф. Решетнева, по адресу: 660014, г. Красноярск, просп. им. газ.
«Красноярский рабочий», 31.
С диссертацией можно ознакомиться в научной библиотеке Сибирского
государственного
аэрокосмического университета имени академика
М. Ф. Решетнева.
Автореферат разослан 25 июля 2013 г.
Учѐный секретарь
диссертационного совета
Кузнецов
Александр Алексеевич
2
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность. В настоящее время возрастающая конкуренция в
экономике, требующая высокого темпа изменений в организации и предельной
эффективности, диктует новые требования к управлению организацией. Ответом
на эти требования в XX – XXI веках явилось появление целого комплекса
принципиально новых подходов к организационному управлению и
автоматизации, опирающихся на управление в разрезе бизнес-процессов.
Возрастающая
сложность
задач
управления
организационнотехнологическими системами, необходимость обработки большого объема
информации при заданном уровне точности и высокой трудоемкости,
оптимизации систем и прогнозирования ее состояний требуют развития
инструментов интеллектуальной поддержки процессов управления и
автоматизации управления. Однако автоматизированные решения по интеграции
фаз жизненного цикла управления бизнес-процессами в единую систему сбора и
обработки данных и оперативного управления с целью повышения
эффективности функционирования системы в настоящее время недостаточно
разработаны.
Для решения данной научной задачи необходимо разработать модели и
структурные решения человеко-машинных систем, предназначенных для
автоматизации производства и интеллектуальной поддержки процессов
управления и необходимой для этого обработки данных в организационнотехнологических системах управления.
Анализ работ по теме исследования выявил ряд существенных проблем,
возникающих на пути решения данной задачи. Фаза моделирования жизненного
цикла
управления
бизнес-процессами,
в
ходе
которой
создается
высокоуровневая модель, состоящая из задач, вызывает следующие проблемы:
неточность и субъективность при построении структуры модели системы;
сложности при сборе и оценке значений показателей бизнес-процессов из
систем учета (в том числе автоматизированных), не ориентированных на
процессное управление.
Фаза имитационного моделирования и анализа, содержанием которой
является построение прогноза состояния бизнес-системы на основе истории
накопленных метрик (измеримых параметров), ставит аналитиков перед
необходимостью решать целый ряд серьезных проблем. К их числу относятся:
высокая трудоемкость прогноза параметров системы при помощи
существующих средств имитационного моделирования;
вычислительная
сложность
имитационного
эксперимента,
экспоненциально возрастающая с ростом числа развилок в ходе процесса.
Анализ работ по применению GERT-сетей для построения прогноза
состояния системы, взамен имитационного эксперимента, выявил ряд
существенных проблем:
при моделировании систем достаточно часто требуется использовать узел,
соответствующий логической функции «ИЛИ» по разветвлению, а между
тем задача моделирования такого узла GERT-сети является не только не
решенной, но и не поставлена ни в одной из изученных работ;
3
существующие
методы
расчета
GERT-сетей,
основанные
на
использовании топологического уравнения Мейсона, имеют высокую
трудоемкость;
не производилась оценка прогностической способности GERT-сетей ни
для одного из классов систем.
В работе предлагается решать проблему точности и объективности
построения структуры модели системы за счет использования технологии
анализа процессов (Process mining), оценку параметров ресурсной
эффективности бизнес-процессов предлагается решить за счет реализации
системы оперативного учета, ориентированной на бизнес-процессы, а проблему
высокой трудоемкости прогноза параметров системы предлагается решать за
счет использования аппарата GERT-сетей взамен «многопроходного»
имитационного эксперимента.
В целом, актуальность темы диссертационной работы заключается в
решении комплекса вопросов по созданию автоматизированной методики
вероятностного прогнозирования состояния организационно-технологических
систем на основе математического, информационного и алгоритмического
обеспечения систем управления автоматизированными технологическими
процессами и производствами.
Объект исследования – организационно-технологическая система,
описанная бизнес-процессами.
Предмет исследования – средства идентификации и формализации
организационно-технологических систем и алгоритмы
автоматизации
интеллектуальной поддержки процессов управления.
Цель работы – разработка методики вероятностного прогнозирования
состояния
организационно-технологической
системы,
обеспечивающей
повышение точности и объективности исследования структуры модели системы
за счет применения технологии аналитической обработки процессов (Process
mining) и учета в разрезе бизнес-процессов, и снижение трудоемкости прогноза
параметров системы без потери точности по сравнению с существующими
методами за счет применения математического аппарата GERT-сетей.
Задачи работы:
1. Разработать подход структурной и параметрической идентификации
дискретно-событийных моделей бизнес-процессов на основе учетных данных
автоматизированной системы управления (АСУ) с использованием технологии
аналитической обработки процессов (Process mining), включая методы
извлечения данных АСУ и методы построения журналов событий.
2. Разработать методику параметрической идентификации бизнеспроцессов на основе учетных данных АСУ, позволяющую оценивать ресурсную
эффективность каждого из бизнес-процессов системы.
3. Разработать
методику
GERT-сетевого
описания
системы,
представленной бизнес-моделями, полученными в результате аналитической
обработки процессов (Process mining) для прогнозирования и анализа состояния
системы, включающую: алгоритм трансляции модели бизнес-процессов в
модель GERT-сети, модель узла GERT-сети, описывающего разветвление хода
бизнес-процесса по логическому правилу ИЛИ (OR).
4
4. Разработать методику оценки числовых характеристик GERT-сети на
основе эквивалентных преобразований, позволяющую усовершенствовать
методы расчета GERT-сетей без использования топологического уравнения
Мейсона и вычисления производных по производящей функции моментов сети.
5. Оценить прогностическую способность разработанной методики и
провести экспериментальную проверку корректности разработанных методов и
алгоритмов
на
основе
данных
производственного
процесса
деревообрабатывающего производства.
Область
исследования.
Теоретические
основы
и
методы
математического моделирования организационно-технологических систем и
комплексов, функциональных задач и объектов управления и их
алгоритмизация.
Методы исследования. Для решения задач научного исследования
применены: процессный подход к управлению, методы общей теории систем и
теории управления, методы математического моделирования, теории
вероятностей и математической статистики, идентификации систем, теории
стохастических сетей.
На защиту выносятся следующие результаты:
1. Методика параметрической идентификации бизнес-процессов на
основе учетных данных АСУ.
2. Методика GERT-сетевого описания системы, представленной бизнесмоделями.
3. Методика оценки числовых характеристик GERT-сети на основе
эквивалентных преобразований.
Научная новизна:
1. Впервые применен подход структурной и параметрической
идентификации дискретно-событийных моделей бизнес-процессов на основе
учетных данных АСУ с использованием технологии аналитической обработки
процессов (Process mining), обеспечивающий повышение точности и
объективности исследования структуры модели и позволяющий перейти от
показателей системы к прогнозу состояния системы на основе GERT-сетей.
2. Разработана
методика
математического
моделирования
организационно-технологических систем, представленных бизнес-моделями, в
виде GERT-сети, включающая алгоритм трансляции модели бизнес-процессов в
модель GERT-сети, модель узла GERT-сети, описывающего разветвление хода
бизнес-процесса по логическому правилу ИЛИ (OR), позволяющая снизить
трудоемкость построения вероятностного прогноза параметров системы без
потери точности по сравнению с существующими методами.
3. Разработана методика оценки числовых характеристик GERT-сети
(математического ожидания и дисперсии) на основе эквивалентных
преобразований, преимущество которой заключается в аналитическом расчете
значений характеристик сети без потери точности и с меньшей трудоемкостью.
Практическая значимость:
1. Предложенные методы, математические модели и алгоритмы
позволяют: повысить точность и объективность исследования структуры и
значений показателей эффективности модели организационно-технологической
5
системы, описанной бизнес-процессами, и снизить трудоемкость прогноза
параметров системы без потери точности.
2. Разработан инструмент анализа процессов на примере широко
распространенной системы 1С: Предприятие 8 УПП: разработана методика
извлечения данных из АСУ и построения журнала событий (event log),
разработан подход к анализу бизнес-процесса производства деревянных
остекленных конструкций и оценена его эффективность на основе GERT-сетей.
3. Разработан инструмент параметрической идентификации бизнеспроцессов на основе учетных данных системы, позволяющий получать значения
показателей ресурсной эффективности бизнес-процессов системы из проводок
оперативного учета в 1С: Предприятие 8 УПП.
Достоверность полученных результатов и выводов обусловлена:
корректностью использования математических моделей; согласованностью
теоретических результатов с основными положениями теории вероятностей и
математической статистики; сравнением значений основных результатов с
известными
методами
математического
моделирования;
сравнением
полученного прогноза с фактическими значениями экспериментальной выборки
по прогнозируемому объекту.
Полученные результаты сравнивались с фактическими показателями
деятельности
организационно-технологических
систем
и
показали
достоверность и высокую прогностическую способность предложенной
методики.
Личный вклад автора. Все результаты диссертации получены лично
автором. Из публикаций, выполненных в соавторстве, в диссертацию включены
результаты, полученные лично автором.
Апробация работы. Результаты диссертационной работы докладывались
и обсуждались на 6 международных конференциях: Пятнадцатая международная
конференция по эвентологической математике и смежным вопросам «XV
ЭМ’2011», г. Красноярск, 2011; Одиннадцатая международная конференция по
финансово-актуарной
математике
и
эвентологии
безопасности
«XI
ФАМЭБ’2012», г. Красноярск, 2012 (2 доклада); Восьмая международная
научно-практическая конференция «Перспективы развития информационных
технологий», г. Новосибирск, 2012; Шестнадцатая международная конференция
по эвентологической математике и смежным вопросам «XVI ЭМ’2012», г.
Красноярск, 2012 (2 доклада); Одиннадцатая международная научнопрактическая
конференция
«Перспективы
развития
информационных
технологий», г. Новосибирск, 2013; Двенадцатая международная конференция
по финансово-актуарной математике и эвентологии безопасности «XII
ФАМЭБ’2013», г. Красноярск, 2013.
Публикации. Основное содержание диссертации отражено в 14
публикациях автора, из которых 5 статей в рецензируемых научных журналах и
изданиях.
Структура и объем работы. Диссертация состоит из введения, 4 глав,
заключения, списка используемых источников из 138 наименований. Общий
объем работы 146 страниц.
6
СОДЕРЖАНИЕ РАБОТЫ
Во введении представлена актуальность работы, цель исследования и
задачи, научная новизна и практическая значимость, структура и объем работы.
В первой главе проводится анализ предметной области и литературных
источников по теме диссертации. Рассмотрен процессный подход к управлению,
как один из актуальных и наиболее эффективных способов управления
организационно-технологическими системами.
Рассмотрены подходы к идентификации сложных организационнотехнологических
систем,
описанных
моделями
бизнес-процессов.
Проанализированы методы сбора и извлечения данных по бизнес-процессам из
АСУ.
Рассмотрены математические методы прогнозирования, оценки и анализа
бизнес-процессов с целью повышения эффективности управления системой,
включая сети Петри, цепи Маркова, альтернативные стохастические сети,
имитационное моделирование. Проанализированы возможности применения
GERT-сетей для исследования бизнес-процессов и существующие методы
расчета GERT-сетей.
Во второй главе описаны методы математического моделирования
организационно-технологических систем, модели и алгоритмы прогнозирования,
оценки и анализа бизнес-процессов, составляющие теоретическую основу
работы.
На рисунке 1 представлена модель системы управления. Объектом
управления является организационно-технологическая система, описанная
бизнес-процессами.
Рисунок 1 – Модель системы управления
На рисунке 1 представлены: f(t) – возмущающие воздействия; x(t) –
выходные воздействия; u(t) – управляющие воздействия; y(t) – фактические
значения показателей функционирования системы; z(t) – целевые значения
показателей.
В подсистеме оперативного управления (управление системой)
предложена схема, позволяющая автоматизировать построение прогноза
состояния системы (Рисунок 2). Данная схема является реализацией
разработанной методики вероятностного прогнозирования состояния
организационно-технологической системы, описанной бизнес-моделями.
Методика включает следующие этапы:
7
1. сбор данных о системе непосредственно из автоматизированной системы
управления (АСУ), поддерживающей ее бизнес-процессы;
2. структурная и параметрическая идентификация модели бизнес-процессов
на основе собранных данных с использованием технологии анализа
процессов (Process mining);
3. прогноз значимых параметров функционирования системы (например,
время выполнения процесса и его трудоемкость) на основе GERT-сетей.
Рисунок 2 – Схема автоматизации построения прогноза состояния системы
Для оценки параметров ресурсной эффективности бизнес-процессов
разработана методика параметрической идентификации бизнес-процессов на
основе учетных данных. Решение задачи параметрической идентификации
бизнес-процессов основано на сопоставлении учетных данных АСУ с моделью
бизнес-процессов.
Традиционно учет хозяйственных операций ведется таким образом, что
учетные данные не сопоставлены с выполняемыми бизнес-процессами. АСУ для
реализации методики не выстроена в соответствии с требованиями управления
на основе бизнес-процессов – данные о хозяйственных операциях не содержат
разреза бизнес-процессов.
Необходимо внести изменения в порядок учета организацией
хозяйственных операций – дополнить бизнес-операцию, отражающую факт
хозяйственной деятельности в АСУ, двумя аналитическими идентификаторами:
бизнес-процесс источник и бизнес-процесс приемник. Таким образом, учетные
данные будут иметь соответствующий разрез бизнес-процессов, а значение
параметра бизнес-операции будет соответствовать выходу одного процесса и
входу другого.
Агрегируя данные по однотипным параметрам в разрезе бизнес-процессов
можно получить их показатели. Таким образом, используя разработанную
методику можно перейти к показателям процессов и далее к показателям
эффективности (KPI). Разработанная методика реализована в программном
продукте 1С Предприятие 8.2 на базе конфигурации «Управление
производственным предприятием 8».
Для прогноза функционирования системы в работе используется аппарат
GERT-сетей. Главная идея GERT-сетей заключается в том, что дискретнособытийная модель представляется в виде ориентированного графа –
8
стохастической сети, состоящей из ребер (дуг) и узлов. Дуга
i, j
характеризуется законом распределения случайной величины Yij (или
нескольких величин), значимой для исследования – например, стоимости или
времени выполнения операции, а также вероятностью перехода pij из
предшествующего узла в следующий. Для задания закона распределения
случайной величины Yij удобнее использовать производящую функцию
моментов M ij (s) . Производящая функция для непрерывной случайной величины
для которой задана плотность распределения
равна
Yij ,
f ( yij ) ,
M ij ( s)
e
syij
величины
M ij ( s )
f ( yij )dyij . Производящая функция для дискретной случайной
Yij , для которой задана
e
syij
f ( y ij ) .
При
yij
условная вероятность
a const
производящая
f ( yij ) , равна
функция
равна
M ij ( s) e sa , в частности если a 0 , то M ij (s) 1 .
Узел определяет логику ветвления процесса, порядок выполнения ребер
(одновременно, по одному, в произвольной комбинации). Использование
операций над производящими функциями законов распределения величин на
ребрах и набора правил приведения к эквивалентному ребру позволяет вывести
функцию, характеризующую закон распределения требуемой величины для
завершающего узла (узлов) GERT-сети. Именно этот закон исчерпывающе
заменяет собой результаты исследования выходной величины методом
«многопроходного имитационного моделирования». Результатом использования
GERT-сетей, как правило, является вычисление значений переменных,
связанных с первыми моментами ( v1 и v 2 ) распределения выходной величины
относительно начала координат – математическое ожидание (1), дисперсия (2),
коэффициент асимметрии и эксцесса.
v1
2
2
v2
v12
s
[ M E ( s)] s
(1)
0
2
[ M E ( s )] s 0
[ M E ( s )] s 0
(2)
s
s2
Разработана методика GERT-сетевого описания бизнес-процессов,
которая позволит построить прогноз состояния системы. Методика отличается
от ранее предлагавшихся большей полнотой и систематичностью, а также
предусматривает реализацию описания развилки типа «ИЛИ».
В рамках GERT-сетевого описания бизнес-процессов предложен
алгоритм трансляции модели бизнес-процессов в GERT-сеть. Для описания
дискретно-событийной модели бизнес-процесса в работе используется нотация
ARIS eEPC (цепочка процесса, управляемого событиями). При первоначальной
формулировке алгоритма было найдено очевидное противоречие графических
нотаций ARIS eEPC и GERT – в eEPC-модели активным элементом,
обозначающим действие, является процесс (узел), а в GERT – дуга. Чтобы
преодолеть это противоречие, было решено сопоставлять с процессом eEPC не
одиночную дугу GERT-сети, а сочетание «узел+ребро». На уровне описаний
бизнес-процессов это соответствует связке «процесс+событие».
9
Пусть модель бизнес-процесса в нотации ARIS eEPC и модель GERT-сети
будут заданы каждая двумя матрицами инцидентности (инцидентность узлов с
дугами, инцидентность дуг с узлами). Каждая дуга eEPC-модели задана
вероятностью выполнения. У каждой функции бизнес-процесса задано значение
атрибута, соответствующего исследуемой величине (например, время
выполнения операции, затраты ресурсов на выполнение операции) или набор
значений за определенный период времени – история накопленных метрик
(измеримых параметров).
Алгоритм трансляции модели бизнес-процесса в GERT-сеть состоит из
следующих шагов:
1. Сопоставим каждому символу (функция/операция, событие, правило
ветвления/слияния)
eEPC-модели
STEOR-узел
(EORфункция/«исключающее ИЛИ» на входе и стохастическая функция на
выходе узла) GERT-сети.
2. Приравняем матрицы инцидентности eEPC-модели и GERT-сети.
3. Сопоставим правила слияния хода процесса в eEPC и в GERT-сети
(Таблица 1).
4. Сопоставим правила разветвления хода процесса в eEPC и в GERT-сети
(Таблица 1).
5. Определим вероятность выполнения дуг GERT-сети на основе дуг eEPC.
6. Определим плотность вероятности для дуг GERT-сети.
Таблица 1 – Принципы сопоставления правил слияния/разветвления
Тип правила
eEPC-модели
Слияние хода
процесса по
правилу
Разветвление
хода
процесса по
правилу
Символ
eEPC-модели
AND Rule
OR Rule
XOR Rule
AND Rule
OR Rule
XOR Rule
Узел GERT-сети
С входной AND-функцией
С входной IOR-функцией
С входной EOR-функцией
С детерминированной выходной функцией
Нет прямого решения в аппарате GERT,
предлагаемое решение приведено ниже
Со стохастической выходной функцией
Логическая операция
Логическое И
Включающее ИЛИ
Исключающее ИЛИ
Логическое И
Включающее ИЛИ
Исключающее ИЛИ
Существует два подхода для определения плотности распределения дуги
GERT-сети. Первый – для всех функций модели eEPC принимается один закон
распределения с такими параметрами, чтобы средние значения исследуемой
величины функций бизнес-процесса соответствовали математическому
ожиданию (например, Голенко-Гинзбург доказывает, что в предельном случае
время выполнения операции в организационно-технологической системе
подчиняется бета-распределению), второй – для каждой дуги производится
идентификация закона распределения по выборке (история накопленных
метрик).
Выходная функция, моделирующая выход по логическому правилу
«ИЛИ», в математическом аппарате GERT-сетей отсутствует. Задачу
моделирования данной функции решим с использованием существующих узлов
GERT-сети, не прибегая к вводу новых узлов или модификации аппарата GERTсетей. В работе предложена модель узла GERT-сети, описывающая
разветвление хода процесса по логическому правилу «ИЛИ».
10
На рисунке 3, a представлен бизнес-процесс с правилом разветвления
(элемент S2) по логическому «ИЛИ», на рисунке 3, б представлена
соответствующая ему модель GERT-сети. События A и B (Рисунок 3, a) –
независимые.
Рисунок 3 – Моделирование по логическому ИЛИ
Узел GERT-сети v1 (Рисунок 3, б) соответствует функции F (Рисунок 3, a)
бизнес-процесса, узел v5 – событию A, узел v8 – событию B. Вероятности
выполнения дуг равны: p1 0,8 , q1 0,2 , p2 0,5 , q 2 0,5 . При этом p1 q1 1,
p2 q2 1 . Подсеть M – модель узла GERT-сети, описывающая разветвление
хода процесса по логическому правилу ИЛИ.
К преимуществам предложенной модели (Рисунок 3, б) можно отнести:
компактное отображение GERT-сети; независимость срабатывания дуг по
разветвлению; срабатывание хотя бы одной из дуг по разветвлению.
v2 , v3 ,
v2 , v6 ,
v3 ,v4 ,
v6 , v7 ,
v3 ,v7 ,
v6 , v4
Дуги:
являются «холостыми» – на них не выполняется работа. Функционирование
предложенной модели (Рисунок 3, б) основано на активации дуг v2 , v3 и
v2 , v6 , выходящих из узла v 2 с вероятностью равной 1. Таким образом,
происходит активация узлов v3 и v 6 , которые имеют независимые
стохастические выходные функции, обеспечивающие активацию: только узла
v5 , только узла v8 , узлов v5 и v8 одновременно, что соответствует таблице
истинности логического оператора «ИЛИ».
Вероятности
событий
равны:
P( A) P(v5 ) p1 * q 2 ,
P( B) P(v8 ) p2 * q1 , P( A B) P(v5 , v8 ) p1 * p 2 q1 * q 2 .
Для того, чтобы преодолеть проблему высокой трудоемкости расчета
GERT-сети с использованием топологического уравнения Мейсона, в работе
предложена методика оценки числовых характеристик GERT-сети на основе
эквивалентных
преобразований,
включающая
формулы
пересчета
математического ожидания и дисперсии для трех базовых преобразований дуг
GERT-сети и алгоритм эквивалентных преобразований однородной GERT-сети.
Суть методики состоит в следующем. Даны две дуги GERT-сети,
характеризующиеся случайными величинами X 1 и X 2 , у которых заданы:
производящая функция моментов M i (s) , математическое ожидание M [ X i ] и
дисперсия D[ X i ] . Поскольку GERT-сеть может быть заменена одной
эквивалентной дугой, следовательно, может быть найдена случайная величина
11
Y,
характеризующая выходную величину GERT-сети. Известно, что
производящие функции моментов для трех базовых эквивалентных
преобразований дуг имеют следующую форму:
Последовательные дуги:
M E ( s)
WE ( s) / pE
p1M1 ( s) p2 M 2 ( s)
p1 p2
M1 ( s ) M 2 ( s )
(3)
Параллельные дуги:
M E ( s)
WE ( s) / pE
p1M1( s)
p1
p2 M 2 ( s)
p2
(4)
Дуга и петля:
(1 p2 ) M1 ( s)
(5)
1 p2 M 2 ( s)
Необходимо найти числовые характеристики M [Y ] и D[Y ] случайной
величины Y GERT-сети равной комбинации случайных величин X 1 и X 2 для
M E ( s)
WE ( s) / pE
p1M1 ( s) 1 p2
1 p2 M 2 ( s)
p1
трех базовых эквивалентных преобразования дуг. При этом числовые
характеристики M [Y ] и D[Y ] должны быть найдены в аналитическом виде через
комбинацию соответствующих M [ X i ] и D[ X i ] случайных величин X 1 и X 2 .
Решение задачи нахождения числовых характеристик GERT-сети без
использования топологического уравнения Мейсона (6) и вычисления частных
производных основывается на преобразовании GERT-сети к эквивалентной дуге
с пересчетом числовых характеристик случайных величин дуг.
H 1
T ( L1 )
T ( L2 )
T ( L3 ) ... ( 1) m T ( Lm ) 0
(6)
Предложены формулы нахождения числовых характеристик для трех
базовых преобразований дуг GERT-сети.
Последовательные дуги:
(7)
M [Y ] M [ X 1 ] M [ X 2 ]
(8)
D[Y ] D[ X 1 ] D[ X 2 ]
Параллельные дуги:
M [Y ]
D[Y ]
p1D[ X1]
p1
p1 M [ X 1 ]
p1
p2 D[ X 2 ]
p2
p2 M [ X 2 ]
p2
(9)
p1 p2 ( M [ X1] M [ X 2 ]) 2
p1
p2 2
(10)
Дуга и петля:
p2
M[X 2 ]
1 p2
p2
p2
D[Y ] D[ X 1 ]
D[ X 2 ]
( M [ X 2 ]) 2
2
1 p2
( p 2 1)
M [Y ] M [ X 1 ]
(11)
(12)
Формулы (7–12) получены путем аналитического вычисления частных
производных (1) и (2), по производящим функциям моментов (3-5) для
эквивалентной дуги GERT-сети для трех базовых преобразований дуг.
В рамках реализации методики предложен алгоритм преобразования
однородной GERT-сети к эквивалентной дуге, основанный на поиске
12
участков сети с тремя типами расположения дуг и их замене на эквивалентную
дугу с пересчетом математического ожидания и дисперсии по предложенным
формулам (7–12), а также вероятности выполнения дуги. Общий ход алгоритма
представлен на рисунке 4.
Структуру GERT-сети G отобразим в матрице смежности A(G) с n
вершинами. Каждый элемент матрицы a ij , для которого aij 1 , содержит
вероятность pij выполнения дуги
(i – номер строки, j – номер столбца,
i, j
i, j 1, n ) и значения математического ожидания M [ X ij ] и дисперсии D[ X ij ] .
Рисунок 4 - Схема алгоритма преобразования GERT-сети
Трудоемкость и емкостная сложность алгоритма. Размер входных
данных характеризуется числом узлов n GERT-сети. Асимптотическая
сложность алгоритма есть O(n 3 ) . Емкостная сложность алгоритма есть O(n 2 ) .
В третьей главе представлено описание экспериментального объекта.
13
В настоящее время современное деревообрабатывающее предприятие
является лидером по производству различных изделий из дерева широкого
потребления. На рынке представлены различные пиломатериалы разной степени
обработки, клееные изделия из древесины, древесные плиты, полуфабрикаты из
древесины и др. Производство данных изделий не возможно без современного
дорогостоящего оборудования и грамотно построенного производственного
процесса.
Одним из развивающихся и актуальных направлений в деревообработке
является производство деревянных остекленных конструкций. Данные изделия
являются
конкурентной
альтернативой
конструкциям
из
ПВХ
(поливинилхлорид) и алюминия со стеклопакетом.
В качестве экспериментального объекта был выбран бизнес-процесс
производства
деревянных
остекленных
конструкций
одного
из
деревообрабатывающих
предприятий.
Однако,
как
и
на
многих
деревообрабатывающих
предприятиях
при
производстве
деревянных
остекленных конструкций существуют значительные потери (потери времени,
финансовые и ресурсные потери), что напрямую сказывается на эффективности
производства и всего предприятия. Таким образом, актуальным является
исследование данного производства с целью его оптимизации и повышения
эффективности функционирования, а также автоматизации процессов
управления.
Учетные данные о функционировании производства хранятся в АСУ 1С:
Предприятие 8 УПП, которое технически позволяет накапливать информацию
обо всех операциях, производимых на производстве. Таким образом, существует
возможность извлечения накопленных учетных данных из АСУ по выполнению
процесса, позволяющая идентифицировать производственный процесс на основе
технологии Process mining и исследовать данный класс систем.
Приводится описание процесса производства деревянных остекленных
конструкций, описание 1С: Предприятие 8 и накопленных данных по
выполнению процесса. Разработан метод извлечения данных из 1С: Предприятие
8 УПП и метод построения журналов событий (event log), на основе которых
были извлечены данные из АСУ по исследуемому процессу.
В четвертой главе рассмотрено практическое применение методики
построения
вероятностного
прогноза
состояния
организационнотехнологической системы.
Задача построения системы хозяйственного учета в разрезе бизнеспроцессов, позволяющей оценивать ресурсную эффективность каждого из
бизнес-процессов, проверена на данных АСУ 1С: Предприятие 8, собранных в
ходе выполнения проекта повышения эффективности одной из оптовых
генерирующих компаний рынка электрической энергии (ОГК).
Поставлен эксперимент по прогнозу числовых характеристик бизнеспроцесса производства деревянных остекленных конструкций на основе его
GERT-сетевого описания.
Был идентифицирован процесс производства деревянных остекленных
конструкций (Рисунок 5, а) на основе технологии анализа процессов (Process
mining) и программного продукта ProM 6, в который был импортирован журнал
14
событий (event log), сформированный на основе данных из АСУ, полученных в
третьей главе, по выполнению производственного процесса. На рисунке 5, б
представлен бизнес-процесс в нотации ARIS eEPC. С помощью разработанного
алгоритма трансляции модели бизнес-процесса в GERT-сеть получено GERTсетевое описание бизнес-процесса производства деревянных остекленных
конструкций (Рисунок 5, в). В таблице 2 приведены обозначения
соответствующих моделей (Рисунок 5).
Рисунок 5 – Модели производственного процесса
Для бизнес-процесса производства деревянных остекленных конструкций
интересным является исследование двух параметров – время выполнения
операций (трудоемкость процесса) и общее время выполнения процесса,
включая время ожидания между операциями. Тогда необходимо рассчитать две
GERT-сети, которые имеют одну структуру, представленную на рисунке 5, в.
Первая GERT-сеть для трудоемкости процесса, вторая для общего времени
выполнения процесса.
15
Таблица 2 – Обозначения соответствующих моделей
Операция процесса
– (стартовое состояние)
Процесс в ProM 6
m1
m2
Проектирование изделия
m3
Комплектация заказа ТМЦ
m4
Изготовление деталей изделия
m5
Сборка конструкций
m6
Остекление (запакетка)
m7
Приемка изделия ОТК
m8
Перемещение изделия на СГП
m9
Внутреннее перемещение изделия
на СГП
Изготовление стеклопакета
Доставка
Монтаж
– (конечное состояние)
ARIS eEPC
ev1
s2
s3
s4
s5
s6
s7
s8
s9
GERT-сеть
v1
<v2,vk>
<v3,vk>
<v4,vk>
<v5,vk>
<v6,vk>
<v7,vk>
<v8,vk>
<v9,vk>
s12, s13
s10
s11
ev22
<v12,vk>, <v13,vk>
<v10,vk>
<v11,v13>
v14
m12, m13
m10
m11
m14
Расчет GERT-сетей для трудоемкости и для общего времени выполнения
процесса проводился на основе трех методов: на основе уравнения Мейсона, с
помощью разработанной методики оценки числовых характеристик на основе
эквивалентных преобразований, с помощью «многопроходного» имитационного
эксперимента в AnyLogic. Результаты расчетов приведены в таблице 3.
Таблица 3 – Результаты расчетов GERT-сетей
Величина
Метод расчета
Трудоемкость Уравнение Мейсона
процесса
На основе эквивалентных
преобразований
Имитационный эксперимент
Общее время Уравнение Мейсона
выполнения На основе эквивалентных
процесса
преобразований
Имитационный эксперимент
Мат. ожидание
Дисперсия
Значение Погрешность Значение Погрешность
часы
%
часы2
%
11,115
5,28
11,12
0,04
5,294
0,273
11,125
266,889
266,924
0,086
0,013
5,331
10445
10448
0,971
0,029
266,939
0,019
10459
0,135
Результаты
расчетов
(Таблица
3)
показывают
адекватность
разработанного аналитического метода оценки числовых характеристик
(математического ожидания и дисперсии) на основе эквивалентных
преобразований GERT-сети по сравнению с известными методами – расчет
GERT-сети на основе уравнения Мейсона, имитационный эксперимент.
На рисунке 6 представлены характеристики (1 – плотность вероятности, 2
– функция распределения) GERT-сети для трудоемкости, на рисунке 7 – для
общего времени выполнения, полученные с помощью имитационного
эксперимента в AnyLogic.
Значения погрешности математического ожидания и дисперсии (Таблица
3) рассчитаны в сравнении с результатами, полученными на основе уравнения
Мейсона, и показывают весьма близкие результаты расчетов – не более 1 %. Для
имитационного
эксперимента
было
проведено
10
дополнительных
экспериментов по каждой модели – погрешность для математического ожидания
не превышала 1 %, а для дисперсии – 3 %. При этом имитационный эксперимент
является более трудоемким для решения данной задачи.
16
Рисунок 6 – Характеристики GERT-сети для трудоемкости процесса
Рисунок 7 – Характеристики GERT-сети для продолжительности процесса
Таким образом, для задачи расчета числовых характеристик GERT-сетей
предпочтительно использовать разработанную методику оценки на основе
эквивалентных преобразований сети, поскольку данная методика отличается от
существующих тем, что позволяет отказаться от использования топологического
уравнения Мейсона и вычисления производных по производящей функции
моментов сети. При этом преимущество в отличие от существующих методов
для данного класса задач заключается в аналитическом расчете значений
характеристик сети без потери точности и с меньшей трудоемкостью.
Произведена оценка прогностической способности GERT-сетевого
моделирования бизнес-процессов (Таблица 4) на основе сравнения результатов
расчета (Таблица 3) GERT-сетей с численными характеристиками выборки.
Для анализа полученных значений погрешности (Таблица 4) проведено
сравнение
числовых
характеристик
идентифицированных
законов
распределения с выборочными характеристиками по каждой операции для
трудоемкости процесса. Анализ показал, что математическое ожидание и
дисперсия имеют малую погрешность, следовательно законы распределения
случайных величин GERT-сети идентифицированы достаточно точно. Тем не
17
менее, погрешность прогноза может также быть связана с точностью
восстановления топологии модели.
Таблица 4 – Сравнение результатов расчета
Величина
Метод расчета
Мат. ожидание
Дисперсия
Значение Погрешность Значение Погрешность
мин.
%
мин.2
%
Трудоемкость Выборочные характеристики
10,89
3,38
процесса
Уравнение Мейсона
11,12
2,11
5,294
56,63
На основе эквивалентных
11,125
2,16
5,331
57,72
преобразований
Общее время Выборочные характеристики 254,369
6605
выполнения Уравнение Мейсона
266,924
4,94
10448
58,18
процесса
На основе эквивалентных
266,939
4,94
10459
58,35
преобразований
Оценка прогностической способности GERT-сетевого моделирования
бизнес-процессов показала высокую предсказательную способность для
математического ожидания (погрешность не более 5 %), однако необходимо
проведение дополнительного исследования для оценки влияния различных
факторов на значения числовых характеристик (в частности дисперсии)
выходной величины GERT-сети.
Анализ бизнес-процесса производства деревянных остекленных
конструкций на основе GERT-сетей показал:
трудоемкость процесса (11,12 часов) в общем времени выполнения
(266,924 часов) занимает 4 %, что соответствует результатам для других классов
бизнес-процессов, где время суммарного ожидания между операция составляет
80-98 % времени процесса;
высокая вероятность (2-10 %) на дугах обратных связей говорит о
достаточно большом количестве брака на разных производственных этапах.
Модель GERT-сети может быть использована для оптимизации процесса.
Структурная оптимизация GERT-сети (Рисунок 5, в) возможна в уменьшении
вариативности бизнес-процесса, параметрическая оптимизация – в направлении
уменьшения вероятностей на петлях обратных связей (брак при выполнении
операций). Данные действия невозможны без регламентации процесса и
принятия
управленческих
решений,
направленных
на
проведение
организационных мероприятий по оптимизации производственного процесса, и
следовательно повышения эффективности производства.
Для оценки принятия решений об оптимизации производственного
процесса необходимо знать эффект от оптимизации. Для этого произведены
расчеты GERT-сети (Таблица 5), в которых уменьшена вероятность на дугах
обратных связей в сторону целевых значений – числовые характеристики
процесса без брака (величина брака равна 0 %).
В случае уменьшения брака на производственных этапах (Таблица 5), где
был брак 10 %, на 5 % и на 2 %, где был брак 5 %, эффект от оптимизации
составит: сокращение времени производственных этапов на 2,45 %, сокращение
общей продолжительности процесса на 8,53 %. Таким образом, предложен
подход к оценке эффективности оптимизации производственного процесса на
18
основе GERT-сетей с меньшей трудоемкостью по сравнению с известными
методами при заданной точности результатов.
Таблица 5 – Оценка оптимизации модели производственного процесса
Величина
Состояние
системы
Трудоемкость Текущее
процесса
Оптимизация
Целевое
Общее время Текущее
выполнения
Оптимизация
процесса
Целевое
Мат. ожидание
Значение
Погрешность
часы
%
11,12
10,847
2,45
9,926
10,74
266,924
244,158
8,53
208,218
21,99
Дисперсия
Значение
Погрешность
2
часы
%
5,294
4,39
17,08
0,056
98,94
10448
5593,137
46,47
298,111
97,15
Применение на практике новых научных результатов, полученных при
проведении исследования, на примере бизнес-процесса производства
деревянных остекленных конструкций позволяет: построить прогноз для нового
варианта выполнения процесса, провести анализ процесса и его показателей,
оценить эффективность процесса, выявить пути для оптимизации структуры и
параметров выполнения процесса, провести оценку эффективности
оптимизации, провести оперативный мониторинг статистических показателей
при накоплении достаточной истории метрик.
В заключении представлены основные результаты исследования и
выводы на основе экспериментальных данных.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ
В результате проведенных исследований разработана методика
вероятностного прогнозирования состояния организационно-технологической
системы, обеспечивающая повышение точности и объективности исследования
структуры модели системы за счет применения технологии аналитической
обработки процессов (Process mining) и снижение трудоемкости исследования
системы без потери точности по сравнению с существующими методиками за
счет применения математического аппарата GERT-сетей.
Поставленная цель достигнута, решены следующие задачи:
1. Разработан подход структурной и параметрической идентификации
дискретно-событийных моделей бизнес-процессов на основе учетных данных
автоматизированной системы управления (АСУ) с использованием технологии
аналитической обработки процессов (Process mining), включая методы
извлечения данных АСУ и методы построения журналов событий.
2. Разработана методика параметрической идентификации бизнеспроцессов на основе учетных данных АСУ, позволяющая оценивать ресурсную
эффективность каждого из бизнес-процессов системы.
3. Разработана
методика
GERT-сетевого
описания
системы,
представленной бизнес-моделями, полученными в результате аналитической
обработки процессов (Process mining) для прогнозирования и анализа состояния
системы, включающая: алгоритм трансляции модели бизнес-процессов в модель
GERT-сети, модель узла GERT-сети, описывающего разветвление хода бизнеспроцесса по логическому правилу ИЛИ (OR).
19
4. Разработана методика оценки числовых характеристик GERT-сети на
основе эквивалентных преобразований, позволяющая усовершенствовать
методы расчета GERT-сетей без использования топологического уравнения
Мейсона и вычисления производных по производящей функции моментов сети.
5. Оценена прогностическая способность разработанной методики и
проведена экспериментальная проверка корректности разработанных методов и
алгоритмов
на
основе
данных
производственного
процесса
деревообрабатывающего производства.
Дальнейшая работа может проводиться в следующих направлениях:
проверка чувствительности моментов к различным параметрам GERTсети (вероятности дуг, законы и параметры распределения случайных величин
дуг) с выходом на рекомендации по оптимизации модели в целом;
проверка практической применимости аппарата GERT-сетей для других
аддитивных параметров – вероятностно-ресурсные характеристики: движение
ресурсов, в том числе денег, загрузка исполнителей;
разработка методов расчета произвольных GERT-сетей для
вероятностно-временных и вероятностно-ресурсных характеристик.
ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ
Статьи в журналах из перечня ВАК
1. Зырянов А.А. Прогноз динамики событийных моделей бизнеспроцессов на основе GERT-сетей / М.Г. Доррер, А.А. Зырянов //
Информатизация и связь, 2012. – №7. – С. 124–127.
2. Зырянов А.А. Алгоритм трансляции модели бизнес-процессов в
модель GERT-сети / А.А. Зырянов, М.Г. Доррер // Вестник КрасГАУ. –
Красноярск: КрасГАУ, 2012. – №12. – С. 13–18.
3. Зырянов А.А. Модель узла GERT-сети, описывающая разветвление
хода бизнес-процесса по логическому «ИЛИ» // Хвойные бореальной зоны. –
Красноярск: СибГТУ, 2012. - №5-6. – С. 25–29.
4. Зырянов А.А. Оценка показателей бизнес-процессов на основе GERTсетей / А.А. Зырянов, М.Г. Доррер // Хвойные бореальной зоны. – Красноярск:
СибГТУ, 2012. - №5-6. – С. 57–63.
5. Зырянов А.А. Структурная и параметрическая идентификация модели
бизнес-процессов деревообрабатывающего предприятия на основе учетных
данных автоматизированной системы управления / М.Г. Доррер, А.А. Зырянов,
А.А. Яровая // Хвойные бореальной зоны. – Красноярск: СибГТУ, 2011. - №3-4.
– С. 357–366.
Публикации в сборниках научных трудов
6. Зырянов А.А. Расчет числовых характеристик однородной GERT-сети
на основе эквивалентных преобразований // Труды XII международной
ФАМЭБ'2013 конференции. – Красноярск: СФУ, НИИППБ, 2013. – С. 175–180.
7. Зырянов А.А. Идентификация и прогноз функционирования модели
бизнес-процессов дистанционного обучения / М.Г. Доррер, А.А. Зырянов, Е.А.
Ланцев // Труды XII международной ФАМЭБ'2013 конференции. – Красноярск:
СФУ, НИИППБ, 2013. – С. 163–168.
20
8. Зырянов А.А. Методика расчета числовых характеристик однородной
GERT-сети // Перспективы развития информационных технологий: сборник
материалов XI Межд. научно-практической конференции. – Новосибирск:
СИБПРИНТ, 2013. – С. 21–27.
9. Зырянов А.А. Узел GERT-сети, описывающий разветвление хода
бизнес-процесса по логическому ИЛИ // Труды XVI международной ЭМ'2012
конференции. – Красноярск: СФУ, НИИППБ, 2012. – С. 106–110.
10. Зырянов А.А. Прогноз бизнес-процесса разработки медиапродукта на
основе GERT-сети / Е.В. Касьянова, А.А. Зырянов // Труды XVI международной
ЭМ'2012 конференции. – Красноярск: СФУ, НИИППБ, 2012. – С. 111–115.
11. Зырянов А.А. Прогноз поведения бизнес-процессов на основе GERTсетей // Перспективы развития информационных технологий: сборник
материалов VIII Межд. научно-практической конференции. – Новосибирск:
СИБПРИНТ, 2012. – С. 25–34.
12. Зырянов А.А. Трансляция модели бизнес-процессов в нотации ARIS
eEPC в GERT-сеть / А.А. Зырянов, М.Г. Доррер // Труды XI международной
ФАМЭБ'2012 конференции. – Красноярск: НИИППБ, СФУ, 2012. – С. 186–192.
13. Зырянов А.А. Расчет вероятностных характеристик бизнес-процессов
на основе GERT-сетей / А.А. Зырянов, М.Г. Доррер // Труды XI международной
ФАМЭБ'2012 конференции. – Красноярск: НИИППБ, СФУ, 2012. – С. 192–198.
14. Зырянов А.А. Определение показателей бизнес-процессов на основе
анализа событий хозяйственной деятельности предприятия / А.А. Зырянов, М.Г.
Доррер // Труды XV международной ЭМ'2011 конференции. – Красноярск: СФУ,
НИИППБ, КГТЭИ, 2011. – С. 96–99.
Зырянов Антон Александрович
Методика вероятностного прогнозирования состояния организационнотехнологических систем при помощи формализмов GERT-сетей
Автореферат
Подписано в печать
Формат 60×84/16. Бумага писчая. Печ. л. 1.0
Тираж 100 экз. Заказ № ________
Отпечатано в отделе копировальной и множительной техники СибГАУ
660014 г. Красноярск, пр. им. газеты «Красноярский рабочий», 31
21
1/--страниц
Пожаловаться на содержимое документа