Решение задачи оптимизации ресурсов и планирования вычислений с использованием параллельной имитации отжига

DOI:

Дата направления статьи в редакцию:

Дата публикации:

Аннотация: Для решения задачи оптимизации используемых ресурсов и планирования вычислений в настоящее время успешно используются различные метаэвристики, в частности, метод имитации отжига. Имитация отжига - метод последовательный, что затрудняет его распараллеливание, однако, в последнее время были разработаны различные способы распараллеливания с целью улучшения качества получаемых решений и времени работы алгоритма. Предметом исследования являются методы распараллеливания имитации отжига, в частности, метод независимых запусков с синхронизацией и асинхронный. В качестве примера реализации имитации отжига выбран метод с температурной схемой "тушения", как ниболее быстрый. Проведен аналитический обзор методов распараллеливания имитации отжига с выделением наиболее перспективных, для которых проведена серия вычислительных экспериментов с использованием. Научная новизна заключается в обнаружении новых зависимостей и тенденций, ранее не описанных в подобных исследованиях: для параллельной имитации отжига с синхронизацией поднят вопрос существования зависимости качества получаемого решения не только от количества вычисляющих устройств, но и от частоты обмена решениями. Для параллельнойй асинхронной имитации отжига прослеживается тенденция улучшения решений с увеличением количества вычисляющих устройств, тогда как для синхронной имитации отжига нельзя вести речь об однозначном улучшении и зависимости только от числа вычисляющих устройств.

Ключевые слова: