In this article, an analysis of the main methods for solving the linear cutting problem (LCP) with the criterion of minimizing the number of knife rearrangements is presented. The linear cutting problem in its general form represents an optimization problem that involves placing given types of material (rolls) in such a way as to minimize waste and/or maximize the use of raw materials, taking into account constraints on the number of knives, the width of the master roll, and the required orders. This article discusses a specific case of the problem with an additional condition for minimizing knives' changes and the following approaches for its solution: the exhaustive search method, which ensures finding a global optimal solution but can be extremely inefficient for problems with a large number of orders, as well as random search based on genetic and evolutionary algorithms that model natural selection processes to find good solutions. Pseudocode is provided for various methods of solving the LCP. A comparison is made in terms of algorithmic complexity, controllability of execution time, and accuracy. The random search based on genetic and evolutionary algorithms proved to be more suited for solving the LCP with the minimization of waste and knife rearrangements.

Keywords: paper production planning, linear cutting, exhaustive search, genetic algorithm, waste minimization, knife permutation minimization