Содержание к диссертации
Введение
Глава 1 Современное состояние проблемы планирования сложных обслуживающих комплексов со стохастическими параметрами 13
1.1. Особенности оптимизации сложных обслуживающих систем со стохастическими параметрами 13
1.2. Обзор существующих методов формирования план-графиков 17
1.3. Обзор существующих подходов к оценке длительности обслуживания 23
1.4. Обзор существующих подходов к оценке длительности проекта в целом 35
1.5. Анализ существующих систем имитационного моделирования
1.6. Обзор существующих программных средств формирования план графиков 42
1.7. Цель и задачи диссертационного исследования 45
Глава 2 Математическое моделирование стохастических систем с взаимной зависимостью между отдельными работами, временными ограничениями и критерием равномерной загрузки 50
2.1 Разработка математической модели системы 50
2.2 Критический анализ существующих подходов к оценке математического ожидания бета-распределения 58
2.3 Интервальные оценки математического ожидания с помощью моды 69
2.4 Аналитическое значение математического ожидания бета-распределения по известным дисперсии и моде 75
2.5 Обоснование эффективности полученных результатов 84
2.6 Выводы 87
Глава 3 Оценка закона распределения длительности последовательно решаемых задач 88
3.1 Экспериментальный анализ закона распределения суммы бета-величин 88
3.2 Аналитическая оценка закона распределения суммы двух бета-величин 93
3.3 Оценка параметров закона итоговой случайной величины 101
3.4 Рекурсивный алгоритм для численной оценки закона распределения длительности проекта 104
3.5 Экспериментальное подтверждение гипотезы об аппроксимации суммы бета-величин законно бета 116
3.6 выводы 127
Глава 4 Математическое моделирование вероятностно временных характеристик длительности обслуживания заявки 128
4.1 Математическая постановка задачи и ее особенности 128
4.2 Анализ аналитического подхода к оценке числовых характеристик искомой случайной величины 132
4.3 Аппроксимация числовых характеристик искомой случайной величины 145
4.4 Аппроксимация закона распределения искомой случайной величины 154
4.5 выводы 164
Глава 5 Алгоритмы и численные методы решения формирования графика обслуживания заявки с точки зрения критерия равномерной загрузки и временных ограничений 166
5.1 Анализ особенностей задачи планирования с временными и ресурсными ограничениями, несколькими центрами обслуживания и существующим расписанием 166
5.2 Обобщенный алгоритм планирования 174
5.3 Структура мультиагентной системы для формирования план-графика 177
5.4 Определение оптимального этапа для возврата 183
5.5 Разработка эвристик для планирования работ на данном временном этапе 187
5.6 Результаты использования разработанных эвристических методов для формирования расписания работ обслуживающей системы 200
5.7 выводы 211
Глава 6 Система имитационного моделирования для анализа вероятностно-временных характеристик проекта 213
6.1 Структура программного комплекса 213
6.2 Структура специализированной системы имитационного моделирования 220
6.3 Математическая модель имитационной системы 229
6.4 Алгоритмы формирования структуры модели 233
6.5 Реализация прогона модели 239
6.6. Реализация специализированной системы имитационного моделирования 250
6.7 Результаты моделирования 255
6.8. Выводы 258
Глава 7 Реализация спектра программных комплексов для оптимизации функционирования сложных обслуживающих систем со стохастическими параметрами 260
7.1 Проектирование структуры базы данных 261
7.2 Специфика программного комплекса для воронежского вагоноремонтного завода 272
7.3 Специфика программного комплекса для планирования работ лечебно профилактических учреждений 281
7.4 Особенности программного комплекса для решения задач управления проектами в строительных компаниях 288
7.5 Специфика использования полученных результатов для других обслуживающих систем 294
7.6 Выводы 301
Основные результаты работы 303
Список использованных источников 305
- Обзор существующих подходов к оценке длительности обслуживания
- Аналитическое значение математического ожидания бета-распределения по известным дисперсии и моде
- Аналитическая оценка закона распределения суммы двух бета-величин
- Анализ аналитического подхода к оценке числовых характеристик искомой случайной величины
Введение к работе
Актуальность темы.
Эффективность функционирования сложных обслуживающих систем в современных условиях во многом определяется качеством составленного расписания их работы. Необходимость обработки сразу нескольких заявок с индивидуальными вариантами обслуживания, включающими решение большого количества взаимозависимых задач со стохастическими параметрами, временные и ресурсные ограничения, наличие нескольких центров обслуживания обуславливают формирование и развитие соответствующих математических моделей, алгоритмов и программных комплексов, позволяющих получить оценки длительности выполнения как отдельных задач, так и всей заявки в целом, вероятностно-временных характеристик заявок, оптимизировать процесс построения расписания, а также автоматизировать процесс решения вышеперечисленных задач.
Данная задача относится к классу NP-полных задач теории расписаний. В настоящее время множество проблем в данной области уже исследованы и широко изучены. В частности, большой вклад в развитие теории расписаний для многостадийных систем внесли такие ученые, как Танаев В.С., Конвей Р.В, Максвелл В.Л., Миллер Л.В. и др. Разработкой моделей и методов формирования графиков обслуживания в условиях взаимной зависимости работ, а также управлением ресурсами для оптимизации расписаний занимались Ахьюджа Х., Кендалл И., Новиков Д.А., Бурков В.Н. и др. Развитию методов планирования в условиях стохастических характеристик отдельных работ посвящены научные труды Д.И. Голенко-Гинзбурга, А. Кофмана, Г. Дебазея и др.
Однако, не все проблемы в данной области можно считать решенными. В частности, существующие подходы к формированию расписаний ориентированы в основном на скорейшее завершение обслуживания заявки. Однако, для многих систем время выступает не как критерий, а как ограничение, что существенно осложняет процесс планирования. Существующие математические модели оценки длительности обслуживания комплекса взаимозависимых задач основаны на нормальном законе распределения, что в ряде случаев приводит к недопустимым погрешностям при расчете вероятностных характеристик длительности обслуживания заявки.
Все это обуславливает необходимость разработки математических методов, предназначенных для оценки вероятностно-временных характеристик стохастических параметров сложных обслуживающих систем, численных методов, обеспечивающих формирование расписания в условиях временных и ресурсных ограничений, существующего графика обслуживания заявок, поступивших ранее, нескольких центров обслуживания, а также программных комплексов, позволяющих моделировать процесс обслуживания и автоматизировать использование математических моделей и численных методов для оптимизации функционирования систем с указанными выше особенностями.
В работе развиваются математические модели и методы исследования многостадийных обслуживающих систем, состоящих из нескольких центров, на
вход которых поступает поток заявок, требующих для своего обслуживания выполнения множества взаимно-зависимых работ со стохастическими параметрами.
Диссертационная работа выполнена в рамках научного направления Воронежского государственного технического университета «Вычислительные комплексы и проблемно-ориентированные системы управления».
Целью работы является разработка математических моделей, методов и программных средств, оптимизирующих процесс функционирования многостадийной системы, особенностью которой является случайная длительность выполнения отдельных задач по обслуживанию, а также наличие ресурсных и временных ограничений, путем составления графика обслуживания заявки, а также нахождения эффективных оценок ее стохастических характеристик.
Исходя из данной цели, в работе определены следующие задачи:
1. Проанализировать существующие подходы к оптимизации многоста
дийных комплексов со случайной длительностью обслуживания, ресурсными и
временными ограничениями и несколькими центрами обслуживания с целью
повышения эффективности их функционирования.
2. Получить математическую модель системы, адекватно отражающую
все вышеперечисленные особенности задачи и позволяющую сформулировать
оптимизационную задачу для составления расписания.
-
Получить оценку длительности обслуживания отдельных работ заявки, которая отличалась бы повышенной точностью по сравнению с существующими аналогами.
-
Разработать математическую модель, позволяющую оценить вероятностно-временные характеристики длительности обслуживания заявки.
-
Экспериментально обосновать эффективность полученных оценок.
-
Разработать эвристические методы формирования расписания для обслуживания заявки с учетом временных и ресурсных ограничений и обобщенного ресурсного критерия.
-
Разработать систему имитационного моделирования, представляющую собой инструмент для анализа вероятностно-временных характеристик заявки.
-
Реализовать программный комплекс, обеспечивающий автоматизацию процесса оптимизации сложных систем путем нахождения эффективных оценок ее параметров и построения графика обслуживания заявки с учетом ресурсных и временных ограничений и обобщенного ресурсного критерия.
Методы исследования основаны на теории математического моделирования, теории вероятностей и математической статистики, теории численных методов, методов оптимизации, теории объектно-ориентированного программирования.
Тематика работы соответствует следующим пунктам паспорта специальности 05.13.18 «Математическое моделирование, численные методы и комплексы программ»: п. 3. «Разработка, обоснование и тестирование эффективных численных методов с применением компьютерных технологий»; п. 4 «Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного экс-
перимента»; п.6 «Разработка новых математических методов и алгоритмов проверки адекватности математических моделей объектов на основе данных натурного эксперимента»; п. 8. «Разработка систем компьютерного и имитационного моделирования».
Научная новизна. В работе получены следующие результаты, отличающиеся научной новизной:
-
Математическая модель многостадийной системы, учитывающая случайную длительность обслуживания и ограничения на взаимную зависимость работ, а также временные и ресурсные ограничения, и позволяющая оптимизировать процесс ее функционирования с точки зрения обобщенного ресурсного критерия.
-
Аналитическая оценка длительности выполнения отдельной работы, полученная на основании наименьшего, наибольшего и наиболее вероятного времени обслуживания и обеспечивающая повышенную точность по сравнению с существующими аналогами.
-
Оценка закона распределения случайной величины, описывающей длительность комплекса последовательно выполненных работ, полученная на основании использования бета-распределения и отличающаяся повышенной точностью по сравнению с существующими аналогами.
-
Математическая модель вероятностно-временных характеристик длительности обслуживания заявки, построенная на базе закона бета и обеспечивающая повышенную точность по сравнению с предыдущими аналогами.
-
Эвристические методы, предназначенные для решения задачи оптимизации функционирования системы с временными ограничениями и произвольным ресурсным критерием путем формирования графика обслуживания заявки и обеспечивающие возможность поиска субоптимального решения за приемлемое время.
-
Специализированная система имитационного моделирования, отличающаяся ориентацией на моделирование процесса обслуживания в системах со стохастическими характеристиками взаимно-зависимых работ и обеспечивающая возможность сбора и анализа статистических данных о случайной величине, описывающей длительность обслуживания заявки.
-
Структура программного комплекса, отличающаяся наличием взаимодействующих систем имитационного моделирования, планирования и оптимизации, а также оценки вероятностно-временных характеристик обслуживания и обеспечивающая автоматизацию процесса планирования заявок, особенностью которых является случайная длительность выполнения работ, временные и ресурсные ограничения.
Практическая ценность работы. Практическая ценность работы заключается в разработке комплекса программ, позволяющего формировать план-график работы системы, отличительной особенностью которой является произвольное время обслуживания заявок, а также ресурсные и временные ограничения. Применение данного программного комплекса позволит не только существенно сократить время, затрачиваемое на формирование графика обслуживания заявок, но и существенно повысит качество предлагаемого расписания за
счет использования оценок стохастических параметров системы, отличающихся повышенной точностью по сравнению с существующими аналогами.
Разработанный программный комплекс может быть использован для оптимизации функционирования любых систем, особенностью которых являются наличие нескольких центров, случайная длительность выполнения отдельных работ, а также наличие временных и ресурсных ограничений.
Реализация и внедрение результатов работы. Разработанные подходы могут быть использованы для оптимизации функционирования любых сложных системы, отличительной чертой которых является наличие случайной длительности обслуживания заявок, наличие нескольких взаимно-зависимых работ для обслуживания каждой заявки, а также временных и ресурсных ограничений и критерия равномерной загрузки системы.
Программные средства внедрены и используются для оптимизации функционирования строительных компаний ООО УК «Жилпроект», ОАО «Воро-нежтрубопроводстрой», лечебно-профилактических учреждений МУЗ Хо-хольская ЦРБ и БУЗВО ВОККВД, а также фирмы ООО «ВебФинанс», занимающейся разработкой программного обеспечения.
Апробация работы. Основные положения и результаты диссертационной работы докладывались на следующих научных конференциях и семинарах: Всерос. конф. «Интеллектуализация управления в социальных и экономических системах» (Воронеж, 2008); Всерос. конф. «Новые технологии в научных исследованиях, проектировании, управлении, производстве» (Воронеж, 2008); IV Всерос. науч.-техн. конф. «Вузовская наука – региону» (Вологда, 2008); «Современные проблемы информатизации в моделировании и социальных технологиях» (Воронеж, 2009); «Современные проблемы информатизации в моделировании и социальных технологиях» (Воронеж, 2009); X Всероссийской научно-технической конференции «Теоретические и прикладные вопросы современных информационных технологий» (Улан-Удэ, 2009); VIII Всероссийской научно-технической конференции с международным участием «Информационные технологии и математическое моделирование. Материалы» (Томск, 2009); I Всерос. конф. «Критические технологии вычислительных и информационных систем» (Воронеж, 2011); IV Международной научно-практической конференции «Перспективы развития информационных технологий» (Новосибирск, 2011); V Международной научной конференции «»Актуальные вопросы современной техники и технологии (Липецк, 2011); II Межд. конф. «Информационные технологии в вычислительной технике и связи: Материалы» (Воронеж,
2013), Modern Informatization Problems (Yelm,WA, USA, 2014), Международна
научна школа «Парадигма» (Варна, Болгария, 2015).
Публикации. По теме диссертационной работы опубликовано 74 работы. Из них 28 опубликованы в журналах, рекомендованных ВАК РФ. В работах, опубликованных в соавторстве и приведенных в конце автореферата, личный вклад автора составляет: [1, 24, 26] - – структура программного комплекса, предназначенного для оптимизации функционирования сложных систем; [2, 20, 51] – структура мультиагентной системы; [3] – аналитическая оценка математического ожидания бета распределения; [5, 13] – оптимизационная задача для
обслуживающей системы со стохастическими параметрами; [6, 32, 39] - математическая модель многостадийной обслуживающей системы; [14, 36] - структура системы имитационного моделирования; [17, 41, 43, 45] - математическая модель оценки длительности обслуживания отдельных работ заявки; [19] - алгоритм формирования план-графика для сложных систем при наличии существующего расписания; [27] - реализация основных подсистем программного комплекса; [29-31] - математические модели, алгоритмы и программные комплексы оптимизации сложных обслуживающих систем; [33, 34, 42] - эвристические методы формирования расписания для обслуживания заявки; [52] - реализация вычислительного эксперимента для подтверждения эффективности полученных оценок; [53] - математическая модель вероятностно-временных характеристик длительности обслуживания заявки; [54] - структура базы данных для разработанного программного комплекса.
Структура и объём работы. Работа состоит из введения, семи глав, заключения, списка литературы из 216 наименований и приложений. Основная часть работы изложена на 304 страницах, содержит 115 рисунков и 22 таблицы.
Обзор существующих подходов к оценке длительности обслуживания
Однако, возникает вопрос о законе распределения суммы небольшого числа бета-величин с разными математическими ожиданиями и дисперсиями. В данном случае условия центральной предельной теоремы могут быть существенно нарушены, что сделает оценку (1.41) достаточно грубой. Следует также отметить возможность наличия у проекта двух и боле критических путей. Очевидно, что сумма дисперсий каждой из величин, описывающих отдельный критический путь, будет своя. В связи с этим возникает необходимость в экспериментальном анализе существующих оценок в случае небольшого числа случайных величин, стоящих на критическом пути, а также в случае наличия двух и более критических путей с целью подтверждения их применимости в подобных условиях или необходимости разработки более точных оценок, позволяющих учесть особенности исследуемой задачи.
Еще одним существенным фактором является пренебрежение в формуле (1.40) случайными величинами, описывающими все некритические пути. Очевидно, что при большом количестве путей проекта (что имеет место для реальных систем), а также в случае, если суммарная длительность работ, стоящих на некоторых некритических путях, достаточно близка к аналогичной сумме длительностей работ критического пути, степень влияния некритических работ на исследуемую случайную величину существенно возрастает. В связи с тем, что в существующих подходах этим влиянием пренебрегают, необходимо провести экспериментальный анализ, позволяющий подтвердить или опровергнуть возможность игнорирования любых работ за исключением тех, что стоят на критическом пути. Таким образом, возникает необходимость в разработке математического аппарата, позволяющего с повышенной точностью оценить закон распределения случайной величины, описывающей длительность проекта, а также ее числовые характеристики (математическое ожидание и дисперсию).
Недостаточное развитие методов для оценки длительности проекта и, как следствие, оценки рисков, связанных с несвоевременным его завершением, обуславливают необходимость использования систем имитационного моделирования для анализа времени, затрачиваемого на выполнение всех работ. Такие системы позволят сымитировать процесс выполнения проекта и дать на выходе статистическую информацию о его вероятностно-временнных характеристиках.
В настоящее время существует множество разнообразных систем имитационного моделирования, отличающихся возможностями, функционалом и спецификой применения. Проанализируем наиболее распространенные системы применительно к решению задачи управления проектами. Сформулируем наиболее значащие требования, которым должна отвечать в данном случае система имитационного моделирования: - возможность использования системы для решения задач управления проектами; - возможность задания проекта наиболее простым для пользователя способом (в данном случае это будет графический способ, позволяющий задать проект в виде связного графа, ребра которого обозначают отдельные работы); - возможность импорта исходных данных из базы данных и экспорта результатов моделирования в нее; - возможность экспорта результатов моделирования в Excel. Проанализируем существующие программные продукты с точки зрения описанных выше требований. Одной из наиболее распространенных систем имитационного моделирования является система GPSS. Она предназначена для имитационного моделирования систем с дискретными и непрерывными процессами [15]. Язык GPSS построен в предположении, что модель сложной системы можно представить совокупностью элементов и логических правил их взаимодействия в процессе функционирования моделируемой системы. В составе GPSS имеется специальная программа-планировщик, которая выполняет следующие функции: - обеспечение продвижения по заданным разработчиком маршрутам динамических объектов, называемых транзактами; - планирование событий, происходящих в модели, путем регистрации времени наступления каждого события и выполнения их в нарастающей временной последовательности; - регистрация статистической информации о функционировании модели; - продвижение модельного времени в процессе моделирования системы. В качестве недостатков следует отметить сложность представления процессов обработки данных на уровне алгоритмов. Кроме того, модель представляет собой программу, а, значит, не имеет графической интерпретации, что затрудняет процесс разработки модели и снижает наглядность модели в целом. Anilogic – программное средство, предназначенное для создания имитационных моделей любой сложности [66]. К несомненным достоинствам данного продукта следует отнести удобный графический редактор, позволяющий быстро создавать модели для широкого спектра задач (моделирование бизнес-процессов, логистика, управление производством и т.д.). Данное приложение поддерживает три технологии создания имитационных моделей: дискретно-событийную, системно-динамическую или агентную (а также комбинацию данных подходов в пределах одной модели). В качестве языка разработки использовался Java. В связи с этим, Anilogic позволяет возможность расширения моделей средствами Java, а также экспорт эксперимента в Java-апплет или Java-приложение.
Для построения сложных алгоритмов имитации на основании агентного подхода компанией Rockwell Software был разработан специализированный программный комплекс Arena. Основу этой системы составляют язык моделирования SIMAN и анимационная система Cinema Animation. Следует сказать, что анимации процесса моделирования в системе Arena уделяется большое внимание. Целью создания данной системы имитационного моделирования, прежде всего, как отмечает е создатели, было исследование бизнес-процессов для различных коммерческих организаций.
Аналитическое значение математического ожидания бета-распределения по известным дисперсии и моде
Одним из важнейших ограничений, определяющих специфику задачи, является ограничение на время выполнения проекта. Как следует из формулы (2.3), для каждого проекта Pi задан директивный срок его окончания ТІ. Решение оптимизационной задачи предполагает нахождение времени начала t нач_ц каждой работы j каждого проекта і. В этом случае, время начала должно быть таково, чтобы для каждого проекта выполнялось условие: Тфакт1 T1,i = l,...,n (2.17) Здесь Тфакт_ - фактическое время завершения обслуживания заявки і с учетом составленного расписания; ТІ - директивный срок завершения проекта. Фактическое время завершения обслуживания заявки - это момент, в который будет закончена самая последняя ее работа. С точки зрения задач управления проектами это критическое время проекта [114, 162, 198, 199, 200]. Его можно определить по формуле: Т; факт = max(wrtнач + wrdlit). (2.18) В некоторых случаях вместо строгого неравенства (2.17) иногда целесообразно определять более мягкое ограничение, гарантирующее выполнение проекта к заданному сроку с некоторой вероятностью: Р(Тфакті Ті) Рі- (219) Здесь Pi - вероятность, с которой проект i должен завершиться к моменту Ti. С учетом аппарата теории вероятностей неравенство (2.19) можно переписать в виде: FT (Ti) Pi (2.20) факт i / где FT iTi) - функция распределения случайной величины Tфакт_i, описывающей длительность завершения проекта i. Формулы (2.1)-(2.20) и составляют основу математической модели многостадийной системы, учитывающую случайную длительность обслуживания и ограничения на взаимную зависимость работ, а также временные и ресурсные ограничения, и позволяющую оптимизировать процесс ее функционирования с точки зрения обобщенного ресурсного критерия.
Соответствующую оптимизационную задачу можно сформулировать следующим образом. Пусть в многостадийную систему, состоящую из нескольких центров обслуживания, поступила заявка, требующая для своего выполнения множества последовательно-параллельных работ со случайной длительностью. Требуется задать каждой работе такое время начала, чтобы для каждого центра объем используемых ресурсов выполнялись временные ограничения (2.16) или (2.19), а также ограничения на взаимную зависимость работ (2.16) и объем используемых ресурсов (2.11).
Как видно из математической модели, одной из ключевых ее особенностей, подлежащих исследованию, является стохастический характер длительностей выполнения операций. В связи с этим, остальные части главы подлежат разработке подходов для ее оценивания.
Среди всех компонентов математической модели наибольший интерес с математической точки зрения представляет оценка длительности обслуживания. Как было отмечено ранее, она представляет собой случайную величину, закон распределения которой имеет вид (2.6). Обзор методов, приведенный в главе 1, показал, что наиболее распространенным подходом к оценке математического ожидания бета-величины на основании известных границ области ее определения, а также моды является метод PERT. Математическое ожидание случайной величины, распределенной по закону бета, оценивается формулой (1.37), а дисперсия – (1.35).
Рассмотрим погрешности, которые могут возникать при использовании данного метода для оценки случайной величины, распределенной по закону бета [143]. В первую очередь, это погрешности самого метода, а во вторую – погрешности, возникающие при оценке случайной величиной с помощью математического ожидания.
Второй вид погрешности оценить достаточно просто. Для этого достаточно для каждого значения параметров p и q найти значение математического ожидания, а также найти оценку (1.37). Разница между ними покажет отклонение истинного значения математического ожидания от ее оценки.
В результате расчетов получили следующие значения погрешностей метода относительно математического ожидания.
В данной таблице по столбцам отложены значения параметра p, по строкам – значения параметра q. В каждой ячейке находится значение, представляющее собой разность (по модулю) между математическим ожиданием случайной величины, распределенной по закону бета с данными значениями параметров и его оценкой.
Как можно видеть из данной таблицы, разница между точным значением математического ожидания и ее оценки достаточно невелико.
Однако, необходимо иметь в виду, что метод PERT используется для решения задачи сетевого планирования, в которой проект представляется в виде совокупности взаимозависимых работ. Как известно, начало выполнения каждой из таких работ определяется исходя из так называемого критического времени, которое определяется как время завершения последней операции проекта. Поскольку эта величина будет зависеть от длительности каждой из работ, стоящих на критическом пути, то при суммировании данных значений итоговая погрешность будет также суммироваться. Следовательно, при большом числе работ, определяющих проект, минимизация погрешности при оценке времени выполнения каждой работы является весьма важной задачей. Для анализа точности метода PERT проведем следующий вычислительный эксперимент. Для каждых значений параметров р и q сгенерируем случайную величину, распределенную по закону бета. Далее посчитаем оценку математического ожидания этой величины с помощью формулы (1.37). Проделав данный опыт многократно, определим относительную погрешность метода PERT относительно истинного значения случайной величины. В частности, для каждых значений параметров р и q проведем 1000 опытов по генерации случайных чисел, и на основании этой выборки будем оценивать погрешность.
Аналитическая оценка закона распределения суммы двух бета-величин
В результате эксперимента получились погрешности, приведенные для каждого значения параметров p и q в соответствующих таблицах приложения 3. Анализ этих значений позволил сделать следующие выводы: 1) во всех случаях разработанная оценка случайной величины не хуже, чем существующая оценка метода PERT; 2) Средняя погрешность при оценивании бета-величины математическим ожиданием равно 0,004484, методом PERT – 0,02538. Таким образом, результаты эксперимента подтвердили целесообразность использования предложенного подхода к оценке бета-величины вместо существующего подхода PERT.
1. Анализ специфики функционирования сложных обслуживающих систем позволил сформировать математическую модель распределнной вычислительной системы с несколькими центрами обработки данных, учитывающую случайную длительность обслуживания и ограничения на взаимную зависимость работ, а также временные и ресурсные ограничения, и позволяющую оптимизировать процесс ее функционирования с точки зрения обобщенного ресурсного критерия.
2. В результате анализа метода PERT, являющегося в настоящее время самым используемым методом для оценки длительности работ, был сформулирован и доказан ряд утверждений, положенных в основу метода, позволяющего получить более точную оценку длительности обслуживания отдельной работы по известным значениям дисперсии и моды.
3. Проведенный вычислительный эксперимент позволил обосновать эффективность полученных оценок длительности выполнения отдельных работ и их повышенную точность по сравнению с существующими аналогами. Глава 3 Оценка закона распределения длительности последовательно решаемых задач
Глава посвящена разработке аппарата, позволяющего оценить длительность выполнения множества последовательно решаемых задач с помощью аппарата теории вероятностей в предположении о бета распределении длительности отдельно решаемой задачи.
Экспериментальный анализ случайной величины, описывающей сумму бета величин приведен в первой части. Вторая часть главы посвящена разработке аналитического подхода к оценке суммы двух бета - величин. Оценка параметров итоговой случайной величины в предположении о ее распределении по закону бета и по нормальному закону описана в третьей части. В четвертой части приведен рекурсивный алгоритм, позволяющей численно оценить сумму произвольного числа случайных величин, каждая из которых распределена по закону бета со своими параметрами. Пятая часть посвящена экспериментальному обоснованию выдвинутой гипотезы об аппроксимации суммы бета-величин бета-распределением. Выводы приведены в шестой части главы.
Решается задача оценки закона распределения случайной величины, которая является сумма случайных величин, каждая из которых распределена по закону бета с параметрами pi и qi в интервале [ai,bi]. Как было сказано ранее, в методе PERT предполагается, что итоговая случайная величина распределена по нормальному закону. Это предположение основывается на центральной предельной теореме. Она утверждает, что сумма бесконечного числа одинаково распределенных случайных величин с математическим ожиданием а и дисперсией а2 распределена нормально [30]. Таким образом, для того, чтобы гарантировать нормальность суммы случайных величин, необходимо выполнение двух условий: - математические ожидания и дисперсии составляющих должны быть одинаковы; - количество этих величин должно быть очень велико.
Для выявления других факторов, влияющих на нормальность итогового закона распределения, проанализируем поведение нормального закона. Известно, что это симметричный закон с нулевым эксцессом. Следовательно, если все составляющие распределены симметрично, то итоговая величина предположительно будет также иметь симметричное распределение.
Проведем эксперименты, целью которых будет являться графическое представление случайной величины, полученной как сумма нескольких бета-величин, а также ее числовые характеристики [118]. Будем рассматривать заявку как прямую последовательность взаимно-зависимых работ.
Исходными данными для проведения эксперимента будут являться: - границы интервалов [ai,bi], в которых будут распределены слагаемые; - математические ожидания Mi каждой из этих величин. На выходе необходимо получить: - гистограмму итоговой случайной величины; - ее числовые характеристики. Сначала рассмотрим сумму двух одинаково распределенных бета-величин, обладающих существенной асимметрией. Без ограничения общности, пусть это будут величины, распределенные в интервале [5,10], имеющие математическое ожидание, равное 9.
Анализ аналитического подхода к оценке числовых характеристик искомой случайной величины
Одной из важнейших задач при оптимизации систем со стохастическими параметрами является оценка вероятностно-временных характеристик длительности выполнения заявки. Очевидно, что неотъемлемой характеристикой при формировании расписания является математическое ожидание соответствующей случайной величины. Однако, на практике диапазон возникающих задач существенно шире. В частности, для оценки вероятности завершения обслуживания заявки в определенном диапазоне необходимо знание закона распределения этой случайной величины с точностью до параметров.
Как отмечалось в главе 1, практически единственным методом, позволяющим анализировать вероятностно-временные характеристики момента завершения комплекса последовательно-параллельных работ, является метод PERT. Согласно этому методу, длительность обслуживания заявки является случайной величиной, распределенной по нормальному закону с параметрами a и а, определенными с помощью формул: а= М . (4.1) єКг и а= ГІЖ- (4-2) Здесь Kr обозначает критический путь. Таким образом, вероятность завершения обслуживания заявки к некоторому сроку оценивается следующим образом Р(п Т) = FHopM(a,a,T). (4.3) В случае, если у проекта имеется несколько критических путей, вместо формулы (4.2) используется формула: a = /max(D 1,...,,D n). (4.4) Для исследования точности формул (4.1) - (4.4) проанализируем специфику случайной величины г, определяющей длительность выполнения заявки. Пусть заявка задана множеством последовательно-параллельных работ со случайной длительностью. Пусть случайные величины ь…, к описывают моменты завершения каждой из работ проекта. Поскольку заявка будет выполнена только в том случае, когда будут выполнены все работы, она будет определяться как максимум из этих величин: r = max( ,..., k). (4.5) Таким образом, для определения случайной величины г\ необходимо описать случайные величины ь…, к. В частности, требуется знание их законов распределения с точностью до параметров. Для этого проанализируем специфику исследуемых случайных величин. Очевидно, что каждая из них может быть определена с помощью формулы: i =tm41 +dlit1- (46)
Здесь tнач_i - случайная величина, определяющая момент начала работы i, а dliti - ее длительность. Очевидно, что момент начала работы i определяется моментом завершения работы всех ее смежников. Для каждого из них аналогичным образом можно применить формулу (4.6). Исходя из этого, случайные величины ь… Дк можно переформулировать следующим образом. Пусть в заявке присутствует п различных путей pathb… ,pathn. Пусть случайная величина описывает суммарную длительность работ, присутствующих на пути і. Тогда случайная величина т, определенная по формуле (4.5), где случайные величины описывают длительность выполнения работ, стоящих на пути i, будет представлять собой длительность обслуживания всей заявки.
В главе 2 обосновано предположение о бета распределении длительности отдельной работы. В предыдущей главе было показано, что закон бета является достаточно хорошей аппроксимацией случайной величины, описывающей суммарную длительность множества последовательно выполняемых работ. Исходя из этого, математически задачу можно сформулировать следующим образом.
Пусть задано множество случайных величин =(ь…п), каждая из которых распределена по закону бета в своем интервале [ai,bi] с параметрами (рь qO, i=1,…,n. Рассматривается задача поиска закона распределения с точностью до параметров и числовых характеристик случайной величины, определенной формулой (4.5).
В настоящее время достаточно изученной является задача поиска максимумов из одинаково распределенных случайных величин. В частности, в работах [53, 55, 113] приведено исследование поведения максимумов для некоторых распределений. Однако, все существующие исследования основывались на предположении об идентичности случайных величин і,…,п. Очевидно, что и числовые характеристики этих величин в данном случае совпадают. В этом случае общая формула для описания функции распределения имеет вид:
Принципиальным отличием исследуемой задачи является более общий случай, когда каждая случайная величина имеет свой интервал распределения и свои параметры. Это означает, что законы распределения у разных случайных величин будут различны. В этом случае формула (4.8) перепишется в виде: + п(х). (х),2 ... пі(х)П 2 П (4 9)
Отметим основную сложность, возникающую при необходимости определения числовых характеристик для случайной величины (4.5). Во-первых, необходима предварительная оценка закона распределения каждой из случайных величин І5 i=1,…,n, а также ее параметров. При этом возникнет некоторая (пусть и небольшая) погрешность. Далее необходимо n раз вычислить интегралы, которые возможно взять лишь в численном виде. При этом неизбежно накопление погрешностей, что не позволит получить итоговый результат с приемлемой точностью. В частности, даже более простой и изученный случай, описанный формулами (4.7) и (4.8) в большинстве своем требует численного интегрирования для определения числовых характеристик или использования их оценок. В связи с этим, разработка подходов, позволяющих с одной стороны найти достаточно точную аппроксимацию закона распределения случайной величины (4.5) и ее параметров, а с другой - потратить на вычисление приемлемое время является весьма важной задачей.