# A Scheduling Algorithm for Multi-Workshop Production Based on BOM and Process Route
## 6 Treatment of Time Constraints  
When there is a time limit, a large number of invalid paths will be generated in the process of algorithm evolution. To solve this problem, we can assign priority weight to activities and search nodes with high priority first. The assignment of priority weight values needs to consider the following aspects:  
1. Product delivery cycle: the weight coefficient can be set according to the product delivery cycle, and it is valid for all nodes of the product;
2. Level/complexity of the product: the farther the subordinate node is from the top node of the product, the higher the weight is required;
3. Number of peer nodes: the more peer nodes one node has, the higher weight the node needs to be assigned;
4. Process route and processing time: the longer the process flow and processing time are, the higher the weight required;  
Figure 6: Construction of the process network subgraph. The flexibility of the search needs to be ensured, and the search process can be limited according to the range of weights. The above method of priority assignment can ensure that the searched path is an effective path. The space for path search depends on the restriction of weight usage. If the restriction is strict, it is easy for the algorithm to fall into a local optimum, and if the restriction is loose, it will cause an invalid path. The priority weight value of the activity allocation can be determined by AHP (analytic hierarchy process). AHP is a practical multi-objective decision-making method. Using this method to analyze problems generally includes four steps: the goal of decision-making, the factors considered, and the decision-making object are layered according to their mutual relationship, and the hierarchical structure diagram is drawn; the judgment matrix is constructed to determine the weight of each factor at each level; the single-level ranking is carried out--that is, for a factor at the upper level, the importance of each factor is ranked, and the consistency test is carried out; the hierarchical total ranking is to calculate the weight of the relative importance of all factors at a certain level to the total goal, which is carried out from the highest level to the lowest level in turn. However, the method of priority weight assignment has the problem of the search space being too small. In this regard, this study proposed a new path search strategy, the path search rescheduling strategy, which does not limit the range of the path search. This strategy is suitable for some products with time constraints and can ensure that effective search paths are obtained. The path search rescheduling method adjusts the products that do not meet the schedule constraints and adjusts other products that do not meet the schedule constraints caused by this adjustment. Through this traversal adjustment, all products finally meet the schedule requirements. For the search path 4-5-3-2-1-7-8-6 shown in Figure 7, if the delivery cycle of product 6 is at 7, Figure 7 indicates that the scheduling cannot meet the requirements, and the cycle of product 1 is lost; then, product 6 can be moved before product 1, and its subordinate product 7 needs to be moved to the front of product 2 to form a new search path, as shown in Figure 7. Then, both products 1 and 6 meet the scheduling requirements. The implementation of the path search rescheduling strategy is shown in Figure 8.  
In the figure above, \(Q1\) and \(Q2\) represent the sets of processes to be moved and affected, respectively. The implementation process of path search rescheduling is divided into two processes, respectively, for \(Q1\) and \(Q2\). In the flow on the left side of the diagram, first add the process that needs to be moved to \(Q1\), and check whether moving process \(A\) at the end of \(Q1\) will affect other processes of the same device. If no, move process \(A\) directly. If yes, add the affected process to \(Q2\). Delete process \(A\) from \(Q1\), then judge whether moving process \(A\) will affect its superior processes.