Алгоритмы локального поиска для задачи календарного планирования с ограниченными ресурсами

• Автор: Столяр, Артем Александрович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Новосибирск
• Количество страниц: 121 с. : ил.

ОГЛАВЛЕНИЕ
Введение .

Глава 1. О концентрации локальных оптимумов .

1.1. Окрестности

1.1.1. Окрестность 15

1.1.2. Окрестность 25

1.1.3. Окрестность Аз5 .

1.1.4. Задача о многомерном рюкзаке

1.2. Библиотека тестовых задач.

1.3. Экспериментальные исследования .

1.3.1 Исследование зависимости числа локальных оптимумов

от входных данных задачи .
1.3.2. Исследование концентрации локальных оптимумов
Глава 2. Новые жадные алгоритмы .
2.1. Метод параллельного составления расписаний .
2.2. Вероятностные жадные стратегии ..
2.2.1. Сортировка по временным задержкам
2.2.2. Использование решения задачи на узкое место
2.2.3. Использование решения задачи о многомерном рюкзаке
2.3. Локальные улучшения
2.4. Экспериментальные исследования .
2.4.1. Сравнение жадных стратегий .
2.4.2. Внесение рандомизации
2.4.3. Локальный спуск.
2.4.4. Сравнение с другими алгоритмами
Глава 3. Поиск с запретами и чередованием окрестностей .
3.1. Окрестности
3.2. Общая схема.
3.2.1. Построение начального решения.
3.2.2. Вероятностный поиск с запретами
3.3. Экспериментальные исследования .
3.3.1. Эффект чередующихся окрестностей .
3.3.2. Размер окрестности и ее рандомизация .
3.3.3. Влияние списка запретов
3.3.4. Выбор начального решения .
3.3.5. Интенсификация поиска
3.3.6. Сравнение с другими алгоритмами
Глава 4. Эволюционные алгоритмы
4.1. Стратегия связывающих путей
4.2. Построение связывающего пути .
4.3. Экспериментальные исследования .
4.3.1. Свойства оператора скрещивания
4.3.2. Выбор порождающей пары .
4.3.3. Выбор начальной популяции
4.3.4. Комбинация с локальным поиском.
4.3.5. Сравнение алгоритмов локального поиска
4.3.6. Сравнение с мировым уровнем.
Заключение .
Список литературы


Использование таких приемов как правила доминирования, нижние оценки, непосредственный отбор [] позволяет в большинстве случаев сократить дерево поиска. В зависимости от конкретного метода используются различные схемы ветвления и способы отсечения. В работе [] предлагается алгоритм, основанный на так называемом дереве предшествований. Процедура начинается с присвоения начальной фиктивной работе нулевого момента начала. Дп = {з Р) С Я- Для таких работ выполнено с+ < ву Отношения в О называются дизъюнкциями, и обозначаются через (г — 3). Сюда относятся работы, для которых выполнено либо (г —»• Я> либо у —> г). Множество N содержит пары работ, которые выполняются параллельно в течение некоторого периода времени. Если Со — множество пар, связанных условиями предшествования, Д) — множество пар, которые не могут выполняться одновременно ввиду ограничений по ресурсам, а Д — множество всех оставшихся пар, то схема (Со, Д), 0, Д) будет выступать в качестве корневой вершины в дереве поиска. Ветвление происходит путем перемещения пары из ^ в I), либо в N. С помощью специальных правил [] удается пополнить множества С, С, и А7, сокращая тем самым дерево поиска.