This research considers a problem of distributed missions assignment in the heterogeneous group of aerial rescue robots, which function without obstacles on plain landscape. A new technique of distributed missions assignment problem solving is proposed, based on the metaheuristic optimization algorithms independent runs, which are launched on robots in a distributed manner. The novelty of the technique is that metaheuristics instances with varying computational complexities are formed and distributed through the heterogeneous robotic group with the usage of efficient algorithms for the block size forming and assignment. Computational complexities of metaheuristics instances are formed with two contradictory criteria: the first one is the minimization of the makespan of the missions assignment problem solving via independent runs, the second one is the metaheuristic instance maximization because of the solution quality degrading in case of small number of algorithm iterations. This improves the makespan of distributed missions assignment problem solving significantly without considerable degrading of the overall missions assignment result. Selected simulation results demonstrate the improvement of overall mission assignment time up to 2 times with the mission assignment solution degrading less than 26% in the worst case and without degrading in the best case.