Source-linked AI summary
A Mixed Integer Linear Programming Model for Multi-Satellite Scheduling
Xiaoyu Chen, Gerhard Reinelt, Guangming Dai, Andreas Spitz
TL;DR
The paper addresses multi-satellite scheduling with limited observation capacities. It develops a MILP using conflict analysis and interdependent feasible intervals, obtaining good feasible solutions quickly while also computing true optima.
Problem
The paper addresses multi-satellite scheduling with limited observation capacities in observing targets using satellite imaging resources.
Method
The approach analyzes conflicts among visible mission windows and interdependencies among feasible resource intervals to derive MILP constraints.
Results
Good feasible solutions are obtained very fast, while computation of true optimum solutions is also possible across several classes of problem instances.
Takeaways & Limitations
The proposed MILP is effective for obtaining optimum solutions or solutions with very good quality.
Takeaways & Limitations
The decomposition approach can become trapped in a local optimum, obstructing a good bound from the LP relaxation.
Abstract
from arXiv · showhide
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.
1. Introduction
The paper addresses multi-satellite scheduling when observation capacity is limited and not all mission demands can be satisfied. It analyzes visible-window conflicts and feasible resource intervals to formulate a MILP evaluated on benchmark instances.
- Observation missions require targets to remain visible throughout a resource-specific duration within a feasible time window.The duration depends on satellite orbiting speed and resource scanning speed, while setup time is needed between consecutive observations.
- Increasing satellites and observation requests make satellite capacity a scarce resource, so all mission demands may not be satisfiable in one observation period.
- The paper analyzes resource capacity, visible mission-window distributions, and conflict indicators for available observation windows.
- It derives constraints from interdependencies among eligible time intervals and formulates the scheduling problem as a mixed integer linear programming model.
- Computational results on benchmark problem instances indicate that the proposed method is effective and efficient.
2. Related Work
Prior work includes heuristics, metaheuristics, graph-based formulations, and mathematical programming for satellite scheduling. Multi-satellite settings create strongly overlapping visibility windows, while decomposition can produce low-quality local optima and heuristic methods lack quality guarantees.
- Mathematical and graph-based approaches include linear programs, weighted acyclic digraphs, generalized knapsack formulations, dynamic programming, and ant colony optimization.
- Multi-satellite scheduling is more challenging because resources and targets can overlap, producing highly overlapping visible time windows and prominent combinatorial structure.
- Decomposing the problem into mission assignment and single-satellite scheduling can become trapped in a low-quality local optimum when missions and visible windows interact.
- Existing studies address satellite scheduling with greedy, tabu-search, genetic, evolutionary, simulated-annealing, and other heuristic or metaheuristic methods.
- Heuristic optimization techniques typically require extensive parameter tuning and cannot provide quality guarantees for obtained solutions.
3. A Mixed Integer Linear Programming Model
The model represents multi-satellite observations through visible and feasible time intervals, mission assignments, resource capabilities, and timing requirements. Its constraints capture observation-window eligibility, setup times, resource feasibility, mission accomplishment, and usage limits, with preprocessing-based inequalities intended to tighten upper bounds.
- Model setting: The formulation models missions as point targets requiring continuous observation by compatible satellite resources and accounts for imaging type, swing angle, rotation angle, and setup time.Each mission has earliest and latest observation times, a requested duration, and a positive importance weight.
- Time-interval representation: Visible time windows specify when a resource can observe a mission, while feasible time intervals are formed by unions of overlapping visible windows.These intervals are represented as disjoint resource-specific intervals that can be assigned to missions.
- Time-interval representation: Swing and rotation angles depend on the resource and observation start time, so consecutive observations require transition time for repositioning and stabilization.The model uses upper bounds for setup times because angle changes are not simultaneous and stabilization requires additional time.
- Decision variables and objectives: Binary assignment and ordering variables, together with continuous mission start times, encode selected visible windows, mission sequencing, and resource usage.The objective can maximize either the number of accomplished missions or their total weight.
- Constraints: The constraints enforce observation-window containment, setup times between consecutive activities, resource feasibility, mission accomplishment, integrality, and maximum resource usage.Feasible subinterval capacities limit how many candidate missions can be assigned when visible windows overlap.
- Improved constraints: The proposed effective inequalities are incorporated from preprocessing and produce a significant improvement in obtaining a tighter upper bound of instances.The formulation also recognizes that large Big-M values can obstruct good bounds from the LP relaxation.
4. Computational Experiments
The experiments evaluate the proposed models on 37 multi-satellite scheduling instances with varied target distributions, resource conflicts, and scheduling horizons. Preprocessing and the improved MILP reduce model complexity and generally produce tighter bounds, more optimal solutions, and smaller optimality gaps than the MILP.
- 4.1. Test Instances: 37 problem instances combine different satellites, target sets, and 24- or 48-hour scheduling horizons.Target sets include randomly distributed, clustered, and manually generated high-conflict missions.
- 4.1. Test Instances: Conflict indicators quantify resource availability and instance complexity through assignment capacity and contention across feasible time intervals.The analysis also distinguishes missions by the number and average duration of their visible time windows.
- 4.1. Test Instances: Higher conflict degrees make the mission-capacity measure decrease quickly relative to N, providing a more exact upper bound.The potential assignment opportunity captures flexibility in assigning resources and observations to missions.
- 4.2. Comparison of Proposed Models: Preprocessing improves each phase of overall performance, especially for randomly distributed target instances, while the improved MILP uses fewer binary variables when candidate windows do not overlap.The standard MILP has approximately quadratic binary-variable growth, whereas the improved formulation introduces binaries only for overlapping candidate visible windows.
- 4.3. Optimization Results: For weighted mission objectives, the improved MILP has a worst gap of 2.95%, compared with 35.97% for the MILP.The reported results also show that good upper bounds can be obtained fairly quickly as runtime progresses.
5. Conclusions
The paper addresses multi-satellite scheduling with limited observation capacities by analyzing mission conflicts and embedding the resulting structure in a MILP. Experiments indicate that the model produces good feasible solutions quickly, can obtain true optima, and supports satellite-resource decision systems.
- The model targets limited observation capacities, a core challenge for effectively using satellite-constellation resources.
- Detailed conflict analysis yields stronger MILP constraints that significantly speed up the solution process.
- A 5-index-variable formulation avoids the standard “Big-M” approach and is more suitable for real-world instances with unnecessary variables and constraints.
- The experiments assess model correctness and effectiveness while maximizing either the total number or total weight of assigned missions.
- Good feasible solutions are obtained very fast, while true optimum solutions are also possible.
- The model provides a basis for decision-support systems that schedule satellite resources with imaging and communication tasks.
Appendix A Generation of the Feasible Time Interval
The appendix constructs feasible time intervals from overlapping visible windows assigned to the same resource. It also characterizes their conflict-degree distributions and illustrates the resulting intervals graphically.
- A free visible-time subinterval that overlaps no other window is assigned directly to its mission during preprocessing.
- Remaining visible windows are retained only when they overlap at least one other window.
- Feasible time intervals are generated by combining overlapping visible windows on the same resource.
- Each resource has several disjoint feasible time intervals, and the distributions of visible windows and feasible intervals are visualized.
- Conflict degree describes the number of overlapping visible windows, with different colors representing different conflict degrees in Figure 7.
Appendix B Calculation of Effective Feasible Time Subinterval
The appendix reduces feasible intervals by identifying directly assignable low-conflict pieces and then generating effective subintervals through targeted time-piece operations. The procedure uses conflict information and observation-duration constraints to reduce the search space.
- The preprocessing step removes the lowest-conflict time-piece when its corresponding mission count does not exceed the resource capacity.
- For equal observation durations, the relevant capacity value can be computed directly; otherwise, missions are assigned iteratively from shortest duration while accounting for setup time.
- The effective feasible time subinterval is generated using the previously calculated capacity value and partial processing.
- Missions corresponding to the removed piece can be assigned directly, reducing the search space.
- Conflict-degree distributions guide the inclusion of effective feasible subintervals and corresponding inequalities.
- Three operations iteratively relocate a time-piece and its visible windows according to earliest start, latest end, and largest internal interval criteria.
Appendix C Instance Analysis
The instance analysis describes resource utilization across problem classes with differing conflict-degree distributions. It defines the main complexity and timing measures used to characterize visible and feasible observation time.
- Table 6 reports instance complexity and the importance of each resource based on utilization across differing instance types.
- The instances vary by conflict degree and distribution, which are used to characterize resource utilization.
- δ denotes a resource’s maximum setup time, while N denotes the total number of available visible time windows.
- T is total visibility time across a resource’s visible windows, whereas F is total time across feasible intervals assignable to missions.
- Because visible windows may overlap, feasible observation time corresponds to the union of those windows rather than their total visible time.
- Table 6 presents the resource-utilization analysis for the listed instances.