# A Petri Net-Based Algorithm for Solving the One-Dimensional Cutting Stock Problem
## 4 PN-Based Algorithm for Solving the 1D-CSP
### Marking Evolution and Solution Construction  
To obtain a solution for a given instance of the 1D-CSP with the PN model described in the previous section, referred to as PN-CSP, we begin with the initial marking as shown in Figure 4 where there is an unused stock (place \(p_{1}\)) and \(m\) items with their corresponding number of orders (places \(p_{2}\) to \(p_{m+1}\)). Hence, the general form of the initial marking of the PN-CSP is as follows:  
\[\mathbf{M}_{0}=[L\quad d_{1}\quad d_{2}\quad\cdots\quad d_{m+1}\quad 0\quad 0 \quad 0\quad 0]^{T}.\]  
From the initial marking, the enabled transitions are \(t_{1},t_{2},\ldots,t_{m}\) so that any of the items could be the first in the solution. The solution is constructed in a linear sequence of items arranged from left to right. Once an enabled transition is fired, the pattern place accumulates tokens representing the length of the item placed first in the solution. Suppose transition \(t_{2}\) is fired; then, the resulting marking is as follows:  
\[\mathbf{M}_{1}=[L-l_{2}\quad d_{1}\quad d_{2}-1\quad\cdots\quad d_{m+1}\quad l _{2}\quad 0\quad 0\quad 0]^{T}.\]  
While the number of tokens in \(p_{m+2}\) is not equal to or greater than any of the weights of the arcs \(L,L-1,L-2,\ldots,\lambda\), transitions \(t_{1},t_{2},\ldots,t_{m}\) can be fired one at a time because they will be the only ones enabled. This means the pattern formation continues as long as there is space in the current stock. However, if a determined pattern length less than the stock length is reached, such as \(L-1,L-2\), or \(\lambda\), the corresponding transition from \(t_{m+2}\) to \(t_{m+L}\) is enabled, considering there will be \(1,2\), or \(L-\lambda\) tokens in place \(p_{1}\), representing the waste of the stock. If one of the transitions \(t_{m+2},\ldots,t_{m+L}\) is selected to be fired, the pattern formation stops to renew the stock for a new pattern. For example, consider the marking:  
\[\mathbf{M}_{k}=[2\quad a\quad b\quad\cdots\quad c\quad L-2\quad 0\quad 0\quad 0]^{T},\]  
where \(a,b,\ldots,c\) are the corresponding remaining number of item orders after \(k-1\) items have been included in the first pattern of the solution, and \(M_{k}(p_{m+2})=L-2\). Then, \(t_{m+3}\) is enabled and can be fired, yielding the marking:  
\[\mathbf{M}_{k+1}=[L\quad a\quad b\quad\cdots\quad c\quad 0\quad 2\quad 0\quad 1]^{T}.\]  
Figure 5: General form of the incidence matrices: (**a**) input incidence matrix, \(I^{+}\). (**b**) output incidence matrix, \(I^{-}\). (**c**) incidence matrix, \(I\). Here, there is a new empty stock of length \(L\), and one stock with waste (\(M_{k+1}(p_{m+5})=1\)) has been generated as part of the solution with a waste of 2 (\(M_{k+1}(p_{m+3})=2\)). With the new empty stock, the construction of the solution continues with the remaining items' orders. When a pattern transition is fired, it means that a cutting pattern has been formed, adding a new stock with or without waste to the solution. These markings that enable and fire a pattern transition are called _pattern markings_. On the other hand, if an item transition is fired, it means that an item has been added to the current pattern in construction. These markings that enable and fire an item transition are called _item markings_. The marking evolution is performed as described, forming patterns and renewing the stocks when needed until all of the items have been included in a solution. When the number of tokens in places \(p_{2}\), \(p_{3},\ldots,p_{m+1}\) is zero, the solution has been completed, and the marking \(\mathbf{M}_{f}=[L\ \ 0\ \ 0\ \ \cdots\ \ 0\ \ 0\ \ \omega\ \ \
u\ \ \ \eta]^{T}\) is considered the final marking, where \(\omega\) is the final total waste, \(\
u\) is the final number of stocks without waste, and \(\eta\) is the final number of stocks with waste. Therefore, the solution can be obtained with the firing sequence \(\sigma\) obtained from \(\mathbf{M}_{0}\) to \(\mathbf{M}_{f}\), that is \(\mathbf{M}_{0}\overset{\sigma}{\rightarrow}\mathbf{M}_{f}\).