El objetivo de este trabajo es poner a prueba distintos enfoques de paralelización (sincrónico, cooperativo, centralizado, etc.) para las metaheurísticas empleadas, en los algoritmos de resolución del problema de las p-medianas. Un análisis posterior arrojó: limitaciones en la cantidad de procesadores utilizados debido a la tecnología de red, ventajas en el uso de multiprocesadores y la penalización en el rendimiento al emplear estrategias intensivas en comunicación. Además, en la optimización mediante heurísticas siempre está implícito un balance entre la velocidad en la obtención de una solución y la calidad de ésta, por lo que se sugiere el uso de estrategias híbridas, que aprovechan lo mejor de cada una de ellas.The aim of this paper is to analyze the results of the implementation of several parallelization techniques for the metaheuristics applied to the p-median problem. Further analysis showed: constraints on the number of processors used because of the network technology, advantages in the use of multiprocessors and the penalty in performance when using intensive communications strategies. Moreover, within the optimization using heuristics there is always an implicit balance between speed in obtaining a solution and the quality of it, which suggests the use of hybrid strategies that exploit the best of each.