El problema de asignación (o problema de emparejamiento) en gráficos bipartitos es un problema NP-duro para . En este documento presentamos cinco nuevas heurísticas. Dos algoritmos, y , surgen como mejoras naturales del Algoritmo de (He et al., en: Algoritmos de Grafos y Aplicaciones 2, World Scientific, 2004). Los otros tres algoritmos, , , y , incorporan aleatoriedad. El Algoritmo puede considerarse como una versión codiciosa de , mientras que y son versiones del algoritmo de búsqueda local, especializado para el problema de emparejamiento. Los algoritmos están implementados en Python y se ejecutan en tres conjuntos de datos. En los conjuntos de datos disponibles, todos los algoritmos superan claramente al Algoritmo en términos de calidad de solución. En el primer conjunto de datos con valores óptimos conocidos, el error relativo promedio oscila entre 1.47% sobre el óptimo (algoritmo ) y 0.08% sobre el óptimo (algoritmo ). En el segundo conjunto de datos con valores óptimos conocidos, el error relativo promedio oscila entre 4.41% sobre el óptimo (algoritmo ) y 0.45% sobre el óptimo (algoritmo ). Una mejor calidad de soluciones exige tiempos de computación más largos, por lo tanto, los nuevos algoritmos proporcionan un buen compromiso entre calidad de soluciones y tiempo de computación.