Medium-term production planning of shots for a low earth orbit satellite based on independent sets

This paper deals with the combinatorial problem of medium-term production planning of shots for a low earth orbit satellite. New model and algorithms based on graph theory are proposed, they are mainly based on the notions of stable sets and partition into cliques. They aim at evaluating the maximum feasible number of images asked for, at elaborating feasible shot plans and at identifying subgroups of images that cannot be wholly taken. Numerical experiments confirm the efficiency of the proposed approach.