# Multi-Satellite Task Parallelism via Priority-Aware Decomposition and Dynamic Resource Mapping
## 4 Methodology
### Task Decomposition Strategy Based on Graph Theory and Lagrangian Relaxation
#### 4.1.5 Task Priority Constraint  
Higher-priority tasks should be executed first:  
\[\text{If }\omega_{ij}>\omega_{ik},\quad t_{ij}\leq t_{ik} \tag{26}\]Due to the NP-hard nature of the ILP problem, a Lagrangian relaxation approach is employed to improve the solution efficiency. The resource and task dependency constraints are relaxed into the objective function using Lagrange multipliers to construct the Lagrangian function:  
\[L(x,t,\lambda,\mu) = \max_{i,j}\bigl{(}t_{ij}+d_{ij}\bigr{)}+\sum_{s\in S}\lambda_{s} \left(\sum_{T_{ij}\in M}R(T_{ij})x_{ijs}-R_{s}\right)+\sum_{(ij,jk)\in E}\mu_{ ij,jk}\bigl{(}t_{ij}-t_{ik}-d_{ik}\bigr{)}\] (27) where \(\lambda_{s}\) represents the Lagrange multipliers for the resource constraints, \(\mu_{ij,ik}\) represents the Lagrange multipliers for the task dependency constraints, and \(E\) represents the set of task dependency relationships.  
This Algorithm 1 decomposes the complex integer linear programming problem into smaller subproblems and employs Lagrange multipliers to coordinate global constraints with local optimization, ensuring scientific validity. It begins by initializing the iteration counter and Lagrange multipliers (Line 1). During each iteration, the algorithm solves a relaxed subproblem for each subtask \(T_{ij}\in M\) (Line 3), minimizing the objective function of task start time, delay penalties, and resource constraint violations weighted by Lagrange multipliers. The solution must satisfy binary constraints, time windows, and other feasibility conditions. By accounting for task dependencies, resource constraints, time windows, and priorities, this approach guarantees feasible and near-optimal task allocation. Next, the Lagrange multipliers are updated to enforce resource and temporal constraints (Line 4). The resource-based multiplier \(\lambda_{s}\) is adjusted based on the difference between the total allocated and available resources for each satellite, while the temporal constraint multiplier \(\mu_{ij,ik}\) is updated based on task precedence relationships, ensuring the overall allocation remains balanced and efficient. A stopping criterion is then evaluated (Line 5): if met, the algorithm terminates; otherwise, it increments the iteration counter and continues. Once convergence is achieved, a feasible solution is constructed (Line 6). The final task assignments and start times (or their averaged values) form the basis of the initial solution, which a repair heuristic (e.g., simulated annealing) refines by mitigating constraint violations and improving efficiency. Finally, the algorithm returns the optimized task assignments and start times \(x_{ijs},t_{ij}\) (Line 7).  
```
Input: Task set \(M\), satellite set \(S\), resource constraints \(R_{s}\) Output: Optimal task assignment \(x_{ijs}\), start time \(t_{ij}\)
1 Initialize:\(k\gets 0\), \(\lambda_{s}^{(k)}\) for each \(s\in S\), \(\mu_{ij,ik}^{(k)}\), \(\forall(ij,ik)\), \(\theta^{(k)}\). whilenot convergeddo
2 Solve the relaxed subproblem for each subtask \(T_{ij}\in M\): \(\min_{x_{ijs},t_{ij}}\bigl{(}t_{ij}+d_{ij}+\lambda_{s}^{(k)}R(T_{ij})\,x_{ijs} +\sum_{(ij,jk)}\mu_{ij,kk}^{(k)}\bigl{(}t_{ij}-t_{ik}-d_{ik}\bigr{)}\bigr{)}\),
3 Update Lagrange multipliers by executing following equations: \(\lambda_{s}^{(k+1)}\ \leftarrow\ \lambda_{s}^{(k)}\ +\ \theta^{(k)}\Bigl{(}\sum_{T_{ij}\in M}R(T_{ij})\,x_{ijs} \ -\ R_{s}\Bigr{)}\), \(\forall\,s\in S\), \(\mu_{ij,ik}^{(k+1)}\ \leftarrow\ \mu_{ij,ik}^{(k)}\ +\ \theta^{(k)}\bigl{(}t_{ij}-t_{ik}-d_{ ik}\bigr{)}\), \(\forall\,(ij,ik)\). \(k\gets k+1\).
4 Construct a feasible solution: \(\tilde{x}_{ijs},\tilde{t}_{ij}=\frac{1}{k}\sum_{k=1}^{K}x_{ijs}^{(k)},\frac{1} {k}\sum_{k=1}^{K}t_{ij}^{(k)}\) \((x_{ijs}^{*},t_{ij}^{*})\leftarrow\mathcal{A}(x_{ijs},t_{ij})\) Return:\(x_{ijs}^{*},t_{ij}^{*}\).
```  
**Algorithm 1**Task Decomposition Using Lagrangian Relaxation (LRCTD)