Введение
1 Алгоритмы решения задачи 1 11 2} и ее частных случаев 11
1.1 Постановка задачи минимизации суммарного запаздывания для одного прибора 1 11 J2 Tj 12
1.2 Точный алгоритм решения задачи 11|5^Tj 14
1.3 Случай В задачи l\\J2Tj 18
1.3.1 Случай В-1 и алгоритм его решения 18
1.3.2 Алгоритм В-1 модифицированный 21
1.3.3 Случай В-1 general и алгоритм его решения 23
1.4 Канонические примеры задачи 1|| ]>] 7) 31
1.4.1 Проблема Четно-Нечетного Разбиения (ЧНР) 31
1.4.2 Канонические DL-примеры задачи l|j Yl^j 32
1.4.3 Канонические LG-примеры задачи 1|| ^Tj 34
1.4.4 Свойства канонических LG-примеров 35
1.5 Трудоемкость известных алгоритмов для некоторых частных случаев задачи 54
1.5.1 Свойства канонических DL-примеров задачи 1|| X) Т,
1.5.2 Трудоемкость известных алгоритмов для канонических DL-примеров 65
1.5.3 Трудоемкость известных алгоритмов для случая BF 67
1.6 Метаэвристический подход решения задачи 11|^Tj 71
1.6.1 Алгоритм АСО для задачи 1|| J^Tj 71
1.6.2 Гибридный алгоритм 74
1.6.3 Эффективность алгоритмов для тестовых примеров Поттса и Ван Вассенхова 77
1.6.4 Эффективность алгоритмов для случая В-1 81
1.6.5 Эффективность алгоритмов для канонических DL-примеров 83
2 Графические алгоритмы решения задач Разбиение и Ранец 87
2.1 Алгоритм динамического программирования для задачи Ранец 88
2.2 Графический алгоритм для задачи Ранец 91
2.3 Трудоемкость графического алгоритма 97
2.4 Графический алгоритм для задачи Разбиение 98
2.4.1 Сокращение рассматриваемого интервала (схлопывание) 101
2.4.2 Пример 101
2.5 Трудоемкость Графического алгоритма для задачи Разбиение 105
2.6 Экспериментальная оценка трудоемкости Графического алгоритма 107
3 Исследование задач теории расписаний с отношениями предшествования и ресурсными ограничениями 112
3.1 Постановка задачи построения расписания проекта с учетом ограничений на ресурсы (RCPSP) 113
3.1.1 Алгоритм диспетчеризации для задачи RCPSP . 116
3.1.2 Задача RCPSP с прерываниями обслуживания требований 119
3.2 Относительная погрешность нижних оценок для задачи RCPSP 121
3.2.1 LBQ - длина критического пути 122
3.2.2 LB\ - максимальная загрузка ресурса 122
3.2.3 LBs - дополнение критического пути 123
3.2.4 Нижняя оценка Mingozzi 124
3.2.5 Оценка LBLG 128
3.3 Отношение оптимальных значений целевой функции для задач с прерываниями и без прерываний 132
3.3.1 Доказательство гипотезы для случая задачи RCPSP с одним ресурсом 138
3.4 Задача построения расписания для параллельных машин . 144
3.5 Частный случай задачи RCPSP с одним кумулятивным ресурсом мощности Qi и Pj — 1 147
3.6 Свойства задач построения расписания с ограничениями предшествования 150
3.6.1 Планарность сетевого графика для задач RCPSP и PMS150
3.6.2 Алгоритм укладки сетевого графика на плоскости . 153
3.6.3 Решение обратного примера для задач RCPSP и PMS 157
3.7 Метаэвристический алгоритм решения задачи RCPSP . 159
3.7.1 Алгоритм АСО в рамках 1С:УСО 164
Заключение 166
Список использованных источников 169
