International Journal of Computational Intelligence Research (IJCIR)

Volume 2, Number 2 (2006)


Population-based heuristics for hard permutational optimization problems

Bozejko Wojciech
Wroclaw University of Technology, Institute of Computer Engineering, Control and Robotics, Janiszewskiego 1117, 50372 Wroclaw, Poland.

Wodecki Mieczyslaw
University of Wroclaw, Institute of Computer Science, Przesmyckiego 20, 51151 Wroclaw, Poland


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 [3] 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.

Key words
algorithm, metaheuristics, scheduling, optimization, population, local search.