Содержание к диссертации
Введение
ГЛАВА 1. Анализ методов сетевого планирования и управления в распределенных информационных системах 13
1.1 Правила и особенности составления сетевого графика событий .13
1.1.1 Общие понятия 13
1.1.2 Порядок составления сетевого графика 17
1.2 Исследование современных информационных систем, осуществляющих построение и работу с сетевыми графиками 20
1.3 Анализ существующих методов оценки и пересмотра временных характеристик сетевых моделей 30
1.3.1 Метод оценки сетевого графика по системе PERT 31
1.3.2 Метод оценки сетевого графика по системе GERT .33
1.3.3 Метод оценки сетевого графика по системе PRINCE2
1.4 Формальная постановка задачи исследования 39
1.5 Выводы по главе 40
ГЛАВА 2. Метод децентрализованного управления временными параметрами сетевых графиков множества автономных интеллектуальных агентов 42
2.1 Анализ и выбор методологического аппарата для решения задачи оценивания вероятностно-временных характеристик сетевого графика со случайными длительностями работ .42
2.2 Метод децентрализованного управления временными параметрами сетевых графиков множества автономных интеллектуальных агентов распределенной системы обработки информации и управления 48
2.3 Выводы по главе 65
ГЛАВА 3. Алгоритм формирования локальных сетевых графиков множеством автономных интеллектуальных агентов 67
3.1 Анализ существующих алгоритмов пересмотра и формирования сетевых планов .67
3.2 Алгоритм формирования локальных сетевых графиков множеством автономных интеллектуальных агентов, учитывающих возникновение коллизий в процессе сетевого планировании и управления 74
3.3 Оценка корректности разработанного алгоритма .87
3.4 Выводы по главе 89
ГЛАВА 4. Экспериментальное оценивание эффективности метода децентрализованного управления временными параметрами сетевых графиков множества автономных интеллектуальных агентов 90
4.1 Выбор имитационной среды для моделирования системы децентрализованного управления процессом сетевого планирования 90
4.2 Разработка имитационной модели системы децентрализованного управления процессом сетевого планирования, основанной на аппарате сетевого моделирования стохастических процессов .92
4.3 Проверка адекватности разработанной имитационной модели 98
4.4 Экспериментальное исследование разработанного метода децентрализованного управления временными параметрами сетевых графиков множества автономных интеллектуальных агентов .103
4.5 Выводы по главе 107
Заключение 108
Список терминов, сокращений и условных
Обозначений. 111
Список использованных источников
- Исследование современных информационных систем, осуществляющих построение и работу с сетевыми графиками
- Метод децентрализованного управления временными параметрами сетевых графиков множества автономных интеллектуальных агентов распределенной системы обработки информации и управления
- Алгоритм формирования локальных сетевых графиков множеством автономных интеллектуальных агентов, учитывающих возникновение коллизий в процессе сетевого планировании и управления
- Разработка имитационной модели системы децентрализованного управления процессом сетевого планирования, основанной на аппарате сетевого моделирования стохастических процессов
Введение к работе
Актуальность темы
Одной из актуальных проблем современных распределенных систем обработки информации и управления, реализующих сложные многоэтапные проекты, является согласование сроков выполнения последовательности их этапов. При этом, в случае централизованного управления, координация действий подсистем, ответственных за каждый из этапов, реализуется в рамках единого информационного пространства, обеспечивающего их взаимодействие (рис. 1).
Управление
сетевым
Время
Рисунок 1 – Координация действий исполнителей этапов при централизованном способе
управления
Однако, в ряде случаев, возможность использования схемы с централизованным управлением отсутствует. Это означает, что подсистемы, ответственные за каждый из этапов, функционируют автономно. Примерами подобных распределенных систем являются системы управления: логистикой в территориально-распределенных промышленных и торговых комплексах, поддержки выездных мероприятий и/или операций в интересах охраны и при возникновении чрезвычайных ситуаций, координации действий подвижных объектов, таких как беспилотные летательные аппараты или специализированные роботы. Особенностью подобных систем является использование агентно-ориентированного подхода, согласно которому их подсистемы представлены совокупностью интеллектуальных агентов.
Традиционно задачи согласования сроков выполнения последовательности этапов сложных проектов решаются в рамках теории сетевого планирования и управления (СПУ), представляющей указанную последовательность в виде специальной структуры, именуемой сетевым графиком – динамической моделью процесса реализации проекта. Наиболее известным методологическим аппаратом теории СПУ является метод критического пути, реализуемый в таких технологиях анализа проектов, как PERT, GERT и PRINCE2. В рамках этих технологий сетевой график представляется в виде особого вида диаграмм (сетевые диаграммы PERT, диаграммы Гантта), которые используются для устранения коллизий (рис. 2) – моментов перерасчета критического пути проекта, на основе информации о моментах временных задержек или опережений выполнения его отдельных этапов.
Локальный сетевой график исполнителя 1
Работы і
Длина критического пути равна 205
Локальный сетевой график исполнителя 2
А
Обычно, в рамках процесса СПУ, изменения временных параметров сетевого графика, обусловленных коллизиями, а также расчет критического пути проекта выполняется централизованно, и оперативно доводится до исполнителей этапов проекта по каналам взаимодействия (рис. 1). Однако, в условиях автономного функционирования интеллектуальных агентов, доступной для них является только локальная копия сетевого графика, а, в силу отсутствия каналов взаимодействия, информация о возникающих на предшествующих этапах проекта коллизиях является недоступной (рис. 3).
Время t
Длина критического пути равна 180
Рисунок 2 – Пример коллизии, связанной с задержкой выполнения этапа 1
Таким образом, существует объективное противоречие между децентрализованной организацией ряда распределенных систем обработки информации и управления, реализующих процесс СПУ, и отсутствием методов и алгоритмов управления согласованием временных параметров локальных сетевых графиков многоэтапного проекта в условиях возникновения коллизий.
Наиболее известные исследования методов оценки временных параметров сетевого графика в теории СПУ выполнены Д.И. Голенко, А.Н. Швецовым, С.Я. Виленкиным, Карсаевым О.В., Гейда А.С., Городецким В.И., Соколовым Б.В, Д.Р. Фалкерсоном, А. Кофманом, А.А. Мешковым, Г. Дебазеем, Дж.Е. Келли, В. Купером, Ю.П. Кривенко-вым, Дж. Томпсоном и др.
Локальный сетевой график п
Данные о
Задержках/
Опережениях
этапа 1
Локальный сетевой график 1
т
Управление локальным
сетевым графиком 1
Данные о Д Задержках/ Опережениях этапа 2
Управление локальным
сетевым графиком 2
Данные о
Задержках/
Опережениях
этапа n
Управление локальным
сетевым графиком n
Рисунок 3 – Вариант распределенной системы обработки информации и управления, реализующей сложные многоэтапные проекты в условиях автономности интеллектуальных агентов
Однако, проведенный анализ этой области исследования показал, что существующие методы СПУ, такие как PERT и его модификации GERT и PRINCE2 не поддерживают механизмы управления согласованием локальных копий сетевого графика в условиях автономного функционирования интеллектуальных агентов, что определяет актуальность разработки метода децентрализованного управления процессом сетевого планирования и алгоритма формирования локальных сетевых графиков множества автономных интеллектуальных агентов, учитывающего возникновение коллизий в процессе СПУ.
Область исследования. Содержание диссертации соответствует паспорту специ
альности 05.13.01 «Системный анализ, управление и обработка
информации (информационные системы управления)» (технические науки) по следую
щим областям исследования:
п.5. Разработка специального математического и алгоритмического обеспечения систем анализа, оптимизации, управления, принятия решений и обработки информации;
п.10. Методы и алгоритмы интеллектуальной поддержки при принятии управленческих решений в технических системах.
Объект исследования: распределенная система обработки информации и управления, поддерживающая процесс сетевого планирования многоэтапными проектами на основе автономных интеллектуальных агентов.
Предмет исследования: методы, способы и алгоритмы управления временными параметрами при сетевом планировании.
Цель исследования: совершенствование методов управления временными параметрами сетевых графиков многоэтапных проектов в системах с автономными исполнителями этапов за счет повышения уровня согласованности их локальных сетевых графиков на основе учета коллизий в процессе сетевого планирования.
Научная задача заключается в разработке метода децентрализованного управления процессом сетевого планирования и алгоритма формирования локальных сетевых графиков множества автономных интеллектуальных агентов, учитывающих возникновение коллизий в процессе сетевого планирования и управления.
Для решения научной задачи и достижения поставленной цели были сформулированы и решены следующие основные задачи:
-
Исследование существующих моделей, методов и алгоритмов управления временными параметрами сетевого графика, применяющихся в распределенных системах обработки информации и управления, на предмет поддержки процесса сетевого планирования многоэтапными проектами в условиях автономности исполнителей этапов.
-
Выбор и обоснование модели закона вероятностного распределения значений времени наступления событий сетевого графика, адекватно позволяющей учесть известные временные параметры и требования к их описанию.
-
Разработка метода децентрализованного управления процессом сетевого планирования, учитывающего установленный закон распределения вероятностей значений времени наступления событий сетевого графика и возникающие коллизии.
-
Разработка алгоритма формирования локальных сетевых графиков множества автономных интеллектуальных агентов, обеспечивающего минимизацию количества коллизий за счет применения решающей функции разработанного метода.
-
Проведение вычислительных экспериментов на основе разработанной имитационной модели, иллюстрирующих работоспособность предлагаемых метода и алгоритма.
Методы исследования. Научной основой для решения поставленной задачи
являются: теория и методы сетевого планирования и управления, методы системного
анализа и моделирования, теория коллективного поведения, теория вычислительных
экспериментов, теория вероятностей и математической статистики, теория
эффективности целенаправленных процессов.
Научная новизна полученных результатов заключается:
1. В новом методе управления процессом сетевого планирования, отличающемся
от известных учетом имеющихся временных параметров сетевого графика и требований
к их описанию, что обеспечивает корректность локальных сетевых графиков множества
автономных интеллектуальных агентов на основе учета коллизий.
2. В разработке нового алгоритма формирования локальных сетевых графиков
множества автономных интеллектуальных агентов, базирующегося на предложенном
методе управления процессом сетевого планирования и отличающегося от известных
использованием принципов стайного управления в технических системах, что позволяет
реализовать рациональный вариант децентрализованного управления процессом сетево
го планирования.
3. В разработке имитационной модели системы децентрализованного управления
процессом сетевого планирования, основанной на методах сетевого моделирования сто
хастических процессов, отличающейся от известных тем, что обеспечивается учет кол
лизий, возникающих в ходе реализации сетевого графика, и позволяющей проводить
оценивание работоспособности разработанных метода и алгоритма.
Теоретическая значимость полученных решений заключается в расширении аппарата сетевого моделирования стохастических процессов для адаптации традиционных методов расчета временных параметров сетевых графиков к задаче получения согласованных вариантов локальных сетевых графиков исполнителями проекта.
Практическая значимость работы заключается в доведении разработанных теоретических подходов и алгоритмических конструкций, применяемых для управления процессом сетевого планирования множества автономных интеллектуальных агентов, до уровня программных средств, предусматривающих непосредственное применение в
процессе информационной поддержки организационно-технологических мероприятий, что подтверждается актом внедрения в деятельность Центра специальной связи и информации Федеральной службы охраны Российской Федерации в Орловской области, в учебный процесс Академии ФСО России на кафедре «Автоматизированные информационные системы» и свидетельством о государственной регистрации программы для ЭВМ № 2017612858. Разработанные теоретические подходы отражены в патенте на изобретение № 2606315 от 10.01.2017 г. «Способ обработки запросов пользователей распределенной информационной системы».
Положения, выносимые на защиту:
1. Метод децентрализованного управления временными параметрами сетевого
графика множества автономных интеллектуальных агентов в составе распределенной
системы обработки информации и управления, поддерживающей процесс сетевого пла
нирования и управления многоэтапными проектами, позволяющий учесть имеющиеся
временные параметры сетевого графика и требования к их описанию, а также скоррек
тировать локальные сетевые графики множества автономных интеллектуальных агентов
на основе учета коллизий.
2. Алгоритм формирования локальных сетевых графиков множества автономных
интеллектуальных агентов, позволяющий повысить уровень их согласованности с целью
минимизации возникающих коллизий.
3. Результаты вычислительных экспериментов, проведённых на имитационной
модели системы децентрализованного управления процессом сетевого планирования,
подтверждающие работоспособность разработанных метода и алгоритма.
Достоверность выводов и рекомендаций обусловлена корректными преобразованиями, адекватностью модели стохастического сетевого планирования, отражающей вероятностно-временные характеристики сетевого графика со случайными длительностями работ, отсутствием противоречий с известными положениями теории и практики сетевого планирования и управления, проверкой свойств и вычислительной сложности разработанного алгоритма, а также подтверждена результатами вычислительных экспериментов.
Личный вклад соискателя. Все изложенные в диссертации результаты исследований получены либо соискателем лично, либо при его непосредственном участии.
Апробация результатов диссертационного исследования. Результаты диссертационного исследования обсуждались на следующих научно-технических конференциях: 20-я международная открытая научная конференция «Современные проблемы информатизации», Воронежский ГТУ, 2014 г.; IХ Всероссийская межведомственная научная конференция «Актуальные направления развития систем охраны, специальной связи и информации для нужд государственного управления», Академия ФСО России, Орел, 2015 г.; 21-я международная открытая научная конференция «Современные проблемы информатизации», Воронежский ГТУ, 2015 г.; 11-я Межведомственная конференция «Научно-техническое и информационное обеспечение деятельности спецслужб», ИКСИ, Москва, 2016 г.; Х Всероссийская межведомственная научная конференция «Актуальные направления развития систем охраны, специальной связи и информации для нужд государственного управления», Академия ФСО России, Орел, 2017 г.; 22-я международная открытая научная конференция «Современные проблемы информатизации», Воронежский ГТУ, 2017 г.
Публикации. По теме диссертационного исследования опубликовано 13 печатных работ (из них 6 научных статей опубликованы в 5-и рецензируемых журналах, ре-
комендованных ВАК при Минобрнауки России), в том числе 1 патент на изобретение и 1 Свидетельство Роспатента РФ о государственной регистрации программы для ЭВМ.
Объем и структура работы. Диссертация состоит из Введения, четырех глав, Заключения и Приложений. Работа изложена на 128 страницах машинописного текста, включая 40 рисунков, 7 таблиц и список литературы из 101 наименования.
Исследование современных информационных систем, осуществляющих построение и работу с сетевыми графиками
Одной из востребованных на сегодняшний день возможностей системы Microsoft Project является возможность устранения коллизий между фактическим сетевым планом и базовым (начальным) путем отслеживания проекта. Эта функция реализована с помощью простого ввода фактических данных в систему пользователем. Open Plan – система календарного планирования и управления проектами, которая также широко представлена на российском рынке [34]. Данный программный продукт способен поддерживать следующие основные функции: 1. Разработка структур сетевых планов. 2. Расчет календарных планов с учетом ограничений на все виды ресурсов. 3. Отслеживание выполнения этапов проекта и сравнение текущего состояния сетевого плана с исходным. 4. Предоставление пользователю необходимой отчетности по сетевому графику проекта. Одной из особенностей программного продукта Open Plan является наличие пакета Cobra. Основным предназначением его является моделирование прогнозов выполнения работ проектов с точки зрения сроков и/или материальных ресурсов.
Возможности Cobra по составлению прогнозов могут быть использованы при оценке окончательных параметров проекта на основе анализа хода его выполнения. Прогнозы, которые генерируются для оценки сроков выполнения проекта, обычно включают: оптимистический, пессимистический и наиболее ожидаемый прогноз. При этом использование статистических методов помогает повысить точность прогнозируемых оценок, учитывающих изменения временных параметров сетевого плана под влиянием случайных факторов, возникающих в ходе выполнения работ [34, 35].
Primavera Project Planner – это программа, предназначенная для автоматизации управления проектами [34, 35]. Разработчики данного программного продукта подразумевали ее использование как одной из подсистем в составе корпоративной информационной системы, которая сможет помочь решить задачи сетевого планирования и управления. Основными инструментами, обеспечивающими достижение целей использования продукта Primavera Project Planner, являются такие методы оценки СГ как: определение КП (CPM), метод PERT, what-if анализ [35, 36].
Важная функция контроля выполнения проекта с помощью сетевых планов заключается в отслеживании отклонений текущих значений параметров плана от заданных через так называемый механизм показателей. Показатели наглядно отображают «узкие места» и позволяют управлять параметрами сетевых планов через исполнителей этапов, которые автоматически получат извещения об отклонениях.
Другие программные продукты, позволяющие решать задачи сетевого планирования и управления, такие как Spider Project [35], Sure Trek Project Manager, Time Line и т.д. [37], также обладают типовым набором функций по увязке календарных сроков выполнения работ, отслеживании отклонений и управления параметрами сетевых графиков в виде диаграммы Гантта, анализ и прогнозирование хода выполнения проектов. При этом основу методологии, которая позволяет реализовать данный набор типовых функций, связанных именно со сроками выполнения работ, составляют такие методы оценки сетевых планов, как метод КП, метод PERT, GERT, PRINCE2. Проведенный выше анализ современных информационных систем, осуществляющих построение и работу с сетевыми графиками, показал, что одной из их важнейших функций является управление временными параметрами проекта при условии наличия случайных отклонений от заданных изначально сроков. Подобные ситуации принято называть коллизиями. Устранение коллизий необходимо для того, чтобы исключить несогласованность действий исполнителей работ, которая в свою очередь может поставить под угрозу успешность выполнения всего проекта целиком.
В условиях распределенности исполнителей этапов сетевого плана, реализация описанной выше функции возможна только при наличии каналов передачи информации между исполнителями и управляющим лицом, так как показано на рисунке 1. При этом пересмотр сетевых графиков происходит только после сбора данных об отклонениях и ввода их в систему. Данные особенности не позволяют использовать существующие на сегодняшний день решения в условиях автономного функционирования [4, 5] исполнителей работ СГ проекта, а также отсутствия управляющего модуля (рисунок. 3). Такие системы принято называть самоорганизующиеся [4, 38].
Примерами подобных информационных систем, в которых выполнение проекта осуществляется методом «эстафеты» (когда выполнение работы происходит строго друг за другом и последующая работа не может начаться до того момента времени, пока не закончится предыдущая), являются системы управления: логистикой в территориально-распределенных промышленных и торговых комплексах (рисунок 12, 13) [39, 40], поддержки выездных специальных мероприятий и/или операций в интересах органов государственной власти и при возникновении чрезвычайных ситуаций (рисунок 14) [41], координации действий подвижных объектов в условиях радиомолчания, таких как беспилотные летательные аппараты (рисунок 15) или специализированные роботы [42, 43, 44].
Метод децентрализованного управления временными параметрами сетевых графиков множества автономных интеллектуальных агентов распределенной системы обработки информации и управления
К основным недостаткам данного подхода относится необходимость обоснования значений отрезка [a, b], которые могут значительно отличатся от реальных при выполнении работ СГ; предположение о том, что коэффициенты , - принимают одинаковые значения на каждом этапе сетевого плана проекта; а также сформировавшийся вопрос о том, на какую величину времени может задерживаться выполнение каждого этапа проекта для того, чтобы все входящие в него работы были выполнены, то есть не надо было ни одну из них вычеркивать из графика.
Для преодоления недостатков всех перечисленных выше подходов было проведено дальнейшее исследование ряда модификаций технологии PERT, которое позволило в качестве основы разработанной стохастической модели продолжительности выполнения этапов сетевого плана выбрать закон бета-распределения с плотностью, представленной выражением (2.19): (t-a)a l(b) l [ ] л ,если t є a;b (р() = \(Ь_а)(1+$-1в(а о) Ч /219) [0,если t [a;b] J в которой , - свободные параметры; [a, b] - отрезок, задающий возможные значения случайной величины t времени наступления события; а В (, ) есть функция Эйлера: 1 R B(a,V)=ita(l)dt (220) Данный подход оказался наиболее простым для того, чтобы достаточно быстро определить и рассчитать значения свободных параметров и для исследуемого объекта в условиях наличия статистических данных, то есть известных значений отрезка [а, Ь]. Еще одним преимуществом перед другими рассмотренными подходами является значительное сокращение необходимой для планирования информации, что актуально для коллектива АИА.
Так как в ходе исследования было решено, что все значения случайной величины времени окончания каждого этапа проекта принадлежат отрезку [а, Ь], то условие нормировки для выражения плотности распределения (2.19) проверялось на основе выражения (2.9). Вычисляемое значение интеграла сводилось к рекуррентному выражению, имеющему решение. А экспериментально было доказано, что условие нормировки по выражению (2.9) выполняется для всех значений случайной величины времени окончания каждого этапа из отрезка [a, b].
Значение моды тп для каждого этапа рассчитывается по формуле (2.21): аП О тп = - при ап 1, Рп 1 (2.21) ап + Рп 2 В ходе проводимых исследований было установлено, что параметр для каждой из работ зависит от того, насколько далеко значение моды рассматриваемой работы отстоит от значения времени окончания всего проекта. Экспериментальным путем, методом простого перебора, отталкиваясь от значений 1 и 0,1, удалось быстро получить выражение (2.22), определяющее значения свободного параметра для каждой из работ СГ: 0 =1,25 + 0,1 п п , (2.22) Зная зависимость между значением моды [51] используемого распределения (2.21) от значений свободных параметров , и значений отрезка [a, b], получили выражение (2.23), определяющее значения свободного параметра для каждой из работ СГ:
Данный подход позволил получить плотности распределения случайного времени окончания этапов, соответствующие изначально заданным характеристикам сетевого плана. Результаты расчетов на основании выражений (2.19-2.23) приведены на рисунке 25.
Время наступления событий исходного сетевого плана в ходе выполнения его этапов может быть изменено под воздействием случайных факторов, поэтому для учета произошедших изменений интеллектуальным агентам, управляющим планированием последующих этапов, к модам их этапов предложено добавлять случайную величину zn, обозначающую насколько позже (раньше) закончился текущий этап относительно запланированного срока (аналогично подходу, рассматриваемому выше). Тогда мода следующего этапа примет значение: m n+l m n+l+z n , (224) где n - номер текущей работы, а мода m n+2 будет учитывать и случайный сдвиг z , и случайный сдвиг z . Как и в предыдущем подходе все расчеты сроков завершения каждого этапа будут вестись относительно новых значений.
Применяя используемое в технологии PERT выражение (2.25) для расчета дисперсии каждого этапа СГ, выражение (2.26) для расчета общей дисперсии принятого закона распределения (2.19), и выражение (2.27), возможно оценить значение решающего коэффициента окончания всего сетевого проекта в запланированный срок, заданный значением В [71] сопоставлены значения решающего коэффициента K и возможностей реализации сетевого плана проекта с заданными условиями (таблица 2.1). Соотношение значений решающего коэффициента K с возможностью реализации сетевого плана проекта Значение K Реализация проекта в заданных условиях 1 В выполнение сетевого плана проекта заложены излишние временные ресурсы от 0,6 до 1 Выполнение сетевого плана проекта будет безусловно реализовано в заданное время от 0,1 до 0,6 Выполнение сетевого плана проекта возможно в заданное время при наличии дополнительных ресурсов 0,1 Выполнение сетевого плана проекта возможно только при удалении некоторых работ
При исследовании СГ модельного проекта (рисунок 7), для случайной задержки первого этапа на 15 единиц времени были получены результаты, представленные на рисунке 27. Решающий коэффициент окончания всего сетевого проекта в запланированный срок, заданный значением b, приняла значение K = 0,541. Для случайной задержки третьей работы на 50 единиц времени были получены результаты, представленные на рисунке 28. При этом значение решающего коэффициента окончания всего сетевого проекта в запланированный срок, заданный значением b, стало отрицательным.
Алгоритм формирования локальных сетевых графиков множеством автономных интеллектуальных агентов, учитывающих возникновение коллизий в процессе сетевого планировании и управления
Алгоритм Форда также может быть использован и для определения наиболее ранних и поздних сроков наступления событий СГ. Он аналогичен описанному выше алгоритму, только вместо рангов событий вычисляются значения времен их наступления с помощью рекуррентных соотношений Форда. Также алгоритм Форда помогает установить наиболее «узкие места» проекта через наглядное отображение КП.
Алгоритм Фалкерсона для расчета временных параметров СГ применим для сетевой структуры любого типа. Он основан на том, что в качестве закона распределения вероятностей длительностей работ может быть использовано произвольное ограниченное дискретное распределение. При этом задается совместное распределение длительностей работ. Априорные предположения о законе распределения сроков свершения событий СГ отсутствуют. Алгоритм рассчитывает: нижнюю оценку f; математическое ожидание времени свершения события, в том числе и заключительного [73].
Вычисляемые оценки ft рассчитываются рекуррентно как результат воздействия оператора математического ожидания на формулу для расчета детерминированных сетей [73]: fl = М {тах[У/ + t(i,j)]}, (3.1) где М - оператор математического ожидания; / j при правильной нумерации событий СГ. Стоит отметить, что величина t (і, j) рассматривается здесь как случайная, а ft как значение, вычисленное на предыдущем шаге.
В дальнейшем алгоритм, построенный по методу Фалкерсона, был дополнен Клингеном для случая, когда предполагалось, что закон распределения случайной длительности работ сетевого плана является непрерывным [73].
Алгоритм расчета временных параметров СГ со случайными длительностями этапов, основанный на методе Фалкерсона, может применяться только для анализа средних значений самых ранних сроков наступления событий сетевого плана. Алгоритм Кларка предполагал: любой тип структуры вероятностной сети; нормальный закон распределения вероятностей длительностей работ; независимость случайных длительностей работ. Результатом его работы было получение значений оценок начальных моментов порядка с первого по четвертый. Оператор, вычисляющий соответствующий момент, использовался в формуле Фалкерсона (выражение 3.1). При этом все величины, входящие в данную формулу, рассматривались как случайные.
Предполагалось, что значения сроков свершения предшествующих рассматриваемому событию этапов являются зависимыми друг от друга. Это давало возможность предварительно вычислить коэффициенты корреляции.
Данный алгоритм базируется на формулах для вычисления начальных моментов первого и второго порядков распределения вероятностей максимума двух коррелированных случайных величин xt и xj с соответствующими 2 2 математическими ожиданиями wit и mj и дисперсиями CTJ и Т ,: vi = /и/Ф(77) + m j $)(-ri) + a(p{rj), (3.2) v 2 = {т} + т})Ф(я) + (m j + cry )Ф(-77) + (щ + m j )cup{rj) , (3.3) где: щ -Jflf 71 = , (3.4) а a = 7f + 7j - 2 7f 7jp , (3.5) V2;r (3.6) Моменты распределения максимума некоторого количества случайных величин вычисляются рекуррентно по выражениям (3.2), (3.3) и формулы (3.8), вычисляющей коэффициент корреляции полученной случайной величины с еще одной случайной величиной: (JiPik4ri) + jPjk(-r?) Р(хк,У) = 1 , (3.8) V v 2 v 1 где pmr = р(хт ,x r ).
Выражения (3.2), (3.3) и (3.8) получены на основании предположения о том, что на каждом шаге вычисления максимума снова и снова получается нормальное распределение.
В данном алгоритме возможно наличие существенных погрешностей из-за предположения о том, что на каждом шаге расчета сохраняется нормальный закон распределения. Также существенным недостатком является то, что объем вычислений и, соответственно, асимптотическая сложность данного алгоритма быстро увеличиваются с возрастанием числа этапов СГ.
Алгоритм Виленкина С.Я., как и предыдущие рассмотренные алгоритмы, предназначен для расчета любого вида вероятностных сетевых моделей, использует при расчетах ограниченные законы распределения, предполагает независимость случайных величин. В данном алгоритме случайная величина, обозначающая длительность пути от начального события проекта до конечного, предполагается распределенной по нормальному закону. Математический аппарат данного алгоритма основан на аппроксимации интегральной функции распределения продолжительности КП [51], при этом продолжительность КП представляется как максимальное значение случайных продолжительностей всех путей. Алгоритм Виленкина С.Я. при расчете сложных и объемных вероятностных сетевых моделей приводит к достаточно большим трудностям, связанным с вычислениями.
Разработка имитационной модели системы децентрализованного управления процессом сетевого планирования, основанной на аппарате сетевого моделирования стохастических процессов
Для разработки имитационной модели системы децентрализованного управления процессом сетевого планирования и управления необходимо использовать имитационную среду, которая позволяет проводить анализ исследуемого объекта во времени с возможностью остановки в любой момент для последующего анализа результатов.
Подобную задачу способны решать многие средства имитационного моделирования, представленные на современном рынке. Наиболее известными и доступными на данный момент из них являются такие программные продукты как MatLab, AnyLogiс, Arena, Simulink, PowerSim, Simula, ProModel, SimScript, GPSS World и др. [86-91], а также такие интегрированные среды разработки программного обеспечения как, например, Borland C++ Builder.
Все вышеперечисленные средства можно условно разделить на те, которые основаны на моделях системной динамики, дискретно-событийных и агентных моделях [92].
В моделях системной динамики принято описание исследуемой системы некоторым математическим аппаратом, состоящим из множества значений переменных состояния и системы алгебраических уравнений [90]. К продуктам, имитирующим системную динамику относятся MatLab, AnyLogiс, PowerSim.
Дискретно-событийные модели схожи с моделями системной динамики, однако, они не предоставляют возможности отслеживания развития исследуемого объекта в произвольные моменты времени [92].
Агентное моделирование заключается в том, что исследуемый объект представляется в виде набора отдельных друг от друга объектов, каждый из которых способен взаимодействовать с другими, указанными заранее объектами, которые, в свою очередь, образуют внешнюю среду функционирования [92]. Агентное моделирование позволяет решить задачу получения информации об общем поведении исследуемой системы, состоящей из отдельных активных объектов (агентов) на основании знаний о поведении каждого из них. В программных средствах, реализующих агентное моделирование (AnyLogiс, Borland C++ Builder и др.), пользователь определяет действия на индивидуальном уровне (для агентов), а глобальное поведение исследуемой системы рассматривается как результат поведения многих агентов, каждый из которых взаимодействует с подобными ему агентами и внешней средой.
Так как в работе для реализации системы децентрализованного управления процессом сетевого планирования в условиях автономности исполнителей работ проекта обоснованно используется агентно-ориентированный подход, то очевидным является выбор имитационной среды, реализующей агентные модели.
Наиболее проработанным и широко развитым средством с таким требованием является AnyLogiс [92]. Однако, данная среда скрывает от пользователя процесс формирования случайных значений выбранного для исследования закона распределения. Программная среда Borland C++ Builder позволяет пользователю провести программную реализацию закона распределения с помощью встроенных библиотек, однако данные библиотеки подходят для стандартных параметров закона распределения, которые впоследствии необходимо будет нормировать (рисунок 7, выражения 2.19-2.27). При этом Borland C++ Builder позволяет реализовать выбранный закон распределения наглядно, сразу учитывая необходимую нормировку значений., а также имеет все необходимые возможности для решения поставленной задачи проведения эксперимента, подтверждающего эффективность разработанного метода и алгоритма. Данный программный и будет выбран в качестве среды имитационного моделирования. 4.2 Разработка имитационной модели системы децентрализованного управления процессом сетевого планирования, основанной на аппарате сетевого моделирования стохастических процессов
В результате выбора данной программной платформы удалось реализовать агентно-ориентированный подход с использованием раздельно выполняющихся потоков. Имитация выполнения СГ во времени реализована с помощью встроенного таймера.
Генерация случайных значений времени окончания каждой работы СГ выполняется с помощью встроенного генератора случайных чисел. Однако, в ходе имитационного моделирования были выявлены следующие особенности: генерация случайного числа на отрезке от нуля до заданного значения возможна с помощью встроенных в выбранную имитационную среду Borland C++ Builder функций. Функция RandQ генерирует псевдослучайные значения от 0 до Rmax [93] с равномерным законом распределения [94]. При этом получаются результаты, показанные на рисунке 33.
Чтобы правильно решить подобную проблему необходимо ограничить Rmax некоторым значением R, которое будем рассчитывать по формуле [93]: R = max - ( max [modw]) . (4.1) После этого сгенерируем случайное число Y с помощью встроенной функции RandQ. Если Y R, рассчитанного с помощью выражения (4.1), то случайное число считается сгенерированным. Иначе случайное число генерируется снова. При выполнении описанных выше действий получаются результаты, представленные на рисунке 34. Для того, чтобы от равномерного закона распределения перейти к бета-распределению, описанного выражениями (2.19-2.27), то есть для моделирования случайных значений длительностей работ СГ проекта было разработано решение, состоящее из 8 шагов.