# A Petri Net-Based Algorithm for Solving the One-Dimensional Cutting Stock Problem
## 4 PN-Based Algorithm for Solving the 1D-CSP
### PN Model for the 1D-CSP  
As mentioned above, we use ordinary PN to model a given instance of the 1D-CSP. Figure 4 illustrates the general PN model for a given instance of the 1D-CSP, with \(m\) different items and stock length \(L\). The construction of a solution for a 1D-CSP instance through the PN model follows the next-fit heuristic principle. This means that items are added sequentially to the solution as long as the total length of the items, or pattern length, does not exceed the length of the stock. Otherwise, the next item is put into a new stock, and the process is repeated until all items have been added to the solution. In this way, there will be patterns with or without waste, and the total waste of the solution will be the sum of the waste yielded from each pattern. The PN model allows the formation of patterns with and without waste, enabling the beam search algorithm to find the solution with the minimum waste and the minimum number of stocks with waste. According to the general PN model, there will be \(m\) places for each item type labeled \(p_{2},p_{3},\ldots,p_{m+1}\), as shown in Figure 4. We refer to these places as _item places_. The number of tokens inside the item places represents the number of orders of each item, denoted \(d_{1},d_{2},\ldots,d_{m}\). The stock is represented by a single place labeled \(p_{1}\), and the number of tokens inside this place is equal to the stock length, \(L\). We refer to this place as the _stock place_. Item places, as well as the stock place, are input places for transitions \(t_{1},t_{2},\ldots,t_{m}\), referred to as _item transitions_. Each item transition consumes a token from its corresponding item place, indicating that an order of that item is being put into a solution. Similarly, each item transition removes \(l_{i}\) tokens from the stock place, which corresponds to the length of the item of the corresponding item place. As items are taken, a pattern is formed, and its length is accumulated in the place labeled \(p_{m+2}\), which we name the _pattern place_. As  
Figure 3: Filtered beam search scheme. shown in Figure 4, the pattern place is an output place of each item transition, where each one adds \(l_{i}\) tokens to the pattern place according to the item length it is being added to the solution. Therefore, the number of tokens inside the pattern place varies from 0 to \(L\). However, the minimum pattern length will be \(\lambda=min\{l_{1},l_{2},\ldots,l_{m}\}\), representing a pattern formed by only one order of the item with the smallest length. The transitions \(t_{m+1},t_{m+2},t_{m+3},\ldots,t_{m+L}\) are the _pattern transitions_, and there will be \(L\) transitions of this type. A pattern transition removes tokens from the pattern place according to the corresponding pattern length that has been formed. For example, \(t_{m+1}\) removes \(L\) tokens, \(t_{m+2}\) removes \(L-1\) tokens, and so on, such that \(t_{m+L}\) removes \(\lambda\) tokens. Since a pattern includes the lengths of the items as well as the unused material of the stock (if any), pattern transitions \(t_{m+2},t_{m+3},\ldots,t_{m+L}\) are output transitions of the stock place to complete the pattern formation. Thus, \(t_{m+2}\) removes one token, \(t_{m+3}\) removes two tokens, and so on, such that \(t_{m+L}\) removes \(L-\lambda\) tokens from the stock place. Transition \(t_{m+1}\) is not an output transition of the stock place since it corresponds to a pattern without waste. At the same time, the pattern transitions are input transitions of the stock place so that once a pattern has been formed and included in a solution, another stock must be available to continue the process of forming the solution. Each pattern transition adds \(L\) tokens to the stock place as shown in Figure 4. So far, the PN model can construct any possible solution by starting with any item, but we included three more places to enhance the model.