# A Petri Net-Based Algorithm for Solving the One-Dimensional Cutting Stock Problem
## 3 Basic Concepts
### Petri Nets  
PN was introduced by [PERSON] in 1960 as part of his doctoral dissertation. Since then, many researchers have studied PN theory and its applications. Additionally, other types of PN, such as timed PN, colored PN, and stochastic PN, have been developed to enhance their modeling power. In this paper, we will refer to the ordinary PN. An ordinary PN, or simply PN, is a bipartite graph consisting of two sets of nodes: \(P=\{p_{1},p_{2},\ldots,p_{r}\}\), and transitions \(T=\{t_{1},t_{2},\ldots,t_{s}\}\), such that \(P\cap T=\emptyset\). These nodes are connected by a set of directed arcs \(F\subseteq\{(P\times T)\cup(T\times P)\}\). Places may represent activities or conditions in systems modeling, whereas transitions represent the occurrence of a condition or the execution of an activity [53]. Figure 1 shows a typical example of a PN model, where circles represent places and rectangles represent transitions, respectively. Each arc carries a number or arc weight, defined by the function \(W:F\to N^{+}\), which helps simulate the system's dynamics. Moreover, a particular state of the system is represented by a distribution of tokens (black dots) within the places, resulting in the marking of the PN. Formally, a marking is defined by the function \(M:P\to N\). A marked place means that the corresponding activity or condition is being executed. The dynamics or evolution of PN markings involves removing and adding tokens when a firing occurs. Let \({}^{\bullet}t\) and \(t^{\bullet}\) denote the sets of input and output places of transition \(t\). If \(M(p)\geq W(p,t)\) for each \(p\in{}^{\bullet}t\) at some marking \(M\), then the transition \(t\) is enabled and can be fired. When transition \(t\) is fired, \(W(p,t)\) tokens are removed for each \(p\in{}^{\bullet}t\), and \(W(t,p)\) tokens are added to each output place \(p\in t^{\bullet}\). The dynamics of a PN can also be described by matrix operations using Equation (6), known as the _state equation_ where \(\mathbf{M}_{k}\) is an \(r\times 1\) vector representing the current state or marking of the PN, and \(\mathbf{M}_{0}\) is the initial marking or state of the PN. \(\mathbf{I}\) is the incidence matrix of size \(r\times s\), given by Equation (7) where \(\mathbf{I}^{+}\) and \(\mathbf{I}^{-}\) are the input and output incidence matrices, respectively. \[\mathbf{M}_{k+1}=\mathbf{M}_{k}+\mathbf{I}\mathbf{u} \tag{6}\]  
\[\mathbf{I}=\mathbf{I}^{+}-\mathbf{I}^{-} \tag{7}\]  
Each entry of \(\mathbf{I}^{+}\) corresponds to the weights \(W(t,p)\), while in \(\mathbf{I}^{-}\) the entries correspond to the weights \(W(p,t)\), as shown in Equation (8) for the PN from Figure 1. Finally, \(\mathbf{u}\) is the firing vector of size \(s\times 1\), where one entry is \(1\) (indicating the transition to be fired at marking \(\mathbf{M}_{k}\)), and the remaining entries are zero. Typically, from a set of enabled transitions at a marking \(\mathbf{M}\), one transition is fired at a time to explore the possible states that can be reached from that marking. This is represented by the notation \(\mathbf{M}\xrightarrow{t}\mathbf{M}^{\prime}\), where \(t\) is the fired transition and \(\mathbf{M}^{\prime}\) is the marking reached from \(\mathbf{M}\). Figure 1: PN example. \[\mathbf{I}=\mathbf{I}^{+}-\mathbf{I}^{-}= \begin{bmatrix}0&0\\ 1&0\\ 0&2\\ 0&1\end{bmatrix} - \begin{bmatrix}2&0\\ 0&1\\ 1&0\\ 0&0\end{bmatrix} = \begin{bmatrix}-2&0\\ 1&-1\\ -1&2\\ 0&1\end{bmatrix}  \tag{8}\]  
Given a PN with an initial marking \(\mathbf{M}_{0}\), a firing path \(\sigma\) is a sequence of transitions fired from \(\mathbf{M}_{0}\) to marking \(\mathbf{M}^{\prime}\), denoted as \(\mathbf{M}\xrightarrow{\sigma}\mathbf{M}^{\prime}\). When this occurs, \(\mathbf{M}^{\prime}\) is said to be reachable from \(\mathbf{M}_{0}\). The set of all possible reachable markings from \(\mathbf{M}_{0}\) can be represented by a reachability tree, provided that this set is finite.