Abstract:

This paper researches the scheduling problem of earth observation satellites formation. It builds two integer programming models, one is based on the natural description of the original problem and the other is based on a directed-graph formulation. Based on the convex polytope theory of integer programming, this paper compares the respective optimal-solution-value gaps between the two models and their respective linear relaxations, and makes the conclusion that the linear relaxation of the directed graph formulation is closer to the convex polytope of the original problem. Besides, this paper designs an incomplete branch and bound algorithm based on the directed-graph formulation and implements the algorithm through ILOG CPLEX on randomly generated problem instances. Computation results show the effectiveness of the model and the algorithm, and validate the theoretical gaps-analysis of the two integer programming models.