The cell formation problem is a crucial component of a cell production design in a manufacturing system. This problem consists of a set of product parts to be manufactured in a group of machines. The objective is to build manufacturing clusters by associating part families with machine cells, with the aim of minimizing the inter-cellular movements of parts by grouping efficacy measures. We present two approaches to solve the cell formation problem. First, we present an evolutionary algorithm that improves the efficiency of the standard genetic algorithm by considering cooperation with a local search around some of the solutions it visits. Second, we present an approach based on simulated annealing that uses the same representation scheme of a feasible solution. To evaluate the performance of both algorithms, we used a known set of CFP instances. We compared the results of both algorithms with the results of five other algorithms from the literature. In eight out of 36 instances we considered, the evolutionary method outperformed the previous results of other evolutionary algorithms, and in 26 instances it found the same best solutions. On the other hand, simulated annealing not only found the best previously known solutions, but it also found better solutions than existing ones for various problems. (C) 2010 Elsevier Ltd. All rights reserved.