Введение
1 Распределительные задачи теории расписаний и методы их решения 20
1.1 Распределительные задачи в технике, технологиях и научных исследованиях 20
1.2 Сущность и математическая модель распределительной задачи и ее однородного варианта 23
1.2.1 Основные понятия и базовая структура распределительной задачи 23
1.2.2 Математическая модель однородной распределительной задачи 28
1.2.3 Критериальная оценка решений однородной распределительной задачи 30
1.3 Анализ методов решения однородной распределительной задачи 32
1.3.1 Точные методы решения однородных распределительных задач 33
1.3.2 Списочные методы приближенного решения однородных распределительных задач 38
1.3.3 Эвристические методы приближенного решения оптимизационных задач 42
1.4 Выводы по первой главе 54
2 Построение сравнительной базы для имитационного исследования новых алгоритмов решения рз 56
2.1 Задачи и возможности построения эталонных алгоритмов решения ОРЗ 56
2.1.1 Перспективы сравнительного исследования новых алгоритмов решения РЗ 56
2.1.2 Планирование экспериментального исследования ресурсно-временных возможностей точных алгоритмов решения ОРЗ 57
2.2 Исследование ресурсно-временных возможностей алгоритма полного перебора при решении ОРЗ 59
2.3 Анализ ресурсно-временных возможностей АР при решении ОРЗ 65
3
2.4 Комбинационно модифицированный алгоритм Романовского точного решения ОРЗ 69
2.4.1 Исследование возможных способов повышения быстродействия АР при решении ОРЗ 69
2.4.2 Комбинационная модификация АР точного решения ОРЗ 74
2.4.3 Пример применения комбинационно модифицированного алгоритма Романовского 76
2.5 Экспериментальное исследование ресурсных характеристик
комбинационно модифицированного АР 79
2.5.1 Исследование ресурсной эффективности КМАР при решении РЗ малой размерности 79
2.5.2 Расширенное исследование ресурсной эффективности КМАР на трех исполнительной системе 83
2.5.3 Расширенное исследование ресурсной эффективности КМАР на четырех исполнительной системе 87
2.5.4 Исследования ресурсной эффективности КМАР на исполнительной системе с m>4 91
2.6 Выводы по второй главе 99
3 Структурная модификация алгоритма романовского для быстрого приближенного решения однородных распределительных задач 101
3.1 Модификация алгоритма Романовского методом глубокого отката и максимальной загрузки 101
3.1.1 Исследование ресурсоемких для КМАР вариантов РЗ и возможных путей их решения 101
3.1.2 Ресурсоэффективная модификация КМАР максимизацией загрузки исполнителей и глубоким откатом 108
3.1.3 Структурно-модифицированный алгоритм решения z-задачи в методе Романовского 110
3.1.4 Пример применения структурно-модифицированного алгоритма Романовского 112
3.1.5 Перспективы расширенного использования структурно-модифицированного алгоритма Романовского 115
3.2 Экспериментальное исследование эффективности СМАР при решении РЗ
малой размерности 116
3.2.1 Исследование ресурсно-временных характеристик СМАР 116
3.2.2 Расширенное исследование ресурсных характеристик на трех и четырех исполнительных системах 121
3.2.3 Исследование точностных характеристик СМАР 123
3.3 Экспериментальное исследование эффективности СМАР при решении РЗ
повышенной размерности 127
3.3.1 Планирование эксперимента по исследованию СМАР и разработка показателей оценки его результатов 127
3.3.2 Исследование решения ОРЗ на оптимальность 131
3.3.3 Исследование точностных характеристик СМАР на основе ПФЭ 134
3.3.4 Расширенное исследование ресурсных характеристик структурно-модифицированного алгоритма Романовского 137
3.4 Дополнительные экспериментальные исследования эффективности СМАР
на повышенной размерности РЗ 141
3.4.1 Исследование ресурсно-точностных свойств СМАР при решении РЗ для 3-5 исполнительной системы и широкого диапазона размеров заданий 141
3.4.2 Исследование ресурсно-точностных свойств СМАР при решении РЗ для 5-7 исполнительной системы и дополнительно расширенного диапазона размеров заданий 146
3.4.3 Выборочные исследования ресурсно-точностной эффективности СМАР на повышенной размерности РЗ 149
3.5 Исследование возможных путей улучшения точностной эффективности 3.6 Выводы по третьей главе 154
4 Исследование селективно-перестановочного алгоритма приближенного решения орз и методов улучшения его точностной эффективности 156
4.1 Решение ОРЗ на основе комбинированного использования СМАР и СПА с
одинарными перестановками 156
4.1.1 Условия комбинированного применения СМАР и СПА с одинарными перестановками для решения ОРЗ 156
4.1.2 Исследование точностной эффективности СПАО при решении РЗ малой размерности 157
4.1.3 Расширенное исследование точностной эффективности СПАО на 4-х исполнительной системе 160
4.1.4 Анализ возможных способов повышения точности работы СПАО 163
4.2 Селективно-перестановочный алгоритм решения ОРЗ с использованием мультиперестановок 164
4.2.1 Базовые понятия и определения СПА с мультиперестановками 164
4.2.2 Селективно-перестановочный алгоритм решения ОРЗ с использованием мультиперестановок 170
4.3 Решение ОРЗ на основе комбинированного использования СМАР и СПА с
мультиперестановками 172
4.3.1 Исследование точностной эффективности комбинированного алгоритма «СПАО-СПАМ» на четырех исполнительной системе 172
4.3.2 Исследование точностной эффективности комбинации алгоритма «СПАО-СПАМ» при решении РЗ повышенной размерности 177
4.3.3 Исследование возможных способов повышения точности работы СПАМ 181
4.4 Селективно-перестановочный алгоритм решения ОРЗ с использованием эквивалентных перестановок 184
4.4.1 Эквивалентные преобразования распределительных матриц 184
4.4.2 Селективно-перестановочный алгоритм решения ОРЗ с использованием эквиперестановок 186
4.4.3 Повышение точности решения ОРЗ на основе комбинации СМАР и СПА с эквиперестановками 188
4.5 Исследование ресурсно-временных характеристик СПА 196
4.5.1 Исследование ресурсно-временных характеристик СПА при решении РЗ малой размерности 196
4.5.2 Исследование ресурсно-временных характеристик СПА на 4-х исполнительной системе 200
4.5.3 Исследование ресурсно-временных характеристик СПА при решении РЗ повышенной размерности 205
4.6 Выводы по четвертой главе 211
Заключение 212
Список сокращений 214
Список используемых источников 215
