Введение 4
Глава 1. Предварительные сведения 5
1.1. Задача о расписании 5
1.2. Метод имитации отжига (Simulated annealing) 6
1.2.1. Физическая мотивировка 6
1.2.2. Обозначения 6
1.2.3. Формальная схема метода 7
Глава 2. Применение метода отжига к задаче о расписании ... 9
2.1. Представление расписания 11
2.2. Алгоритм генерации начального состояния 12
2.3. Операция преобразования расписания 14
2.4. Функции перехода в новое состояние 15
2.4.1. Первая функция перехода в новое состояние 15
2.4.2. Вторая функция перехода в новое состояние 16
2.4.3. Третья функция перехода в новое состояние 16
Глава 3. Статистические результаты применения метода к задаче 18
Заключительные замечания 19
Список алгоритмов 20
Литература
Известно, что общая задача о составлении расписания является NP-полной [1]. Существует два подхода к решению этой задачи: нахождение точного решения (подходит для решения небольших задач или единовременного решения каких-то конкретных задач, в силу своего происхождения требующих точного решения) и поиск приближенного решения (подходит для автоматической обработки большого количества задач). В последнем случае мы хотим уменьшить среднюю ошибку по большому массиву задач, при этом сохранив полиномиальную эффективность. Первый подход реализуется такими алгоритмами как полный перебор или метод ветвей и границ [1]. Второй подход реализуется бесчисленным множеством эвристических алгоритмов, об одном из которых пойдет речь в данной работе.
Здесь мы будем обсуждать эффективность эвристического алгоритма имитации отжига для решения общей задачи о расписании.
Работа поделена на разделы: “Введение”, “Глава 1: Предварительные сведения”, “Глава 2: Метод имитации отжига”, “Глава 3: Статистические результаты применения метода к задаче”, “Заключительные замечания” и “Список литературы”. Наиболее важными из них являются Глава 2, в которой подробно описан алгоритм, большей частью реализованный на псевдокоде, и Глава 3, в которой мы приводим статистический анализ эффективности нашей реализации (про реализацию см. далее).
Описываемый алгоритм реализован нами в виде мультиплатформенной программы на языке программирования C++, исходный код которой опубликован в сети
В работе были описаны, реализованы и проанализированы разные вариации метода имитации отжига применительно к общей задаче о расписании. Как и стоило ожидать лучший результат дает вариант алгоритма, где для перехода к новому расписанию два задания меняются местами, а количество итераций линейно зависит от количества заданий (этого следовало ожидать, так как жадный алгоритм, используемый для получения начального решения старается распределить задания равномерно по процессорам).
В итоге мы получили полиномиальный алгоритм, средняя ошибка которого на наших экспериментальных данных составила всего 1.06601.
