# A Petri Net-Based Algorithm for Solving the One-Dimensional Cutting Stock Problem
## 5 Filtered Beam Search Algorithm Implementation
The cumulative costs \(W_{w}\) and \(W_{sw}\) are set to zero for the item markings between the initial marking and the first pattern marking. These costs are computed and updated at each reached pattern marking. Consequently, the outcomes of \(W_{w}\) and \(W_{sw}\) are retained for the item markings between two subsequent pattern markings. Once the final marking is reached, the last \(F_{global}\) outcome is set as the best solution \(P_{best}\). To determine whether the final marking has been reached, at each level, we compare the markings obtained with the desired final marking \(\mathbf{M}_{f}(p_{1})\). However, we only consider the marking of places \(p_{1},p_{2},\ldots,p_{m+2}\). Specifically, we compare the marking \(\mathbf{M}=[M(p_{1})\quad M(p_{2})\quad M(p_{3})\cdots M(p_{m+1})\quad M(p_{m+ 2})\quad*\quad*\quad*]\), obtained at some level, with the final marking \(\mathbf{M}_{f}=[L\quad 0\quad 0\quad\cdots\quad 0\quad 0\quad*\quad*\quad*]\). The \(*\)\(*\) means that the marking of the corresponding places is not considered for the comparison. This is because we do not know in advance how much waste would be generated by the best solution or the number of stocks with and without waste. However, we know that at the final marking, there are no more item orders to place, and the last stock is generated when the last item order is taken for the final cutting pattern. Observe from Algorithm 1, lines 15 and 27, that when performing global and local evaluations, we do not necessarily select \(\beta\) or \(\alpha\) number of markings, respectively. Instead, we select the minimum value between \(\beta\) (or \(\alpha\)) and the number of markings obtained globally (or locally). This is because, in a reachability tree, a marking could be generated by firing different transitions, resulting in fewer markings than the \(\beta\) markings needed at a level or fewer than the \(\alpha\) markings needed from a parent marking or beam node. In some beam search algorithm implementations, if the required \(\beta\) nodes are not met for some level, then more parent nodes at the previous level are explored to meet the required \(\beta\) nodes. However, we do not conduct this in our FBS implementation, as it is possible to encounter dead markings. This might make it impossible to complete the required number of nodes. Dead markings are related to the liveness property of a PN and this property is closely related to the presence of siphons [65]. It is known that a PN with siphons is likely to be non-live, as once the places of a siphon become unmarked at some marking, they remain unmarked in all subsequent markings. We performed a structural analysis for an instance with ten different items and a total of 20 orders, using an open-source PN modeling platform called PIPE2 version 4.3.0 [66] to determine the presence of siphons. The results are shown in Figure 7, indicating that place \(p_{2}\) (\(p_{1}\) according to the enumeration of the PIPE2 platform) is a minimal siphon. Extending this result for the general PN-CSP model with the initial marking in the general form, and considering the dynamics described in the above paragraphs, places \(p_{1},p_{2},\ldots,p_{m}\) could be minimal siphons and could become unmarked at some marking. The PN-CSP would become deadlocked if all the places \(p_{1},p_{2},\ldots,p_{m}\) are unmarked, although this situation indicates that the desired final marking has been reached. However, to prevent our algorithm from getting stuck due to incomplete \(\beta\) nodes at some levels and potentially failing to reach the desired final marking, we decided to use the minimum number of nodes as outlined in Algorithm 1.