Введение
1. Распределительные задачи теории расписаний и методы их решения 15
1.1. Параллельное упорядочивание как важнейший этап составления расписаний 15
1.2. Математическое описание задачи параллельного упорядочивания 18
1.2.1. Работы и операции при составлении расписаний 18
1.2.2. Критерии составления расписаний 20
1.2.3. Характеристика и функциональная классификация задач теории расписаний 21
1.2.4. Математическая модель классической распределительной задачи 24
1.3. Основные аспекты выбора методов решения задач теории расписаний 27
1.4. Детерминированные методы решения распределительных задач 28
1.4.1. Целочисленное линейное программирование 28
1.4.2. Методы ветвей и границ. Заполнение работ по устройствам 30
1.4.3. Методы ветвей и границ. Заполнение устройств по работам 31
1.4.4. Приближенные методы списочного составления расписаний. Алгоритм критического пути 33
1.4.5. Возможности и сферы применения детерминированных методов 37
1.5. Эвристические и вероятностные методы решения распределительных задач 38
1.5.1. Предпосылки появления приближенных вероятностных и эвристических методов.. 38
1.5.2. Комбинаторно-эвристический поиск. 40
1.5.3. Методы отжига 40
1.5.4. Метод роящихся частиц (particle swarm) 41
1.5.5. Табуированный поиск (Tabu Search) 42
1.5.6. Эволюционно-генетический подход 43
1.6. Эволюционно-генетические методы решения распределительных задач 44
1.6.1. Общая характеристика эволюционно генетического подхода 44
1.6.2. Представление данных в генах 46
1.6.3. Стратегии отбора 46
1.6.4. Стратегии формирования нового поколения 48
1.6.5. Генетические операторы 49
1.6.6. Модели ЭГА 51
1.6.7. Некоторые обобщения 52
1.7. Выводы по первой главе 55
/. 7.1. Причины использования приближенных алгоритмов в распределительных задачах.. 55
1.7.2. Основания для исследования возможностей эволюционно-генетических аігоритмов в
теории расписаний 55
1.7.3. Основные направления исследований по использованию эволюционно-генетических алгоритмов в теории расписаний 56
1.7.4. Проблемы инструментальной поддержки исследований эволюционно-генетических алгоритмов в теории расписаний 56
2. Эволюционно-генетическая модель распределительной задачи и ее основные свойства 57
2.1. Побитовая генетическая модель распределительной задачи 57
2.1.1. Влияние сущностных свойств распределительных задач теории расписаний на генетические модели 57
2.1.2. Модель гена распределительной задачи теории расписаний 59
2.1.3. Примеры построения и использования побитового гена распределительной задачи. 64
2.2. Эволюционная модель распределительной задачи и ее основные составляющие 67
2.2.1. Оператор кроссовера в распределительной задаче 67
2.2.2. Оператор мутации в распределительной задаче 72
2.2.3. Оператор инверсии распределительной задаче 74
2.2.4. Оператор выбора в распределительной задаче 77
2.3. Эволюционная модель распределительной задачи 78
2.3.1. Итерационный процесс поиска ЭТА 78
2.3.2. Пример организации итерационного поиска в ЭГА 81
2.3.3. Особенности системы поиска эволюционного алгоритма 83
2.4. Сравнительный анализ примеров решений 85
распределительной задачи эвристическими алгоритмами 85
2.4.1. Задачи и алгоритмы для сравнения 85
2.4.2. Решение задачи эволюционно-генетическим алгоритмом 86
2.4.3. Решение задачи методом отжига 88
2.4.4. Решение задачи методом роящихся частиц 89
2.4.5. Сравнительная оценка результатов применения к РЗ различных методов и алгоритмов решения 91
2.5. Выводы по ВТОРОЙ ГЛАВЕ 95
2.5.1. Состоятельность эволюционно-генетических алгоритмов при решении распределительных задач 95
2.5.2. Основные направления исследования и оптимизации свойств эволюционно-генетических алгоритмов в теории расписаний. 95
3. Исследование эволюционной генетической модели распределительной задачи 96
3.1. Система «РЗ-ЭГА», задачи и методы её исследования 96
3.2. Исследование свойств «РЗ-ЭГА» для 2-х устройств 973
3.2.1. Исследование точностных показателей 97
3.2.2. Исследование показателей быстродействия 100
3.2.3. О перспективных направлениях дальнейших исследований системы «РЗ-ЭГА» 102
3.3. Некоторые результаты исследования свойств системы «рз-эга» для 3-х устройств 103
3.3.1. Исследование нестабильности ЭГА для 3-х устройств 103
3.3.2. Предварительные выводы о нестабильности ЭГА 105
3.4. Исследование влияния параметров эга на вероятностную точность решения РЗ 106
3.4.1. Постановка задачи исследования 106
3.4.2. Широкодиапазонное исследование 4-х факторного пространства ЭГА 108
3.4.3. Исследование найденного перспективного диапазона факторного пространства.. 111
3.4.4. Реализация стратегии крутого восхождения для отыскания области экстремума ИЗ
3.4.5. Исследование подозрительного на экстремум диапазона. 114
3.4.6. Градиентный поиск в экстремальной области по факторам X j иХ ^ U7
3.4.7. Детальное исследование предполагаемой экстремальной области 118
3.4.8. Эксперимент по проверке экстремальной области 119
3.5. Влияние весов работ в распределении на степень точности эга 122
3.6. Выводы по ТРЕТЬЕ ГЛАВЕ 128
3.6.1. Исследование показателей системы «РЗ-ЭГА» для двух устройств 128
3.6.2. Исследование показателей системы «РЗ-ЭГА» для трех устройств 128
3.6.3. Исследование показателей системы «РЗ-ЭГА» в зависимости от распределения весов работ 129
4. Исследование феномена вероятностной точности решения распределительной задачи при использовании эга 130
4.1. Теоретико-экспериментальное обоснование оценки эффективности эга вероятностной точностью 130
4.1.1. Теоретические предпосылки оценки эффективности ЭГА вероятностной точностью 130
4.1.2. Экспериментальное исследование влияния кол-ва заданий на эффективность ЭГА 131
4.1.3. Исследование стабильности работы ЭГА 134
4.1.4. Поиск наихудших распределений для ЭГА 137
4.2. Имитационно-статистический подход к оценке оптимальности решения эга... 141
4.2.1. Исследование распределительной задачи «РЗ-ЭГА» на наличие закономерностей формирования вероятностной точности 141
4.2.2. Теоретические основы оценки заданных вероятностно точностных условий решения РЗ 144
4.2.3. Предельная ресурсная оценка решения РЗ параллельными ЭГА 146
4.3. Исследование быстродействия применения пакетной обработки 149
4.3.1. Предпосылки нестабильности времени выполнения операций ЭГА 149
4.3.2. Экспериментальное исследование временных характеристик при фиксированном порядке выполнения ЭГА 151
4.3.3. Экспериментальное исследование временных характеристик при свободном порядке выполнения ЭГА 152
4.3.4. Методика оценки верхней границы по времени выполнения ЭГА 154
4.4.. Исследование алгоритма адаптации уровня мутации в процессе решения 156
4.5. Выводы по четвертой главе 161
5. Программный комплекс «projectsheduler» имитационного моделирования решения распределительной задачи 162
5.1. Функциональная структура пк 162
5.2. Объектно-ориентированное конструирование функциональных блоков 165
5.3. Структура баз данных пк projectsheduler 168
5.4. Интерфейс пк projectsheduler и работа с ним 173
Заключение 187
Список использованных источников 189
Приложения 199
