## 4 Configuration/Scheduling Feasibility Problem and Context Generation Problem in CPS
The number of tokens \(m_{nt}(r_{a})\) in the resource idle place \(r_{a}\) can be calculated by \(m_{n0}(r_{a})-\sum\limits_{\tau=t-(\mu_{n}^{k}(t_{a})+\mu_{n}^{k}(t_{a}))+1}^{ t}w_{nt}\). Based on the above reasoning, any reachable marking of \(\Psi_{n}=\left(P_{n},T_{n},F_{n},m_{n0},\mu_{n}\right)\) can be represented in \(DG_{n}(V_{n},E_{n})\). The following properties hold for \(DG_{n}(V_{n},E_{n})\) and DTPN \(\Psi_{n}\)=\(\left(P_{n},T_{n},F_{n},m_{n0},\mu_{n}\right)\). **Property 1**. : _Each marking reachable from DTPN \(\Psi_{n}=\left(P_{n},T_{n},F_{n},m_{n0},\mu_{n}\right)\) can be represented by \(DG_{n}(V_{n},E_{n})\)._  
**Property 2**. : _Suppose \(DG_{n}(V_{n},E_{n})\) satisfies constraints (1)-(9). Then there is a marking of \(\Psi_{n}=\left(P_{n},T_{n},F_{n},m_{n0},\mu_{n}\right)\) corresponding to \(DG_{n}(V_{n},E_{n})\)._Property 1 and Property 2 indicate that the dynamics of DTPN \(\Psi_{n}=(P_{n},T_{n},F_{n},m_{n0},\mu_{n})\) can be analyzed based on \(DG_{n}(V_{n},E_{n})\). Conversely, a \(DG_{n}(V_{n},E_{n})\) represents an evolution trajectory of \(\Psi_{n}\). Based on this observation, Problem 1 defined previously to determine whether there exists a firing sequence \(S_{n}\) for \(\Psi_{n}\) such that the final transition \(t_{nf}\) of \(\Psi_{n}\) is the last firing sequence in \(S_{n}\) and is fired \(Q\) times by the deadline \(\theta\) can be stated as the following problem:  
**Problem 2**. : _Find \(h_{nkt}\), \(w_{nkt}\) and \(l_{nt}\) in \(DG_{n}(V_{n},E_{n})\) subject to constraints (1)-(9) such that \(\sum\limits_{t\in\{1,2,\ldots,\theta\}}l_{n\theta}=Q\)._  
Instead of solving Problem 2 directly, we formulate Problem 3 below and show that the solution to Problem 3 can be used to check whether there exists a solution to Problem 2. Let \(DG_{n}(V_{n},E_{n})\) be the graph model constructed by applying the DTPN2 GT algorithm to \(\Psi_{n}\). Problem 3 aims to find \(h_{nkt}\), \(w_{nkt}\) and \(l_{nt}\) in \(DG_{n}(V_{n},E_{n})\) by minimizing the objective function \(\sum\limits_{t=1}^{T}\sum\limits_{k=1}^{K_{n}+1}\left(c_{nkt}^{t}h_{nkt}\right) +\sum\limits_{t=1}^{T}\sum\limits_{k=1}^{K_{n}+1}\left(c_{nkt}^{w}w_{nkt}\right) +\sum\limits_{t=1}^{T}\left(c_{nt}^{t}l_{nt}\right)\). **Problem 3**. : \(\underset{h,w,l}{min}\sum\limits_{t=1}^{T}\sum\limits_{k=1}^{K_{n}+1}\left(c_ {nkt}^{h}h_{nkt}\right)+\sum\limits_{t=1}^{T}\sum\limits_{k=1}^{K_{n}+1}\left( c_{nkt}^{w}w_{nkt}\right)+\sum\limits_{t=1}^{T}\left(c_{nt}^{t}l_{nt}\right)\) subject to constraints (1) through (9). The following property holds for Problem 2 and Problem 3 stated above. **Property 3**. : _There exists a solution to Problem 2 if and only if there exists a solution to Problem 3 with \(l_{nt}\) = 0 for all \(t>\theta\)._  
**Proof. ** Please refer to Appendix A for the proof of Property 4. \(\square\)  
Property 3 states the feasibility condition for a product agent. To establish the feasibility condition for a configuration, we need more definitions as follows:  
**Definition 7**. : _A process agent \(w_{n}\) without an upstream process agents is called an input process agent._  
**Definition 8**. : _An input process agent \(w_{n}\) and a set of resource agents involved the in the multi-level contract net protocol form a feasible configuration if there exists a solution to Problem 3 with \(l_{nt}\) = 0 for all \(t>\theta\). Such an input process agent \(w_{n}\) is called feasible._  
**Definition 9**. : _A process agent \(w_{n}\) with at least one upstream process agent is called a non-input process agent._  
**Definition 10**. : _A non-input process agent \(w_{n}\) and a set of resource agents involved the in the multi-level contract net protocol form a feasible configuration if there exists a solution to Problem 3 with \(l_{nt}\) = 0 for all \(t>\theta\) and there exists at least one upstream feasible process agent with for each input place in \(P_{n}^{ki}\). Such a non-input process agent \(w_{n}\) is called feasible._  
**Definition 11**.