Введение
ГЛАВА 1. Современное состояние теории расписаний 17
1.1. Актуальность задач теории расписаний 17
1.2. Проблемы вычислительной сложности задач теории расписаний 19
1.3. Регулярные методы решения задач теории расписаний 25
1.3.1. Метод динамического программирования 26
1.3.2. Метод ветвей и границ 27
1.3.3. Эвристические алгоритмы 30
1.4. Технология решения многокритериальных задач оптимизации 32
1.5. Типовые задачи обслуживания стационарных объектов
перемещающимся процессором 35
Выводы по главе 1 37
ГЛАВА 2. Однокритериальные задачи обслуживания стационарных объектов перемещающимся процессором 38
2.1. Двурейсовые задачи обслуживания 38
2.1.1. Математическая модель 1DZ1 38
2.1.2. Постановки однокритериальных оптимизационных задач 40
2.1.3. Вычислительная сложность задач 1DZ1(sP) и 1DZ1(mP) 40
2.2. Однорейсовые задачи обслуживания 44
2.2.1. Математическая модель 1DZ2 44
2.2.2. Постановки однокритериальных оптимизационных задач 45
2.2.3. Алгоритмы решения задач 1DZ2(sP) и 1DZ2(mP) 45
2.2.4. Иллюстрирующий пример и результаты вычислительных экспериментов 49
2.3. Обобщенные задачи обслуживания 53
2.3.1. Математическая модель 1DZ3 53
2.3.2. Постановки однокритериальных оптимизационных задач 53
2.3.3. Алгоритмы решения задач 1DZ3(sP) и 1DZ3(mP) 54
2.3.4. Иллюстрирующий пример и результаты вычислительных экспериментов 55
2.4. Задачи обслуживания в двумерной рабочей зоне 58
2.4.1. Математическая модель 2DZ3 58
2.4.2. Постановки однокритериальных оптимизационных задач 59
2.4.3. Алгоритмы решения задач 2DZ3(sP) и 2DZ3(mP) 60
2.4.4. Иллюстрирующий пример 61
Выводы по главе 2 63
ГЛАВА 3. Многокритериальные задачи обслуживания стационарных объектов перемещающимся процессором 64
3.1. Двурейсовые задачи обслуживания 64
3.1.1. Постановки многокритериальных задач для модели 1DZ1 64
3.1.2. Алгоритмы решения задач 1DZ1(T,sP), 1DZ1(T,mP), 1DZ1(sP) и 1DZ1(mP) 65
3.1.3. Алгоритм решения задачи 1DZ1(Tc,T) 69
3.1.4. Иллюстрирующие примеры и результаты вычислительных экспериментов 73
3.2. Однорейсовые задачи обслуживания 80
3.2.1. Постановки многокритериальных задач для модели 1DZ2 80
3.2.2. Алгоритмы решения задач 1DZ2(L,T,sP), 1DZ2(L,T,mP), 1DZ2(T,sP) и 1DZ2(T,mP) 81
3.2.3. Иллюстрирующий пример и результаты вычислительных экспериментов 85
3.3. Обобщенные задачи обслуживания 92
3.3.1. Постановки многокритериальных задач для модели 1DZ3 92
3.3.2. Алгоритмы решения задач 1DZ3(L,T,sP), 1DZ3(L,T,mP), 1DZ3(T,sP) и 1DZ3(T,mP) 93
3.3.3. Вычислительная сложность задач 1DZ3(T,sP), 1DZ3(T,mP), 1DZ3(L,T,sP) и 1DZ3(L,T,mP) 96
3.3.4. Иллюстрирующий пример и результаты вычислительных экспериментов 97
3.4. Задачи обслуживания в двумерной рабочей зоне 104
3.4.1. Постановки многокритериальных задач для модели 2DZ3 104
3.4.2. Алгоритмы решения задач 2DZ3(L,T,sP), 2DZ3(L,T,mP), 2DZ3(T,sP) и 2DZ3(T,mP) 105
3.4.3. Иллюстрирующий пример 108
Выводы по главе 3 110
ГЛАВА 4. Алгоритмы синтеза субоптимальных стратегий обслуживания 111
4.1. Проблемы сравнения двух множеств оценок 111
4.2. Идеология эволюционно-генетических вычислений 114
4.2.1. Обобщенная структура генетического алгоритма 114
4.2.2. Оператор скрещивания в задачах синтеза стратегий обслуживания 117
4.3. Эволюционно-генетический алгоритм синтеза совокупности субэффективных оценок для решения задач, сформулированных в рамках моделей 1DZ3 и 2DZ3 120
4.3.1. Алгоритм решения однокритериальных задач 121
4.3.2. Алгоритм для решения многокритериальных задач 123
4.4. Результаты вычислительных экспериментов 126
Выводы по главе 4 131
ГЛАВА 5. Программный комплекс поддержки диспетчерского управления обслуживанием рассредоточенных объектов перемещающимся процессором 132
5.1. Обоснование выбора языка программирования Python 132
5.2. Программный комплекс поддержки оперативного управления обслуживанием рассредоточенных объектов 134
5.2.1. Назначение и функциональные возможности 134
5.2.2. Архитектура программного комплекса 135
5.2.3. Схема работы с программным комплексом 137
Выводы по главе 5 138
Заключение 139
Литература
