# FMS Scheduling under Availability Constraint with Supervisor Based on Timed Petri Nets
## 5 Modeling FMS with the Decomposed TPN to the TMG Set  
### Decomposition Methodology  
The optimal legal firing sequence problem is impossible to solve when the number of jobs and machines is increased, i.e., scalability issue. Thus, the entire TPN \(=(P,T,O,W,h(T))\) explicitly models the physical functioning of FMS decomposed into several timed marked graphs, for the following reasoning. First, the set of transitions \(T\) is considered as a disjoint subset \(T_{i}\), which contains the transitions \(t_{i,j}\).  
\[T=T_{1}\cup T_{2}\cup\ldots\cup T_{n}=\left(\bigcup_{i=1}^{n}T_{i}\right) \tag{3}\]  
Place set \(P\) presents disjoint subsets \(P_{i}\), which contain the places \(p_{i,j}\) and the set of resource-places \(P_{R}=\{p_{r},1\leq r\leq m\}\):  
\[P=P_{1}\cup P_{2}\cup\ldots\cup P_{n}\cup P_{R}=\left(\bigcup_{i=1}^{n}P_{i} \right)\bigcup P_{R} \tag{4}\]  
\[P_{i}=\{p|\ ^{\circ}p\subseteq T_{i}\ and\ p^{\circ}\subseteq T_{i}\} \tag{5}\]  
Each resource-place \(p_{j}\in P_{R}\) satisfies Equations (4) and (5):  
\[\ ^{\circ}p_{j}=\left\{t_{i,j}|0\leq j\leq m\right\} \tag{6}\]  
\[p_{j}^{\circ}=\left\{t_{i,j-1}|1\leq j\leq m\right\} \tag{7}\]  
The second stage of the modeling methodology aims to remove the resource places from the entire TPN. Indeed, the resulting TPN is divided into \(n\) timed marked graphs TMG\({}^{i}=(P_{i},T_{i},O_{i},W_{i},h(T_{i}))\), \(1\leq i\leq n\), which model the free-dynamic of job \(i\). Hence, the place set \(P_{i}\), direct arcs \(O_{i}\) and affection weights \(W_{i}\) satisfy the following equations:  
\[\bigcup_{i=1}^{n}P_{i}=P\backslash P_{R},\ \forall\ p\in P_{i} \tag{8}\]  
\[O_{i}(p,t)=O(p,t),\ \forall\ p\in P_{i},\ \forall\ t\in T_{i} \tag{9}\]  
\[O_{i}(t,p)=O(t,p)\ \forall\ p\in P_{i},\ \forall\ t\in T_{i} \tag{10}\]  
\[W_{i}(p,t)=0,\ \forall\ p\in P_{R},\ \forall\ t\in T_{i} \tag{11}\]  
\[W_{i}(t,p)=0,\ \forall\ p\in P_{R},\ \forall\ t\in T_{i} \tag{12}\]  
Therefore, \(\cup_{i=1}^{n}\)TMG\({}^{i}\) represents the free-dynamic of jobs without considering the constraints explained in the above section. This is the reason why new parameters as timed direct arcs and extra times should be considered in the decomposed model (Section 3); parameters are computed using our methodology developed in the following section. Based on the third assumption in Section 4, the TPN model parameterization could be concluded through the A(\(t_{i,1},t_{i^{*},0}\)) value determination.  
Therefore, Algorithm 1 summarizes the decomposition methodology.  
```
Step 1. Model the considered system as a set of timed marked graphs taking into account the resource places. Step 2. Elimination of resource places. The resulting net is \(\cup_{i=1}^{n}\)TMG\({}^{i}\) in which each TMG\({}^{i}\) models separately the free-dynamics of job \(i\). Step 3. Add the timed direct arcs between transitions \(\left(t_{i,1},t_{i,0}\right)\), which ensure the right sequence of jobs through operators. Step 4. Introduce the eventual extra time \(\varphi_{t_{i,j}}\left(Z_{i,j+1}\right)\in\mathbb{N}\) that presents the number of times slice delays of job \(i\) in machine \(j\), when the next machine \(j+1\) is unavailable.
```  
**Algorithm 1**The methodology of TPN decomposition.