# A Petri Net-Based Algorithm for Solving the One-Dimensional Cutting Stock Problem
## 8 Discussion  
It can be observed from the results shown in the previous section that the FBS-PN-CSP algorithm is effective and efficient in most of the instances it was tested in comparison with the other two algorithms, except for the _hard10_ dataset. The LLA algorithm could only address the instances of the _hinterding_, _binpack1_, _binpack2_, _binpack3_, and _binpack4_ datasets. It was less effective than the FBS-PN-CSP but more efficient in those instances where they obtained the same best stock result. A reason for this better efficiency is that to construct the cutting patterns the LLA increases the allowed waste in one unit from one iteration to the next, obtaining the best cutting patterns that meet the waste requirement without considering higher amounts of allowed waste. Meanwhile, the FBS-PN-CSP considers several amounts of waste simultaneously, represented by the pattern transitions. As the stock gets longer and the item types increase, the incidence matrix increases accordingly making the computations slower. This observation can be noted with the _hard10_ dataset, which has the longest stock among the datasets tested, and a higher number of item types. A modification in the structure of the PN model such as considering one pattern transition per unit of waste like in the LLA algorithm may improve the performance of the FBS-PN-CSP. Contrary to the LLA algorithm, which tests complete cutting patterns for each allowed waste on each iteration impacting its effectiveness as the stock gets longer, the FBS-PN-CSP constructs the solutions adding one item at a time. The algorithm would have to be modified accordingly to consider the different amounts of waste. Considering the time for the best solution found by the G&S algorithm, the FBS-PN-CSP was more efficient in 50% or more of the instances where both algorithms obtained the same best results for the _hinterding_, _wae_gau1_, _hard28_, _binpack1_, and _binpack2_ datasets. Most of the time required by the G&S algorithm is spent on the cutting patterns construction. Then, as the number of items increases the number of cutting patterns also increases. Nevertheless, the G&S algorithm was limited to constructing 1,000,000 cutting patterns for each instance. In contrast, the FBS-PN-CSP only generates cutting patterns considering those partial solutions with the least waste, and discards immediately the worst solutions. It also should be taken into account that the G&S algorithm had a time limit for its execution of 600 s. Except for the _hard10_ dataset, the FBS-PN-CSP best results were obtained below this time in only one execution. Additionally, the average time from 10 executions of the G&S was longer than the FBS-PN-CSP algorithm and the LLA algorithm in most instances. The results of the _binpack1_, _binpack2_, _binpack3_, and _binpack4_ datasets provide us insights into the sensitivity of the beam width and filter width as the number of item types and the number of orders increase while the stock length remains equal. As the number of orders and item types increased, the best solutions were found with the higher tested values for the beam width and the filter width. The reason is that the more item types, the more item places are needed in the PN model. Thus, more solutions need to be evaluated at the first level of the reachability tree, and higher values of beam width and filter width are preferred to evaluate most of those solutions from the second level, but this impacts the efficiency. The proposed improvement for the PN model structure could also be useful to address this efficiency issue since with a smaller incidence matrix size the computations should be faster and the FBS algorithm could be implemented with higher values of beam width and filter width. From the results of all the tested instances, it is demonstrated that the FBS-PN-CSP could address real-world 1D-CSP problems from small to large number of items. However, the length of the stock impacts its efficiency as shown with the _hard10_ dataset.