Abordar un problema de planificación de misiones multi-robot con conciencia de colisiones, que involucra la asignación de tareas y la búsqueda de rutas, presenta una dificultad significativa debido a la necesidad de eficiencia computacional en tiempo real, escalabilidad y la capacidad de gestionar tanto obstáculos y tareas estáticas como dinámicas dentro de un entorno complejo. Este documento introduce un algoritmo paralelo en tiempo real destinado a superar estos desafíos. El algoritmo propuesto emplea un mecanismo de particionamiento basado en aproximaciones para dividir el conjunto total de tareas no asignadas en varios subconjuntos. Este enfoque descompone el problema original en una serie de problemas de planificación de misiones de un solo robot. Para validar la efectividad del método propuesto, se realizan experimentos numéricos y de hardware, involucrando obstáculos y tareas dinámicas. Además, se proporcionan comparaciones en términos de optimalidad y escalabilidad frente a un método existente, mostrando su rendimiento superior en ambas métricas. Además, se realiza un análisis de la carga computacional para demostrar la consistencia de nuestro método con las observaciones derivadas de estas comparaciones. Finalmente, se demuestra la brecha de optimalidad entre el método propuesto y los óptimos globales en problemas de pequeño tamaño.