Search

The car sequencing problem involves scheduling cars along an assembly line while satisfying as many assembly line requirements as possible. The car sequencing problem is NP-hard and is applied in industry as shown by the 2005 ROADEF Challenge. In this paper, we introduce three new crossover operators for solving this problem efficiently using a genetic algorithm. A computational experiment compares these three operators on standard car sequencing benchmark problems. The best operator is then compared with state of the art approach for this problem. The results show that the proposed operator consistently produces competitive solutions for most instances. [ABSTRACT FROM AUTHOR]

We present a shared memory approach to the parallelization of the Ant Colony Optimization (ACO) metaheuristic and a performance comparison with an existing message passing implementation. Our aim is to show that the shared memory approach is a competitive strategy for the parallelization of ACO algorithms. The sequential ACO algorithm on which are based both parallelization schemes is first described, followed by the parallelization strategies themselves. Through experiments, we compare speedup and efficiency measures on four TSP problems varying from 318 to 657 cities. We then discuss factors that explain the difference in performance of the two approaches. Further experiments are presented to show the performance of the shared memory implementation when varying numbers of ants are distributed among the available processors. In this last set of experiments, the solution quality obtained is taken into account when analyzing speedup and efficiency measures. [ABSTRACT FROM AUTHOR]