# Multi-Satellite Task Parallelism via Priority-Aware Decomposition and Dynamic Resource Mapping
## 4 Methodology
### Task Decomposition Strategy Based on Graph Theory and Lagrangian Relaxation  
To address the challenges of efficient task decomposition considering complex task dependencies, we model the remote sensing tasks as a DAG and apply integer linear programming (ILP) combined with Lagrangian relaxation to minimize the total execution time while satisfying task dependencies and resource constraints.  
Task dependencies play a critical role in determining the execution order and time of tasks in a multi-satellite system. In our approach, tasks are modeled as a DAG, where each node represents a subtask \(T_{ij}\) and directed edges represent the dependency relationships between subtasks. A key aspect of this model is the handling of dependencies that may impose constraints on the execution order of subtasks.  
For instance, if subtask \(T_{ij}\) depends on the results of subtask \(T_{ik}\), then \(T_{ij}\) cannot start until \(T_{ik}\) is completed, along with an additional delay \(\Delta t_{ik}\) to account for data transfer or synchronization. This relationship can be formally expressed as Equation (7).  
However, in cases where there is no strict dependency, subtasks can be executed concurrently, which can reduce the overall execution time. Therefore, adjusting the execution sequence of tasks based on their dependencies is crucial for optimizing the total execution time. By carefully selecting which task should be executed first and considering the delays introduced by dependencies, the overall system efficiency can be maximized.  
For example, if task \(T_{ij}\) is dependent on \(T_{ik}\), but there is no significant data transfer between the two, the system might allow \(T_{ij}\) to start earlier, assuming other resources  
Figure 1: Schematic of main idea of HADRM method.  
are available. This adjustment is particularly important in a distributed multi-satellite environment, where communication and processing delays can be significant.  
This approach ensures that the task execution respects both the dependency relationships and the intrinsic resource requirements of each subtask, optimizing the overall scheduling of tasks.  
The task decomposition problem in multi-satellite cooperative computing is modeled as a DAG, where each node represents a subtask \(T_{ij}\) and edges represent dependency relationships between subtasks. Each subtask \(T_{ij}\) has an completion time \(t_{ij}\) and resource requirements \(R(T_{ij})\). The task dependencies and priorities can be expressed as  
\[\text{If }T_{ij}\text{ depends on }T_{ik},\quad t_{ij}\geq t_{ik}+\delta_{ik}, \tag{20}\]  
where \(\delta_{ik}\) is the minimum time interval between tasks.  
Based on the DAG model, an ILP model is established to minimize the total execution time. The decision variables are defined as follows:  
\(x_{ij}\) is a binary variable, where \(x_{ij}=1\) if subtask \(T_{ij}\) is assigned to satellite \(s\), and 0 otherwise. \(t_{ij}\) represents the start time of subtask \(T_{ij}\).  
We obtain the following objective function:  
\[\text{min}\max_{ij}\bigl{(}t_{ij}+d_{ij}\bigr{)}, \tag{21}\]  
where \(d_{ij}\) is the duration of subtask \(T_{ij}\).  
The optimization problem includes the following constraints (22)-(26):