# Multi-Satellite Task Parallelism via Priority-Aware Decomposition and Dynamic Resource Mapping
## 3 Problem Description and Formulation
### Objective Function  
The objective is to minimize the total execution time of tasks. The objective function is  
\[\min\sum_{m=1}^{M}\sum_{t=1}^{T}\Bigl{(}\varphi_{m}^{p}(t)+\varphi_{m}^{b}(t) \Bigr{)}. \tag{18}\]  
For multi-objective optimization, a weighted method is used and we obtain the final objective function as Equation (19):  
\[\min F=\alpha\sum_{m=1}^{M}\varphi_{m}^{p}(t)+\beta\sum_{m=1}^{M}\varphi_{m}^{b }(t),\]  
s.t.  
\[\text{C1: }t_{ij}\geq t_{ik},\quad\text{if }T_{ij}\text{ depends on }T_{ik},\] \[\text{C2: }\omega_{ij}\geq\omega_{ik},\quad\text{if }\omega_{ij}> \omega_{ik}, \tag{19}\] \[\text{C3: }t_{ij}^{Start}\leq t_{ij}\leq t_{ij}^{End},\] \[\text{C4: }\sum r^{p}(T_{ij})\leq R_{s}^{p},\quad\sum r^{b}(T_{ij} )\leq R_{s}^{b},\quad\sum c(T_{ij})\leq C_{s},\] \[\text{C5: }\frac{\sum r^{b}(s_{i})}{R_{s}^{b}}\approx\frac{\sum r ^{b}(s_{j})}{R_{s}^{b}},\quad\forall s_{i},s_{j}\in S.\]  
The objective function aims to minimize the total execution time of observation and compression tasks while ensuring efficient resource utilization and system stability. The function considers both the observation processing time \(\varphi_{ij}^{p}\) and compression processing time \(\varphi_{ij}^{b}\), with weighting factors \(\alpha\) and \(\beta\) to balance their contributions, where \(\alpha\) and \(\beta\) are weight coefficients for different task phases. The execution time of each task is constrained by resource availability, time windows, and task dependencies. Let \(t_{ij}\) be the execution time of an observation task, with feasible execution times defined in the set \(T_{ij}\). The deviation from the target execution time is denoted as \(d_{i,\text{tar}}(t_{ij})\), while resource allocations for compression tasks are represented by \(r^{p}(T_{ij})\) and are constrained by the maximum allowed resource capacity \(R_{s}^{p}\). Power consumption during execution is modeled by \(r^{b}(T_{ij})\) and \(c(T_{ij})\). Additional constraints include distance or deviation limits \(t_{ij}^{Start}\leq t_{ij}\leq t_{ij}^{End}\), as well as capacity constraints for computation and transmission, given by \(\sum r^{p}(T_{ij})\leq R_{s}^{p}\). Task scheduling follows dependency constraints, ensuring that a compression task \(t_{ij}\) does not start before the observation task \(t_{ik}\), with dependencies represented by \(\omega_{ij}\geq\omega_{ik}\). Furthermore, load balancing is maintained by ensuring that resource utilization across all satellites satisfies \(\frac{\sum r^{b}(s_{i})}{R_{s}^{b}}\approx\frac{\sum r^{b}(s_{j})}{R_{s}^{b}}, \quad\forall s_{i},s_{j}\in S\).  
The analysis shows that this problem is NP-hard. As the number of tasks M and satellite nodes N increases, the combinatorial complexity of task allocation and resource mapping grows exponentially. Polynomial-time algorithms cannot effectively solve this problem.  
Through reduction from the classical task scheduling problem, the complexity of the problem is proven, classifying it as NP-hard. The task dependencies, resource allocation, and time constraints make the problem highly challenging, requiring heuristic or approximation algorithms to solve it.