Алгоритмы решения NP-трудных задач минимизации суммарного запаздывания и минимизации времени выполнения проекта и их применение в комбинаторной оптимизации

• Автор: Гафаров, Евгений Рашидович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Москва
• Количество страниц: 181 с. : ил.

1 Алгоритмы решения задачи 1 11 J2 Tj и ее частных случаев

1.1 Постановка задачи минимизации суммарного запаздывания

для одного прибора 1 11 Tj

1.2 Точный алгоритм решения задачи lj| 2}

1.3 Случай В задачи 1||

1.3.1 Случай В-1 и алгоритм его решения

1.3.2 Алгоритм В-1 модифицированный

1.3.3 Случай В-1 general и алгоритм его решения

1.4 Канонические примеры задачи 1|| ]Г] Tj

1.4.1 Проблема Четно-Нечетного Разбиения (ЧНР)

1.4.2 Канонические DL-примеры задачи 1||

1.4.3 Канонические LG-примеры задачи 1 ||]Г} Tj
1.4.4 Свойства канонических LG-примеров
1.5 Трудоемкость известных алгоритмов для некоторых частных
случаев задачи 1 || Y^Tj
1.5.1 Свойства канонических DL-примеров задачи 1|| Tj
1.5.2 Трудоемкость известных алгоритмов для канонических DL-примеров
1.5.3 Трудоемкость известньГх алгоритмов для случая BF 67 1.6 Метаэвристический подход решения задачи 1|| 52 Tj
.1.6.1 Алгоритм АСО для задачи 1|| Tj
1.6.2 Гибридный алгоритм
1.6.3 Эффективность алгоритмов для тестовых примеров Поттса и Ван Вассенхова
1.6.4 Эффективность алгоритмов для случая В
1.6.5 Эффективность алгоритмов для канонических DL-примеров
Графические алгоритмы решения задач Разбиение и Ранец
2.1 Алгоритм динамического программирования для задачи Ранец
2.2 Графический алгоритм для задачи Ранец
2.3 Трудоемкость графического алгоритма
2.4 Графический алгоритм для задачи Разбиение
2.4.1 Сокращение рассматриваемого интервала (схлопывание)
2.4.2 Пример
2.5 Трудоемкость Графического алгоритма для задачи Разбиение
2.6 Экспериментальная оценка трудоемкости Графического алгоритма
Исследование задач теории расписаний с отношениями
предшествования и ресурсными ограничениями
3.1 Постановка задачи построения расписания проекта с учетом ограничений на ресурсы (ПСРЭР)
3.1.1 Алгоритм диспетчеризации для задачи ЯСРЭР
3.1.2 Задача ИСРЭР с прерываниями обслуживания
требований
3.2 Относительная погрешность нижних оценок для задачи ПСРБР121
3.2.1 ЬВ0 - длина критического пути
3.2.2 ЬВ - максимальная загрузка ресурса
3.2.3 ЬВз - дополнение критического пути
3.2.4 Нижняя оценка М^огг1
3.2.5 Оценка ЬВю
3.3 Отношение оптимальных значений целевой функции для задач с прерываниями и без прерываний
3.3.1 Доказательство гипотезы для случая задачи КСРЭР с
одним ресурсом
3.4 Задача построения расписания для параллельных машин
3.5 Частный случай задачи ИСРБР с одним кумулятивным ресурсом мощности <^1 и Р]
3.6 Свойства задач построения расписания с ограничениями предшествования
3.6.1 Планарность сетевого графика для задач ШТРБР и РМ8150
3.6.2 Алгоритм укладки сетевого графика на плоскости

тогда
С2п('к) = Р(тГ 1) + Р2п-1 + Р2п = 5 + 2 п3Ь + 26 + 5п
= Ь + п3Ь + -5п — -А.
Известно, нто Ь + п3Ь = ^2п+1, тогда выполняется —5 < с2п(7г) — ^2п+1 < $■
Необходимо рассмотреть два подслучая, когда с2п(7г) > с?2га+1 и С2тг(^") ^ С^2п+11- С2п(7г) > Фы+1Рассмотрим расписание п1 следующего вида тг'
(тгь ^2п-1, р2п+1, Ргп, 7Г2).
Р’(тг) - Н(тг') = Т2п(тг) + Т2п+1(тг) - (Т2п(тг') +
+ Т2п+1{1т')) = (Т2п+1(тг) - Г2п+1(V)) - (Т2п(тг')
-72„(ТГ)) = (Р2п+1 + (С2п(7г)-^2п+1))-Р2п+1 = С2п(7г)-£г2г1+1 > О2- С2п(7г) < с/2п+1'
При ЭТОМ С2п(7г) > С?2п, так как С?2п+1 -с?2„ = 6 И С?2п+1 -с2п(7г) <

Распишем структуру расписания 7г.
= (7Гц, Ии_1, р2г,7Г12, р2„_1,И21г, р2п+Ъ 7Г22),
ГДе |{7Г22}| = !-1Де {^2(г-1)-1, %-1)}-
Если А = р2(,_1)_1, то транспозиция соседних требований ^(г-1)-1 и Рг^-1) согласно правилу ЭРТ не увеличит значение целевой функции.
Пусть X — Рг(г—1)- При расписании 7Г запаздывает (та + 1) требование.