# A Theoretical Foundation for Context-Aware Cyber-Physical Production Systems
## 5 Approach to Deadline Awareness Problem and Future States Awareness Problem
### An Optimization Approach to Determining a Control Policy for CPPS
```
Input: \(Gj\), \(\Pi\), \(\Phi\), \(g(t)\), \(h(t)\) 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 the start node \(s_{j}\) Create the end node \(e_{j}\)\(V_{j}\leftarrow\left\{s_{j},e_{j}\right\}\) Step 1: For \(n=1\) to \(N_{j}+1\) For each \(\tau=1\) to \(\Pi+1\) Create a node with number \(v_{(n-1)(\Pi+1)+\tau}\)\(V_{j}=V_{j}\cup\left\{v_{(n-1)\Pi+\tau}\right\}\) End For Step 2: Create arc \(a(s_{j},1)\) from node \(s_{j}\) to the node \(v_{1}\)\(A_{j}\gets A_{j}\cup\left\{a(s_{j},1)\right\}\) Set arc cost \(\lambda\left(a(s_{j},1)\right)\gets 0\) Step 3: For \(n=1\) to \(N_{j}\) For each \(\tau=1\) to \(\Pi\) Create an arc \(a(v_{(n-1)\Pi+\tau}v_{(n-1)\Pi+\tau+1})\)\(A_{j}\gets A_{j}\cup\left\{a\right\}\) Set arc cost \(\lambda\left(a\left(v_{(n-1)\Pi+\tau}v_{(n-1)\Pi+\tau+1}\right)\right)\) to \(0\) End For Step 4: For \(n=1\) to \(N_{j}\) For each \(\tau=1\) to \(\Pi\) If \(\tau+\mu(t_{n})\leq\Pi+1\) Create arc \(a(v_{(n-1)(\Pi+1)+\tau}v_{n(\Pi+1)+\tau+\mu(t_{n})})\)\(A_{j}\gets A_{j}\cup\left\{a(v_{(n-1)(\Pi+1)+\tau}v_{n(\Pi+1)+\tau+\mu(t_{n})}) \right\}\) Set arc cost \(\lambda\left(a(v_{(n-1)(\Pi+1)+\tau}v_{n(\Pi+1)+\tau+\mu(t_{n})})\right)\gets 0\) Find the resource type \(\tau\) for processing operation \(n\)\(A_{jrt}\gets A_{jrt}\cup\left\{a(v_{(n-1)(\Pi+1)+\tau}v_{n(\Pi+1)+\tau+ \mu(t_{n})})\right\}\), the set of arcs in the spatial-temporal network of type-\(i\) task involved in the use of type-\(r\) resource in period \(\tau\) End If End For Step 5: For each \(\tau=1\) to \(\Pi+1\) Create arc \(a(v_{N_{j}\Pi+\tau},e_{j})\) from node \(e_{N_{j}\Pi+\tau}\) to node \(e_{j}\)\(A_{j}\gets A_{j}\cup\left\{a(v_{N_{j}\Pi+\tau},e_{j})\right\}\) If \(\tau>\Phi\) Set arc cost \(\lambda(a(v_{N_{j}\Pi+\tau},e_{j}))\gets h(\tau)\) Else Set arc cost \(\lambda(a(v_{N_{j}\Pi+\tau},e_{j}))\gets g(\tau)\) End If End For
```  
**Algorithm 1**Spatial-Temporal Network Construction Algorithm for Type-\(j\) Task Subnet  
The Joint Spatial-Temporal Network Construction Algorithm in Algorithm 2 first iteratively invokes Algorithm 1 to construct the Spatial-Temporal Network (STN) \(STN_{j}(V_{j},A_{j})\) for each type of task subnet and then construct \(JSTN(V,A)\) with \(V=\bigcup\limits_{j\in I}V_{j}\) and \(A=\bigcup\limits_{j\in I}A_{j}\). Algorithm 2 finally merges all start node \(s_{j}\) for all \(j\in I\) into one source node \(s\) to obtain the JSTN. Algorithm 2 in shows the Joint Spatial-Temporal Network Construction Algorithm. Note that the structure of a JSTN is different from that of a STN in [10] as JSTN represents the spatial-temporal relation of multiple types of tasks whereas a STN represents only the spatial-temporal relation of a single type of tasks. Figure 5 shows the structure of a JSTN. Figure 5: A Joint Spatial–Temporal Network (JSTN). The STN of type-\(j\) task subnet in \(G\) is denoted as \(STN_{j}(V_{j},A_{j})\). We define the subset of arcs in \(A_{j}\) that require type-\(r\) resources in period \(t\) below. **Definition 13**. : \(A_{j\tau}\) _is the set of arcs requiring the type-\(r\) resources in period \(t\)._  
Note that the states across the time horizon of the CPPS model \(G\) can be represented in the corresponding STNs. Therefore, we propose an optimization problem formulation to determine whether there exists a control policy that can bring \(G(m_{0})\) to \(G(m_{f})\) without visiting undesirable states by the deadline.