International Journal of Computational
Intelligence Research (IJCIR)
Volume 2, Number 2 (2006)
Population-based heuristics for hard permutational optimization problems
Wroclaw University of Technology, Institute of Computer Engineering, Control and Robotics, Janiszewskiego 11–17, 50–372
University of Wroclaw, Institute of Computer Science, Przesmyckiego 20, 51–151
In this paper we present a population-based algorithm for solving permutational optimization problems. It consists in testing the feasible solutions which are the local minima. This method is based on the following observation: if there are the same elements in some positions in several permutations, which are local minima, then one can suppose that these elements can be in the same positions in the optimal solution. The presented properties and ideas can be applied to two classical strongly NP-hard scheduling problems:
1. single machine total weighted tardiness problem
2. flow shop problem with goal function Cmax.
Computational experiments on the benchmark instances from the OR-Library  are presented and compared with the results yielded by the best algorithms discussed in the literature. These results show that the algorithm proposed allows us to obtain the best known results for the benchmarks in a short time.
algorithm, metaheuristics, scheduling, optimization, population, local search.