ROBUST TABOO SEARCH FOR THE QUADRATIC ASSIGNMENT PROBLEM

An adaptation of taboo search to the quadratic assignment problem is discussed in this paper. This adaptation is efficient and robust, requiring less complexity and fewer parameters than earlier adaptations. In order to improve the speed of our taboo search, two parallelization methods are proposed and their efficiencies shown for a number of processors proportional to the size of the problem. The best published solutions to many of the biggest problems have been improved and every previously best solution (probably optimal) of smaller problems has been found. In addition, an easy way of generating random problems is proposed and good solutions of these problems, whose sizes are between 5 and 100, are given.