Тема: МЕТОД ИМИТАЦИИ ОТЖИГА ДЛЯ ЗАДАЧИ С РАСПИСАНИИ С ПАРАЛЛЕЛЬНЫМИ ПРОЦЕССОРАМИ

Известно, что общая задача о составлении расписания является NP-полной [1]. Существует два подхода к решению этой задачи: нахождение точного решения (подходит для решения небольших задач или единовременного решения каких-то конкретных задач, в силу своего происхождения требующих точного решения) и поиск приближенного решения (подходит для автоматической обработки большого количества задач). В последнем случае мы хотим уменьшить среднюю ошибку по большому массиву задач, при этом сохранив полиномиальную эффективность. Первый подход реализуется такими алгоритмами как полный перебор или метод ветвей и границ [1]. Второй подход реализуется бесчисленным множеством эвристических алгоритмов, об одном из которых пойдет речь в данной работе.
Здесь мы будем обсуждать эффективность эвристического алгоритма имитации отжига для решения общей задачи о расписании.
Работа поделена на разделы: “Введение”, “Глава 1: Предварительные сведения”, “Глава 2: Метод имитации отжига”, “Глава 3: Статистические результаты применения метода к задаче”, “Заключительные замечания” и “Список литературы”. Наиболее важными из них являются Глава 2, в которой подробно описан алгоритм, большей частью реализованный на псевдокоде, и Глава 3, в которой мы приводим статистический анализ эффективности нашей реализации (про реализацию см. далее).
Описываемый алгоритм реализован нами в виде мультиплатформенной программы на языке программирования C++, исходный код которой опубликован в сети
Купить

В работе были описаны, реализованы и проанализированы разные вариации метода имитации отжига применительно к общей задаче о расписании. Как и стоило ожидать лучший результат дает вариант алгоритма, где для перехода к новому расписанию два задания меняются местами, а количество итераций линейно зависит от количества заданий (этого следовало ожидать, так как жадный алгоритм, используемый для получения начального решения старается распределить задания равномерно по процессорам).
В итоге мы получили полиномиальный алгоритм, средняя ошибка которого на наших экспериментальных данных составила всего 1.06601.

Купить