# A Scheduling Algorithm for Multi-Workshop Production Based on BOM and Process Route
## 3 Process Network Diagram Model Based on BOM and Process Route
With the organization of product BOM and its process, a process network diagram of the workshop level can be formed; then, further decomposition can be carried out according to the sequence of products in each workshop to form a process-level process network diagram, which can be expressed as \(X^{\prime\prime}\) = (\(W\), \(N\), \(C\), \(M\)), in which \(W\) is the set of workshops, \(N\) is the set of process nodes in the new network diagram, \(C\) is the relationship matrix between nodes, \(M\) is the set of equipment, \(c_{uv}\) = 1 means that process \(v\) is the succeeding node of process \(u\), \(r\) is the number of nodes, \(c_{sum}\) = 1 represents process \(u\) of node, and \(c\) is processed by equipment \(m\) in workshop \(s\). \[C\)=\(\left\{c_{uv}\right\}\)\(u,v=1,...,r \tag{9}\]  
\[r=\sum\limits_{i=1}^{n}\sum\limits_{s=1}^{w}L(i,s) \tag{10}\]  
\[c_{uv}=\left\{ \begin{array}{c}1,(Q_{uv},Q_{uv}\in Q_{i},v=u+1)\cup(u=\sum \limits_{i=1}^{i}\sum\limits_{s=1}^{n}L(t,s)-1,v=\sum\limits_{t=1}^{j-1}\sum \limits_{s=1}^{w}L(t,s)+1,P_{i}\in P_{j}^{s})\\ 0\end{array} \right. \tag{11}\]  
\[c_{sum}=\left\{ \begin{array}{c}1,m\in M_{s}\\ 0\end{array} \right. \tag{12}\]  
4. For multiple products, we can convert the BOM structure according to step 1 for each product. If there are relevant nodes, a merge procedure can be performed, and then the conversion can be performed according to step 2 and step 3. Finally, a complete process network diagram can be created. For product A-L shown in Figure 3, its process routes are shown in Table 1. Product A is composed of B and C, C is composed of D and E, product F is composed of G and H, G and H are composed of E, I and D, J, respectively, and E is composed of K and L. Products A and F both contain part D and assembly E. The process relationship of these products is shown in Table 1. These products are processed or assembled by the equipment in W1-W4 workshops. According to the above steps, it can be converted into a workshop-level process  
time, so as to minimize the overall production cycle time. The constraints of the above scheduling problem are as follows:  
1. Each product can be processed by multiple devices in multiple workshops;
2. The workshop where each process is located and the device used by each process are determined;
3. At a certain processing time, one device can only be occupied by one process;
4. At a certain processing time, a product can only be processed by one device and cannot be interrupted once the process starts;
5. The product is processed in the order of its process route, and one process cannot be started until its preceding process is completed;
6. The product must follow its BOM structure; that is, the product can start only after all its components have been completed;
7. The product should be completed before its delivery date. For the scheduling problem of \(n\) products in a multi-workshop environment, according to the structure of the process network diagram and the above constraints, we can see that each process of the products needs to be processed according to the process network diagram and the constraints on the workshop, device, and process. The ultimate goal is to obtain the optimal processing cycle--that is, to minimize the maximum completion time of each product. The mathematical model of this problem can be expressed as Equation (13):  
\[T=\min(\max(TQ_{il}^{e})) \tag{13}\]  
The constraints can be expressed as:  
\[TQ_{ik}^{e}+TQ_{ik}\leq TQ_{i,k+1}^{e} \tag{14}\]  
\[TQ_{ik}^{e}+TQ_{ik}\leq TQ_{ih}^{e},MQ_{ik}=MQ_{ih} \tag{15}\]