A Constrained non-dominated sorting genetic algorithm of sequential tasks planning for Multi-EOS

Multi-EOS (Earth Observing Satellites) tasks planning problem is a typical over-subscribed resource allocation problem with multi-objective, especially to make schedule for both LEO (Low Earth Orbit) and HEO (High Earth Orbit) satellites. The optimization work of scheduling is assigning appropriate time window to every request (including data transmission process between satellites and ground facilities) under physical and task precedence constraints. In this paper, we construct a mixed integer programming model for this problem. Then we proposed a multi-objective constrained non-dominated sorting genetic algorithm based on the strategy of elitist selection, in this algorithm, a fast non-dominated sorting approach with computational complexity of O(MN²) is used, to be able to keep a better spread of solutions and better convergence near the true Pareto-optimal front, crowd-distance comparison operator is used and get a better result compare to strength Pareto evolutionary algorithm, constraints control are also used to guarantee the feasibility of solutions. The approach is tested upon three applications derived from satellites data base of AGI´s satellite toolkit.