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.
In comparison to the single satellite scheduling problem, the use of multiple satellites gives more flexibility and is thus more challenging . @cite_6 @cite_11 @cite_4 use graph representations to formulate the problem, for which dynamic programming and ant colony optimization algorithms are proposed to produce a near-optimal solution. To this end, simple sequential missions with conflicts can easily be represented as graphs. However, if the problem involves multiple satellites, the visibility fields of different resources may overlap. Furthermore, several targets may be in the field of view of the same resource simultaneously, and a target may be observed by more than one resource at the same time. Thus, the visible time windows are highly overlapping during the scheduling period, making the combinational characteristic of the problem more prominent. This ultimately renders the uniform modelling of the problem difficult .
@cite_4 @cite_6 @cite_11
2186460581 2087326379 2082026440
The development of appropriate project management techniques for Research and Development (R&D) projects has received significant academic and practical attention over the past few decades. Project managers typically face the problem of allocating resources and scheduling activities, for which the underlying combinatorial problem is NP-hard. The inherent uncertainty in many R&D environments increases the complexity of the problem. Satellite observation scheduling plays a significant role in improving the efficiency of satellite observation systems. Although extensive scheduling algorithms have been proposed for the satellite observation scheduling problem (SOSP), the task clustering strategy has not been taken into account up to now. This paper presents a novel two-phase based scheduling method with the consideration of task clustering for solving SOSP. This method comprises two phases: a task clustering phase and a task scheduling phase. In the task clustering phase, we construct a task clustering graph model and use an improved minimum clique partition algorithm to obtain cluster-tasks. In the task scheduling phase, based on overall tasks and obtained cluster-tasks, we construct an acyclic directed graph model and utilize a hybrid ant colony optimization coming with a mechanism of local search, called ACO-LS, to produce optimal or near optimal schedules. Extensive experimental simulations demonstrate the efficiency of the proposed scheduling method. 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.