# Multi-Satellite Task Parallelism via Priority-Aware Decomposition and Dynamic Resource Mapping
## 3 Problem Description and Formulation
### Problem Definition  
The goal of task decomposition is to find an optimal decomposition strategy that minimizes the total execution time of the tasks while satisfying the task dependencies and time window constraints. The total execution time of a task \(m_{i}\), denoted as \(\varphi_{m}(t)\), is the sum of the completion times of all its subtasks. For each subtask \(T_{ij}\), its completion time \(\varphi_{ij}(t)\) is given by the following formula:  
\[\varphi_{ij}(t)=\max(\varphi_{ik}(t)+\Delta t_{ik},\varphi_{ij}^{\text{sub}}), \tag{5}\]  
where \(\varphi_{ik}(t)\) represents the completion time of a dependent subtask \(T_{ik}\), and \(\Delta t_{ik}\) is the time delay between the completion of subtask \(T_{ik}\) and the start of subtask \(T_{ij}\) due to their dependency. The term \(\varphi_{ij}^{\text{sub}}\) represents the subtask completion time, which is determined by the resources required for the subtask. Specifically, it is the time needed to execute subtask \(T_{ij}\) independently, considering the computational, communication, and payload resources required. This can be formally expressed as  
\[\varphi_{m}(t)=\sum_{j=1}^{k}\varphi_{ij}(t), \tag{6}\]  
where \(\varphi_{ij}(t)\) represents the completion time of subtask \(T_{ij}\). The completion time of each subtask depends on Remark 1. **Remark 1** (Task Dependencies and completion time). : _When a subtask \(T_{ij}\) depends on the result of another subtask \(T_{ik}\), its completion time must be after the completion of the dependent task. The completion time of a dependent subtask is determined by both the completion time of the preceding subtask and the delay introduced by the dependency. Specifically, subtask \(T_{ij}\) can only begin after \(T_{ik}\) has completed, with an additional delay \(\Delta t_{ik}\) that reflects the time required for data transfer, communication, or synchronization between the tasks. This relationship can be mathematically expressed as_  
\[t_{ij}\geq t_{ik}+\varphi_{ik}(t)+\Delta t_{ik},\quad\text{if subtask }T_{ij}\text{ depends on }T_{ik}, \tag{7}\]  
_And the completion time of subtask \(T_{ij}\) must be after the completion time of subtask \(T_{ik}\), where \(t_{ij}\) is the start time of subtask \(T_{ij}\), \(t_{ik}\) is the completion time of subtask \(T_{ik}\), and \(\varphi_{ik}(t)\) is the completion time of subtask \(T_{ik}\). The additional delay \(\Delta t_{ik}\) accounts for the necessary synchronization and data handling before \(T_{ij}\) can begin._  
_In scenarios where there is no dependency, the completion time of subtask \(T_{ij}\) is independent of other tasks. The completion time \(\varphi_{ij}^{sub}\) of a subtask \(T_{ij}\) is determined solely by the resources required for its execution, including computational, communication, and payload resources. This is expressed as_  
\[\varphi_{ij}^{sub}=\frac{r^{p}(T_{ij})}{R_{s}^{p}}+\frac{r^{b}(T_{ij})}{R_{s }^{b}}+\frac{c(T_{ij})}{C_{s}}, \tag{8}\]  
_where \(r^{p}(T_{ij})\), \(r^{b}(T_{ij})\), and \(c(T_{ij})\) are the resource requirements for payload, computation, and communication, respectively, and \(R_{s}^{p}\), \(R_{s}^{b}\), and \(C_{s}\) are the available capacities of the satellite._  
_In task scheduling, we take the maximum of the two values--the earliest possible completion time determined by task dependencies and the independent completion time of the subtask itself. Therefore, the completion time of subtask \(T_{ij}\) is given by Equation (5)._  
_This ensures that the task execution respects both the dependencies between tasks and the intrinsic resource requirements of each subtask, optimizing the overall scheduling of tasks._  
The objective is to find the optimal task decomposition strategy that minimizes the total task execution time. The total cost function can be expressed as the sum of the execution times of the observation and data processing tasks:  
\[\mu_{m}(t)=\varphi_{m}(t). \tag{9}\]  
The total execution time is further decomposed into observation and compression tasks in Equations (10)-(12).