Aiming at the issue of cooperating multiple air vehicles mission planning, an improved genetic algorithm is put forward. According to the task types, adopt matrix encoding and heuristic rule to ensure the task sequence of every air vehicle. The simulated anneal algorithm is used for local optimization. The testing result shows that the algorithm can effectively resolve the problem of cooperating multi air vehicle.