Solution of the problem of finding the optimal column in terms of optimal paper cutting

This paper describes the search of the optimal column in terms of the column generation method for solving the problem of paper cutting. The initial problem is a search for a set of cutting plans, providing the production of all products in the required amounts with minimal waste of material in the edge. The column generation method was chosen due to the large variety of options cutting. This raises the problem of finding the optimal column at each iteration by solving the auxiliary problem of linear cutting given the large number of technological parameters. The solution is arrived at by means of linear and dynamic programming, the correctness of using these algorithms in the conditions of the problem is also investigated. The problem is complicated by considering the deadlines of production orders. The algorithm developed, which is part of a software system, has been tested on a set of real industrial data of pulp and paper mills. As a result of testing a 1–2 percent increase of useful production using the software system was observed. Bibliogr. 10.