Про розв'язання квадратичної задачі про призначення

Abstract

Запропоновано дві модифікації повторюваного ітерованого алгоритму табу розв’язання квадратичної задачі про призначення (з технологією виділення ядра і без неї). Проведено дослідження цих модифікацій порівняно з кращими сучасними алгоритмами розв’язання цієї задачі. Показано ефективність розроблених алгоритмів, зокрема, для задач великої розмірності, для яких з їхньою допомогою знайдено нові рекорди.

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

This paper focuses on the development and improvement of the iterated repeated tabu algorithms for solving the quadratic assignment problem using core allocation technology. The comparative analysis of the empirical computational performance is presented, comparing the modern algorithms from the literature and the algorithms proposed in this paper. The results confirm the efficiency of the modified algorithms in terms of the solution quality and time especially for large-scale problems.