# A Petri Net-Based Algorithm for Solving the One-Dimensional Cutting Stock Problem
## 5 Filtered Beam Search Algorithm Implementation
28:if\(\mathcal{M}_{r}\
eq\emptyset\)then
29: Kept the \(\tau=\min(\alpha,|\mathcal{M}_{r}|)\) markings with the lowest \(F_{local}\) cost and eliminate the remaining ones from \(\mathcal{M}_{r}\). 30:endif
31:else
32: Keep the markings in \(\mathcal{M}_{r}\). 33:endif
34: Make \(New\ level\cup\mathcal{M}_{r}\)
35:endif
36:endfor
37: Check whether the final marking \(\mathbf{M}_{f}=[L\quad 0\quad 0\quad\cdots\quad 0\quad 0\quad*\quad*\quad*]\) has been reached. 38:if\(\mathbf{M}_{f}\) has been reached then
39:\(F_{best}\gets F_{global}\)
40:\(Best\ solution\gets True\)
41:else
42:\(level\gets level+1\)
43:\(Current\ level=New\ level\)
44:endif
45:endwhile
```  
**Algorithm 1** Pseudocode of algorithm FBS-PN-CSP  
In most beam search algorithm implementations, node costs at any node are computed using a function that considers cumulative costs up to the node and an estimation of the remaining solution's cost. The effectiveness of these algorithms heavily depends on choosing the right estimation cost function. Usually, in the FBS algorithm, local evaluation uses cumulative costs, while global evaluation considers both cumulative and estimated costs. Our FBS implementation employs the objective function (1) as a fitness function to perform both local and global evaluations. This function calculates the complete solution, capturing the number of stocks used, the total waste generated, and the number of stocks with waste that have been generated in the solution. As we progress in constructing the reachability tree, each node or marking represents only a partial solution, thus its corresponding cost is also partial. Despite not having a complete solution, partial solutions provide insights into the number of stocks used, those with or without waste, and the amount of unused material or potential waste on the current stock. For example, at the initial marking or root node, no stock has been used, resulting in no stocks with or without waste, and an unused material length of \(L\). At level L1, item markings represent solutions where one order of each item has been taken, but no stock has been fully utilized with or without waste. Eventually, as the reachability tree progresses, pattern markings are reached at some level, indicating that a cutting pattern has been obtained. At the first pattern marking, a stock has been used, and the waste amount for the stock is known. Subsequent item markings' costs must consider the used stock and its waste. It can be seen from the objective function (1) that the first term sums the partial wastage of each used stock, while the second sums the number of stocks with waste. We compute two cumulative costs accordingly: one for waste using Equation (9) and another for the number of stocks with waste using Equation (10). Both are employed in Equation (11) for the global evaluation of nodes. These two cumulative costs are computed upon reaching a pattern marking, while Equation (12) is utilized for local evaluations, considering the unused material of the current stock in each solution. \[W_{w}=W_{w}+\sqrt{\frac{w_{j}}{L}} \tag{9}\]  
\[W_{sw}=\frac{M(p_{m+5})}{M(p_{m+5})+M(p_{m+4})} \tag{10}\]  
\[F_{global}=\frac{W_{w}+W_{sw}}{M(p_{m+5})+M(p_{m+4})+1} \tag{11}\]  
Figure 6: Reachability tree construction with FBS implementation. \[F_{local}=\left\{ \begin{array}{ll}\frac{1}{M(p_{m+5})+M(p_{m+4})+1}\left(\frac{M (p_{1})}{L}+W_{sw}\right)&\text{if $M$ is an item marking}.\\ \\ \frac{1}{M(p_{m+5})+M(p_{m+4})+1}\left(\frac{w_{i}}{L}+W_{sw}\right)&\text{if $M$ is a pattern marking}. \end{array} \right. \tag{12}\]  
In Equations (9) and (12), \(w_{j}\) is obtained from the incidence matrix of PN-CSP, where \(w_{j}=\mathbf{I}(p_{m+3},t)\) for \(t\in\{t_{m+2},t_{m+3},\ldots,t_{m+L}\}\). This is because when a pattern transition is fired, the marking of place \(p_{1}\) is immediately updated to \(L\), indicating that the amount of waste in the already used stock is lost. However, this amount of waste can be determined from the incidence matrix.