We address the multi-satellite scheduling problem with limited observation capacities that arises from the need to observe a set of targets on the Earth's surface using imaging resources installed on a set of satellites. We define and analyze the conflict indicators of all available visible time windows of missions, as well as the feasible time intervals of resources. The problem is then formulated as a mixed integer linear programming model, in which constraints are derived from a careful analysis of the interdependency between feasible time intervals that are eligible for observations. We apply the proposed model to several different problem instances that reflect real-world situations. The computational results verify that our approach is effective for obtaining optimum solutions or solutions with a very good quality.
@cite_13 propose a greedy algorithm and a genetic algorithm based on the assumption that there are only one resource and one observation window for every mission. A single-satellite single-orbit scheduling problem is addressed with a tabu search heuristic in , an adaptive meta-heuristic in @cite_8 , and a 0 1 linear programming model in . Another 0 1 model based on preprocessing the observation segments is discussed by @cite_10 . The problem of maximizing the total amount of downloaded data is addressed with a mixed-integer programming model and an iterative algorithm . There are also several publications that treat the single satellite scheduling as a machine scheduling problem with constraints of operating time windows. The problem is then solved by a heuristic . By considering the setup time between two consecutive observations, @cite_2 introduce the selecting and scheduling problem for an agile Earth observation satellite. @cite_9 take the limited time window and transition time constraints into account.
@cite_13 @cite_8 @cite_9 @cite_2 @cite_10
2148027993 2605409691 2082026440 2185236731
This paper describes three approaches to assigning tasks to earth observing satellites EOS. A fast and simple priority dispatch method is described and shown to produce acceptable schedules most of the time. A look ahead algorithm is then introduced that outperforms the dispatcher by about 12 with only a small increase in run time. These algorithms set the stage for the introduction of a genetic algorithm that uses job permutations as the population. The genetic approach presented here is novel in that it uses two additional binary variables, one to allow the dispatcher to occasionally skip a job in the queue and another to allow the dispatcher to occasionally allocate the worst position to the job. These variables are included in the recombination step in a natural way. The resulting schedules improve on the look ahead by as much as 15 at times and 3 on average. We define and use the "window-constrained packing" problem to model the bare bones of the EOS scheduling problem. Abstract Agile satellites belong to the new generation of satellites with three degrees of freedom for acquiring images on the Earth. As a result, they have longer visible time windows for the requested targets. An image shot can be conducted at any time in the window if and only if the time left is sufficient for the fulfillment of the imaging process. For an agile satellite, a different observation time means a different image angle, thus defining a different transition time from its neighboring tasks. Therefore, the setup time for each imaging process depends on the selection of its observation start time, making the problem a time-dependent scheduling problem. To solve it, we develop a metaheuristic, called adaptive large neighborhood search (ALNS), thus creating a conflict-free observational timeline. ALNS is a local search framework in which a number of simple operators compete to modify the current solution. In our ALNS implementation, we define six removal operators and three insertion operators. At each iteration, a pair of operators is selected to destroy the current solution and generate a new solution with a large collection of variables modified. Time slacks are introduced to confine the propagation of the time-dependent constraint of transition time. Computational experiments show that the ALNS metaheuristic performs effectively, fulfilling more tasks with a good robustness. In this paper, we develop models and algorithms for solving the single-satellite, multi-ground station communication scheduling problem, with the objective of maximizing the total amount of data downloaded from space. With the growing number of small satellites gathering large quantities of data in space and seeking to download this data to a capacity-constrained ground station network, effective scheduling is critical to mission success. Our goal in this research is to develop tools that yield high-quality schedules in a timely fashion while accurately modeling on-board satellite energy and data dynamics as well as realistic constraints of the space environment and ground network. We formulate an under-constrained mixed integer program (MIP) to model the problem. We then introduce an iterative algorithm that progressively tightens the constraints of this model to obtain a feasible and thus optimal solution. Computational experiments are conducted on diverse real-world data sets to demonstrate tractability and solution quality. Additional experiments on a broad test bed of contrived problem instances are used to test the boundaries of tractability for applying this approach to other problem domains. Our computational results suggest that our approach is viable for real-world instances, as well as providing a strong foundation for more complex problems with multiple satellites and stochastic conditions. Earth Observation Satellite (EOS) scheduling is an important oversubscribed constraint optimization problem. Permutation-based scheduling methods have recently been shown to be effective on these problems. However, the new agile EOS satellites present additional scheduling complexity because they allow image acquisition over a window of possible observation times. Constraint propagation algorithms have been successfully applied in traditional local search methods for these problems. In this paper, we describe a synthesis of permutation-based search and constraint propagation for agile EOS scheduling. Our approach incorporates the advantages of both techniques. We obtain the large neighbourhood behaviour of permutation search for oversubscribed resource scheduling problems. As well, we exploit the power of constraint propagation to retain as much flexibility as possible while building the schedule. We investigate different local optimization algorithms (including hill-climbing, simulated annealing and squeaky wheel optimization) coupled with constraint propagation over image acquisition time windows. We compare our method to recent permutation-based methods for non-agile EOS scheduling which rely upon a greedy scheduler for assigning image acquisition times. Experiments are performed on synthetic EOS data sets using both uniform random image targets and actual urban image target sets. We measure both schedule quality and solution degradation as new image requests are added dynamically to the problem. Our results suggest that permutation-based search coupled with constraint propagation works very well for agile EOS scheduling.