Ви є тут

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

Автор: 
Гафаров Евгений Рашидович
Тип роботи: 
диссертация кандидата физико-математических наук
Рік: 
2008
Кількість сторінок: 
181
Артикул:
1051
179 грн
Додати в кошик

Вміст

Оглавление
Введение б
1 Алгоритмы решения задачи 1 7 и ее частных случаев
1.1 Постановка задачи минимизации суммарного запаздывания
для одного прибора 1 2
1.2 Точный алгоритм решения задачи 1 2 .
1.3 Случай В задачи 2
1.3.1 Случай В1 и алгоритм его решения.
1.3.2 Алгоритм В1 модифицированный.
1.3.3 Случай В1 и алгоритм его решения.
1.4 Канонические примеры задачи 2
1.4.1 Проблема ЧетноНечетного Разбиения ЧНР
1.4.2 Канонические примеры задачи 1 2
1.4.3 Канонические примеры задачи 1 2
1.4.4 Свойства канонических примеров
1.5 Трудоемкость известных алгоритмов для некоторых частных
случаев задачи 1 2
1.5.1 Свойства канонических примеров задачи 1 2
1.5.2 Трудоемкость известных алгоритмов для канонических примеров
1.5.3 Трудоемкость известиx алгоритмов для случая
1.6 Метаэвристический подход решения задачи 20
.1.6.1 Алгоритм АСО для задачи 1 2 .
1.6.2 Гибридный алгоритм.
1.6.3 Эффективность алгоритмов для тестовых примеров
Попса и Ван Вассенхова
1.6.4 Эффективность алгоритмов для случая В1
1.6.5 Эффективность алгоритмов для канонических
примеров .
Графические алгоритмы ешения задач Разбиение и Ранец
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 Относительная погрешность нижних оценок для задачи
3.2.1 длина критического пути .
3.2.2 ЬВ максимальная загрузка ресурса
3.2.3 дополнение критического пути.
3.2.4 Нижняя оценка ii .
3.2.5 Оценка .
3.3 Отношение оптимальных значений целевой функции для задач с прерываниями и без прерываний .
3.3.1 Доказательство гипотезы для случая задачи с одним ресурсом
3.4 Задача построения расписания для параллельных машин . .
3.5 Частный случай задачи с одним кумулятивным ресурсом мощности i и 1.
3.6 Свойства задач построения расписания с ограничениями предшествования
3.6.1 Планарность сетевого графика для задач и
3.6.2 Алгоритм укладки сетевого графика на плоскости . .
3.6.3 Решение обратного примера для задач и
3.7 Метаэвристический алгоритм решения задачи
3.7.1 Алгоритм АСО в рамках 1СУСО .
Заключение
Список использованных источников