We report the performance of 15 construction heuristics to find initial solutions, and 4 search algorithms to solve a frequency assignment problem where the value of an assigned frequency is determined by the site where it is assigned. The algorithms were tested on 3 sets of problems, the first one corresponds to the well-known Philadelphia problems, and the last two correspond to situations frequently encountered when FM frequencies are assigned in Mexico. Our experimental results show that the construction heuristics that consider the weights of the sites perform well. Among the 4 search algorithms tested, the one based on cross entropy performed better than the others in small problems, whereas in large problems the algorithm based on simulated annealing performed the best. © 2012 Elsevier Ltd. All rights reserved.