Введение
1 Постановка задачи 10
1.1 Содержательное описание задачи 10
1.2 Модель входных данных 12
1.3 Механизмы обеспечения надежности 12
1.4 Модель расписания 14
1.5 Вычисление времени выполнения расписания 17
1.6 Вычисление надежности 19
1.7 Математическая постановка задачи 20
1.8 Выводы 22
2 Обзор возможных подходов к построению алгоритмов решения задачи и алгоритмов решения близких задач 23
2.1 Цель обзора 23
2.2 Полный перебор 23
2.3 Метод ветвей и границ 24
2.4 Жадные алгоритмы 25
2.5 Алгоритм имитации отжига 27
2.6 Генетические алгоритмы 29
2.7 Выводы 31
3 Алгоритм построения расписания 33
3.1 Общая схема алгоритма 33
3.2 Операции преобразования расписания 34
3.3 Стратегии применения операций . 39
3.4 Условие перехода к новому расписанию и критерий останова. 43
3.5 Вычислительная сложность одной итерации алгоритма 44
3.6 Выводы 46
4 Исследование свойств алгоритма 47
4.1 Асимптотическая сходимость алгоритма 47
4.2 Метрика в пространстве расписаний 54
4.2.1 Метрика L(A, B) 54
4.2.2 Метрика H(A, B) 55
4.2.3 Связь между метриками L(A, B) и H(A, B) 59
4.2.4 Оценка для L(A, B) 62
4.3 Экспериментальное исследование алгоритма 62
4.3.1 Оценка точности на модельных данных 62
4.3.2 Оценка точности на совместимых исходных данных 72
4.3.3 Сравнение законов понижения температуры 75
4.4 Выводы 79
5 Инструментальная система 80
5.1 Требования к системе 80
5.2 Описание системы 80
5.2.1 Описание архитектуры системы 80
5.2.2 Графический пользовательский интерфейс 86
5.2.3 Подсистема для построения вычислительных систем для обработки данных от фазированных антенных решеток 88
5.3 Выводы 90
Заключение 92
Литература 93
