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

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

Автор: Столяр, Артем Александрович

Шифр специальности: 05.13.18

Научная степень: Кандидатская

Год защиты: 2004

Место защиты: Новосибирск

Количество страниц: 121 с. ил.

Артикул: 3299303

Автор: Столяр, Артем Александрович

Стоимость: 250 руб.

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

ОГЛАВЛЕНИЕ
Введение .
Глава 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, сокращая тем самым дерево поиска.

Рекомендуемые диссертации данного раздела

28.06.2016

+ 100 бесплатных диссертаций

Дорогие друзья, в раздел "Бесплатные диссертации" добавлено 100 новых диссертаций. Желаем новых научных ...

15.02.2015

Добавлено 41611 диссертаций РГБ

В каталог сайта http://new-disser.ru добавлено новые диссертации РГБ 2013-2014 года. Желаем новых научных ...


Все новости

Время генерации: 0.243, запросов: 244