Институт вычислительной математики и математической геофизики СОРАН

Тезисы докладов

В работе рассматривается NP--трудная задача теории расписания Pm||Cmax. Исследуется сложность нахождения локального оптимума для окрестностей Swap и объединение Swap и Flip.

В задаче Pm||Cmax задано n работ и m идентичных параллельных машин. Для каждой работы определена длительность ее выполнения. Требуется распределить работы по машинам так, чтобы минимизировать время завершения всех работ.

Для данной задачи исследуется сложность нахождения локального минимума: для заданной окрестности и произвольного входа найти локально оптимальное решение. П. Брукер в [1, 2] показал, что для окрестности Flip стандартный алгоритм локального спуска имеет трудоемкость O(n^2). Окрестностью Flip заданного решения называют множество решений, получаемых переносом одной работы на другую машину. В данной работе рассматривались более широкие окрестности Swap и объединение Swap и Flip. Окрестностью Swap называют множество решений, полученных из данного перестановкой двух работ, расположенных на разных машинах. Объединение Swap и Flip является объединением этих окрестностей. Вопрос о трудоемкости алгоритма локального спуска с данными окрестностями до сих пор оставался открытым.

В данной работе доказано, что с каждой из перечисленных окрестностей стандартный алгоритм локального спуска достигает локальный минимум с любой стартовой точки за полиномиальное число шагов, а именно:

для задачи P2||Cmax с обеими окрестностями Swap и объединение Swap и Flip алгоритму локального спуска требуется O(n^3) шагов;

для задачи Pm||Cmax с обеими окрестностями Swap и объединение Swap и Flip алгоритму локального спуска требуется O(m^2n^4) шагов.

В дальнейшем интересно исследовать аналогичный вопрос для окрестности Push, которая строится на основе идеи Лина-Кернигана [3].

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии Обратная связь

[Головная страница] [Конференции]

© 2006, Институт Вычислительной Математики и Математической Геофизики СО РАН, Новосибирск
© 2006, Сибирское отделение Российской академии наук, Новосибирск
    Дата последней модификации: 06-Jul-2012 (11:52:51)