## 4 Generation of Solutions for Nominal CPS
```
Input: \(J\), \(R\), \(\Pi\), \(C_{rt}\), \(G\)\(j_{r}\), \(G\)\(j_{r}^{k},k\in\Omega_{r}^{j}=\{1,2,\ldots,k_{r}^{j}\}\), \(Q_{j}\), \(r\in R\ \forall t\in\{1,2,\ldots,\Pi\}\) Output: Feasibility_Indicator, \(f\) Step 0: \(f\gets 0\)\(\overline{C}_{rt}\gets C_{rt}\) Step 1: \(\boldsymbol{J}_{1}\leftarrow\boldsymbol{J}\) While \(\boldsymbol{J}_{1}\
eq\Phi\) Select \(j\in\boldsymbol{J}_{1}\) Construct \(STN_{j}(V_{j},A_{j})\) Find a solution \(f_{j}\) for the Spatial-Temporal Network \(STN_{j}(V_{j},A_{j})\) based on \(\overline{C}_{rt}\forall r\in R\ \forall t\in\{1,2,\ldots,\Pi\}\) Update \(\overline{C}_{rt}=\overline{C}_{rt}-\sum\limits_{a=(u,w)\in A_{jrt}}f_{j}(u,w )\forall r\in R\ \forall t\in\{1,2,\ldots,\Pi\}\)\(\boldsymbol{J}_{1}\leftarrow\boldsymbol{J}_{1}\backslash\{j\}\)\(f\gets f+f_{j}\) End While Step 2: If the solution \(f\) satisfies the condition of Property 1 Set \(Feasibility\_Indicator\) = true Else Set \(Feasibility\_Indicator\) = false End If
```  
**Algorithm 2**Check Feasibility of Nominal CPS  
The above optimization problem is an integer programming problem that can be solved by applying any integer programming solvers such as the CPLEX Optimizer [38]. We will analyze the complexity of Algorithm 2 later in this section. The following property states that a property can be used to check whether the order deadline \(\theta\) can be met. **Property 2. **_If the Feasibility_Indicator is \"true\" by applying the Algorithm to Check Feasibility of \(G=G\|\mathcal{G}\) with respect to \(m\), \(G=G\|\mathcal{G}\) is feasible with respect to \(\theta\)._  
_Proof of Property 2_  
Please refer to Appendix A.  
Computational complexity of the Algorithm 2 to check feasibility of nominal CPS is analyzed as follows. For each \(f\in\boldsymbol{J}_{1}\), Algorithm 2 constructs \(STN_{j}(V_{j},A_{j})\), finds a solution \(f_{j}\) for the spatial-temporal network \(STN_{j}(V_{j},A_{j})\) and updates \(\overline{C}_{rt}=\overline{C}_{rt}-\sum\limits_{a=(u,w)\in A_{jrt}}f_{j}(u,w )\forall r\in R\ \forall t\in\{1,2,\ldots,\Pi\}\) and \(f\gets f+f_{j}\). The number of nodes constructed in the spatial-temporal network \(STN_{j}(V_{j},A_{j})\) for type \(j\) task, where \(j\in\boldsymbol{J}\) is \(N_{j}\Pi+2\). The number of arcs constructed in the spatial-temporal network \(STN_{j}(V_{j},A_{j})\) for type \(j\) task, where \(j\in\boldsymbol{J}\), is bounded by \(2N_{j}(\Pi-1)+2+\Pi\). Therefore, the complexity to construct \(STN_{j}(V_{j},A_{j})\) and the number of nodes in \(STN_{j}(V_{j},A_{j})\) is bounded by \(O(N_{j}\Pi)\). The problem to find the solution \(f_{j}\) for the spatial-temporal network \(STN_{j}(V_{j},A_{j})\) is a minimal cost flow problem with additional constraints. Therefore, a lower bound of the computational complexity to find the solution \(f_{j}\) for the spatial-temporal network with capacity constraint \(\overline{C}_{rt}\) is \(O(N_{j}^{2}\Pi^{2}Q_{j})\). Therefore, a lower bound on the computational complexity of the algorithm to construct \(RSTN_{j}(V_{j},A_{j})\) and find a solution is \(O(JR^{2}\Pi^{2}+N_{j}^{2}\Pi^{2}Q_{j})\). As the number of arcs in the set \(A_{rt}\) is no greater than \(R\Pi\), the number of arithmetic operations involved in calculating \(\sum\limits_{a=(u,w)\in A_{rt}}f_{j}(u,w)\) is bounded by \(JR\Pi\) for each \(r\in\mathbf{R},\ t\in\{1,2,\ldots,\Pi\}\). Therefore, the overall computational complexity to compute \(\overline{C}_{rt}-\sum\limits_{a=(u,w)\in A_{rt}}f_{j}(u,w)\forall r\in \mathbf{R}\ \forall t\in\{1,2,\ldots,\Pi\}\) is bounded by \(JR^{2}\Pi^{2}\). Therefore, the overall computational complexity to update \(\overline{C}_{rt}\) is \(O(JR^{2}\Pi^{2})\). As \(\boldsymbol{J}_{1}\) is set to \(\boldsymbol{J}\) initially in Algorithm 2 and \(|\boldsymbol{J}|=J\), a lower bound on the computational complexity of Algorithm 2 to check feasibility is \(O(J^{2}R^{2}\Pi^{2}+JN_{j}^{2}\Pi^{2}Q_{j})\), which is of polynomial complexity.