## 6 Heuristic  
Since the presented optimal strategy is NP hard, in order to evaluate the benefits of the proposed allocation strategy in a complex scenario like a real orbital case, it is necessary to introduce a heuristic mimicking the optimization problem solution. We propose a heuristic leveraging the [PERSON]'s algorithm, as detailed in Algorithm 1. This algorithm applies on a new graph \(\mathcal{G}=(\mathcal{N},\mathcal{E})\), being a modified version of the graph presented in Section 4, where instead of distinguishing nodes dealing with only two processing states, we also consider a third processing state, the \"in-processing\" state. This is due to the fact that the introduction of the \"in-processing\" layer allows us to take into account that a node processing a task can transmit it in the same time cycle, during which processing happens only if the energy remaining after processing is enough to accomplish the transmission of a processed task. In fact, while this condition was verified by means of appropriate constraints in the optimization problem definition, in the case of the proposed shortest-path-based heuristic, we have to input the algorithm with a graph containing only admissible paths. For this reason, we need to update the values assumed by the parameter \(p\) defined in Section 5. While defining the heuristic, we consider \(p\in\{0,1,2\}\), where \(p=0\) represents a node dealing with unprocessed tasks, \(p=1\) a node dealing with in-processing tasks, and \(p=2\) a node handling processed tasks. In particular, while transmission and storage links remain the same as defined in Section 4, processing links are distinguished as follows:  
* If \(i_{s}=i_{d}=i\), \(p_{s}=0\), \(p_{1}=1\), the edge represents the service processing accomplished by the \(i\)-th physical node during the \(t\)-th time cycle (i.e., a processing link), with associated capacity and energy cost as discussed in the processing link definition given in Section 4;
* If \(i_{s}=i_{d}=i\), \(p_{s}=1\), \(p_{1}=2\), the edge represents a fictitious link to bridge nodes in the processing state to nodes in the processed state, associated with an infinite capacity and no energy cost. ```
Input:\(\Sigma,\mathcal{N},\mathcal{E},\beta\)
1 Initialize: \(\Lambda_{[i_{s},p_{s}],[i_{s},p_{s}]}\gets 0,\Psi_{i_{s}}^{\dagger}\gets 0, \forall i_{s},i_{d}\in[0,\ldots,N_{S}-1],\ p_{s},p_{d}\in[0,2],\ t\in[0,\ldots,T-1]\);
2 Initialize: \(\Pi\leftarrow\mathcal{O}\);
3 for\({}^{h}\in\Sigma\)do
4\(\mathcal{N},\mathcal{E}\leftarrow Extract\ Subgraph({}^{h},\Lambda_{l},\mathcal{N}, \mathcal{E},\beta)\);
5\(\mathcal{G}\leftarrow(\mathcal{N},\mathcal{E})\);
6\(\mathcal{\Pi}\gets Dijkstra\left(\delta,n_{l}^{h},n_{l_{S}-1}^{(h+\ell)} \right)\);
7 if\(\Pi\
eq\emptyset\)then
8\(\Pi\leftarrow\Pi\cup\Pi\)
9 for\(\{i_{s},p_{s},i_{d},p_{s}\}\in\Pi\)do
10 Calculate \(\Lambda_{[i_{s},p_{s}],[i_{s},p_{d}]}^{\dagger}\) by means of Equation (25);
11 Calculate \(\Psi_{i_{s}}^{\dagger}\) by means of Equation (26);
12
13 end for
14 for\(t\in[f_{t}^{h},\ldots,f_{t}^{h}+f_{t}^{h}]\)do
15\(\beta_{t}^{\top}\gets\beta_{t}^{\top}-\{f^{h}\}\);
16
17 end for
18
19 else
20\(\Omega\leftarrow\Omega\cup\{f^{h}\}\);
21
22 end if
23
24 end for
25
26 end for
```  
**Algorithm 1**Ground Station Energy-Saving Heuristic (GSESH)  
Let us detail the main steps of the Ground Station Energy-Saving Heuristic (GSESH) presented in Algorithm 1. After having initialized the matrices tracking the link occupancy and node energy usage in time (Line 1), we apply the following steps for each service to be allocated. We first extract a subgraph containing only nodes related to time cycles between the service generation and delivery deadline cycles and only edges with enough capacity to host the unprocessed service and related to nodes with enough energy to accomplish its transmission and/or processing (Line 3). Subgraph extraction is obtained by applying Algorithm 2, which will be discussed in detail further on.