## 4 Generation of Solutions for Nominal CPS
In this case, the places in \(P_{j}\) are numbered from upstream to downstream and are denoted as \(p_{1}^{j}\), \(p_{2}^{j}\), \(p_{3}^{j}\), \(\ldots\), \(p_{2N_{j}+1}^{j}\), \(P_{j}=\{p_{1}^{j}\), \(p_{2}^{j}\), \(p_{3}^{j}\), \(\ldots\), \(p_{2N_{j}+1}^{j}\}\) and \(P_{j1}=\{p_{1}^{j}\), \(p_{3}^{j}\), \(p_{5}^{j}\), \(\ldots\), \(p_{2N_{j}+1}^{j}\}\). To represent timing in a spatial-temporal network \(STN_{j}(V_{j},A_{j})\), a time horizon of \(\Pi\) periods is considered. A node in \(STN_{j}(V_{j},A_{j})\) represents a specific point in time and space. We create \(\Pi\) nodes for each place in \(P_{j1}\), one start node and one end node in \(STN_{j}(V_{j},A_{j})\) to represent spatial-temporal information. In constructing \(STN_{j}(V_{j},A_{j})\), the capacity of an arc involving the use of type \(r\) resources is set to the residual capacity \(\overline{C}_{rt}\) of type \(r\) resources. Let \(C_{rt}\) denote the initial capacity (the number) of type \(r\) resources in period \(t\), where \(C_{rt}\) is set to \(m_{r0}(r)\) for all \(t\). Initially, the residual capacity \(\overline{C}_{rt}\) of type \(r\) resources in period \(t\) is set to \(C_{rt}\). The residual capacity \(\overline{C}_{rt}\) will be updated iteratively in the Algorithm 2 (to be introduced later) to check feasibility of nominal CPS to reflect the assignment of tasks to resources. The algorithm (Algorithm 1) to construct \(STN_{j}(V_{j},A_{j})\) for type \(j\) tasks, where \(j\in\mathbf{J}\), is as follows. ```
Input: \(G_{j}\), \(G_{r}^{k}\), \(k\in\Omega_{r}^{j}=\left\{1,2,\ldots,k_{r}^{j}\right\}\), \(\Pi\), \(Q_{j}\), \(\theta\) Output: \(STN_{j}(V_{j},A_{j})\), where \(V_{j}\) is the set of nodes and \(A_{j}\) is the set of arcs Step 0: Create a start node \(s_{j}\) and an end node \(e_{j}\) \(V_{j}=\left\{s_{j},e_{j}\right\}\) Step 1: For \(n=1\) to \(N_{j}\)  For each \(t=1\) to \(\Pi\)  Create a node numbered \((n-1)\Pi+t\)  Add the node to \(V_{j}=V_{j}\cup\left\{(n-1)\Pi+t\right\}\)  End For  End For Step 2: Add an arc \(a=(s_{j},1)\) from \(s_{1}\) to the node \(1\) \(A_{j}\gets A_{j}\cup\left\{a\right\}\)  Set arc capacity \(c_{a}\) to \(Q_{j}\) and arc cost \(w_{a}\) to \(0\) Step 3: For \(n=1\) to \(N_{j}\)  For each \(t=1\) to \(\Pi-1\)  Add an arc \(a\) from node \((n-1)\Pi+t\) to node \((n-1)\Pi+t+1\) \(A_{j}\gets A_{j}\cup\left\{a\right\}\)  Set arc capacity \(c_{a}\) to according to the residual capacity \(\overline{C}_{rt}\), where \(r\) is theresource type used by operation \(n\)  Set arc cost \(w_{a}\) to \(0\)  End For Step 4: For \(n=1\) to \(N_{j}\)  For each \(t=1\) to \(\Pi-1\)  If \(t+\mu(t_{2n-1})+\mu(t_{2n})\leq\Pi\)  Add an arc \(a\) from node \((n-1)\Pi+t\) to node \(n\Pi+t+\mu(t_{2n-1})+\mu(t_{2n})\) \(A_{j}\gets A_{j}\cup\left\{a\right\}\)  Find the resource type \(r\) for processing operation \(n\)  Update \(A_{jrt}\gets A_{jrt}\cup\left\{a\right\}\), the set of arcs in the spatial-temporal  network of type \(j\) task involved in the use of type-\(r\) resource in period \(t\)  Set arc cost \(w_{a}\) to \(0\)  End If  End For  Step 5: For each \(t=1\) to \(\Pi\)  Add an arc \(a\) from \(N_{j}\Pi+t\) to node \(e_{j}\) \(A_{j}\gets A_{j}\cup\left\{a\right\}\)  If \(t>\theta\)  Set arc cost \(w_{a}\) to \(t\)  Else  Set arc cost \(w_{a}\) to \(0\)  End If End For
```  
**Algorithm 1**Construct Spatial-Temporal Network \(STN_{j}(V_{j},A_{j})\) for Type \(j\) Tasks  
\(STN_{j}(V_{j},A_{j})\) captures the flows of parts temporally and spatially. To optimize the schedule to meet the deadline, the cost for an arc corresponding to period \(t\) after the deadline \(\theta\) is simply set to \(t\) and the cost for all the other arcs is set to zero. We use \(f_{j}\) to denote the flows of parts in \(STN_{j}(V_{j},A_{j})\). We use \(f_{j}(u,v)\) to represent the flows of parts from node \(u\) to node \(v\) in \(STN_{j}(V_{j},A_{j})\) across time and space. To concisely represent the flows in \(STN_{j}(V_{j},A_{j})\), we will use \(f_{u,v}\) instead of \(f_{j}(u,v)\) whenever it is clear from the context.