|
Архив публикацийТезисыXV-ая конференцияМетод локального поиска для задачи о расписании с ограничением предшествованияСанкт-Петербургский государственный университет, Россия, 198504, Санкт-Петербург, Петергоф, Университетский проспект, д. 28 1 стр.Задачи составления расписаний являются популярным объектом исследований и имеют многочисленные и разнообразные приложения. Например, построение расписаний для распределения работ в организации, планирование производственного процесса, распределение ресурсов и другие. Задачи составления расписаний в основном являются NP-трудными, для их решения широко применяются приближенные алгоритмы. Одним из таких алгоритмов является метод локального поиска. Целью метода является нахождение допустимого решения с локально-оптимальным значением целевой функции. Качество получаемого локального оптимума зависит от начального решения, методов определения окрестности и методов поиска в окрестности. Мы рассматриваем задачу составления расписания, которая выглядит следующим образом: задан проект, состоящий из множества ресурсов и множества заданий фиксированной длительности. Задания связаны между собой отношением предшествования. Каждое задание использует один из ресурсов, и должно выполняться без прерывания. Требуется составить такое расписание, чтобы общее время выполнения проекта было минимальным. Мы разработали метод локального поиска для данной задачи, рассмотрели различные способы построения начального расписания, а также два варианта поиска в окрестности – полный, когда выбирается наилучшее решение из всей окрестности, и эвристический способ, когда выбирается решение, дающее первое улучшение целевой функции, причем последний способ показал наилучшие результаты. Численные эксперименты проводились для задач средней размерности (число заданий от 50 до 100). Результаты сравнивались с данными, полученными с помощью метода ветвей и границ, а также с нижней оценкой целевой функции. Результаты экспериментов показали, что для 10% задач были найдены лучшие решения за меньшее время. |
