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

Ключевые слова: имитация отжига, параллельный алгоритм, оптимизация, вычислительная система, оптимизация ресурсов, параллельные вычисления, распределение ресурсов, метаэвристика, методы распараллеливания, планирование вычислений

Контактная информация: Клименко Анна Борисовна, 347935, Россия, Ростовская область, г. Таганрог, ул. 8 Переулок, 15.

Библиография:
MсGee A. A. and Markarian M. D. Optimum Allocation of Research (Engineering Manpower within a Multi-Project Organizational Structures). IRE Trans. Engng. Manag., v. 9, No. 3, 1962.
Levy F. E., Thompson G., Wiest J. Multiship, Multishop, Workloadsmoothing Program, Naval Research, Logistics Quarterly, v. 9, No. 1, 1962.
Fey С.F. Least Cost Estimating and Scheduling with Limited Resources. Abstract. Recent Advances Math. Programm, 1963.
Барский А.Б. Параллельные процессы в вычислительных системах: планирование и организация. – М.: Радио и связь, 1990.
F. Busetti, Simulated annealing overview. 2003. (http://citeseer.uark.edu:8080/citeseerx/viewdoc/summary;jsessionid=9F958F3AD8ACB341A84315A737883592?doi=10.1.1.66.5018)
L.Ingber, Simulated annealing: practice versus theory.1993. (http://citeseer.uark.edu:8080/citeseerx/viewdoc/summary?doi=10.1.1.15.1046)
Crainic T.G., Toulouse M. Parallel Metaheuristics. In T. G. Crainic and G. Laporte, editors, Fleet Management and Logistics, pages 205-25 1, 1998. Kluwer Academic Publishers.

References (transliteration):
MsGee A. A. and Markarian M. D. Optimum Allocation of Research (Engineering Manpower within a Multi-Project Organizational Structures). IRE Trans. Engng. Manag., v. 9, No. 3, 1962.
Levy F. E., Thompson G., Wiest J. Multiship, Multishop, Workloadsmoothing Program, Naval Research, Logistics Quarterly, v. 9, No. 1, 1962.
Fey S.F. Least Cost Estimating and Scheduling with Limited Resources. Abstract. Recent Advances Math. Programm, 1963.
Barskiy A.B. Parallel'nye protsessy v vychislitel'nykh sistemakh: planirovanie i organizatsiya. – M.: Radio i svyaz', 1990.
F. Busetti, Simulated annealing overview. 2003. (http://citeseer.uark.edu:8080/citeseerx/viewdoc/summary;jsessionid=9F958F3AD8ACB341A84315A737883592?doi=10.1.1.66.5018)
L.Ingber, Simulated annealing: practice versus theory.1993. (http://citeseer.uark.edu:8080/citeseerx/viewdoc/summary?doi=10.1.1.15.1046)
Crainic T.G., Toulouse M. Parallel Metaheuristics. In T. G. Crainic and G. Laporte, editors, Fleet Management and Logistics, pages 205-25 1, 1998. Kluwer Academic Publishers.