DOI: 10.17587/prin.15.35-43
Genetic Algorithm for Linear Cutting Problem
R. V. Voronov, Professor, rvoronov@petrsu.ru, A. I. Shabaev, Associate Professor, vlad991199@yandex.ru, V. V. Klimenko, Postgraduate Student, vlad991199@yandex.ru, Petrozavodsk State University, Petrozavodsk, 185910, Russian Federation
Corresponding author: Vladislav V. Klimenko, Postgraduate Student, Petrozavodsk State University, Petrozavodsk, 185910, Russian Federation, E-mail: vlad991199@yandex.ru
Received on October 12, 2023
Accepted on November 14, 2023
The article deals with the problem of calculating the volume calendar plan of a paper mill. To find the optimal schedule, a combination of the following criteria is used: minimal trim loss, minimal changes to the knives setup and smooth transitions by product grades. Solution algorithms are presented that use a combination of the simplex method, the column generation, the branch and bound methods, the greedy algorithm.
The specifics of paper production and sales are taken into account — customer orders are measured not in the whole number of units of finished products, but by weight, which is specified with "tolerances".
A variant of the genetic type algorithm for the paper production planning problem is proposed. The algorithm uses special crossover and mutation operators based on the multiple solution of quadratic or linear programming problems. The result of a computational experiment based on real production data of a paper mill in European part of Russia shows that the algorithm can be effectively used to plan the work of one paper machine for several shifts or as an auxiliary tool when devising cutting plans for a group of paper machines.
The proposed algorithm provides an optimal solution with no more than 400 cutting plans, which corresponds to approximately 8 orders for rolls of the same diameter and density produced on one paper machine. That is, it can be used when planning production for no more than two days. To build planning systems for longer periods of time (week, month), it is necessary to develop special algorithms.
Keywords: cutting stock problem; optimization; pulp and paper industry; uniform production plan
pp. 35–43
For citation:
Voronov R. V., Shabaev A. I., Klimenko V. V. Genetic Algorithm for Linear Cutting Problem, Programmnaya Ingeneria, 2024, vol. 15, no. 1, pp. 35—43. DOI: 10.17587/prin.15.35-43 (in Russian).
References:
- Zak Y. A. Optimization of production planning and cutting of paper products, Control systems and machines, 2010, no. 5, pp. 82—93 (in Russian).
- Voronov R. V. Mathematical models and methods of automated planning systems for paper production: thesis. Petrozavod. state univ., 2004, 143 p. (in Russian).
- Urban A. R. Mathematical models and numerical methods in the software package for optimization of paper production planning: thesis. Petrozavod. state Univ., 2016, 110 p. (in Russian).
- Wagner B. J. A genetic algorithm solution for one-dimensional bundled stock cutting, European Journal of Operational Research, 1999, vol. 117, no. 2, pp. 368—381. DOI: 10.1016/S0377-2217(98)00244-6.
- Onwubolu G. C., Mutingi M. A genetic algorithm approach for the cutting stock problem, Journal of Intelligent Manufacturing, 2003, no. 14, pp. 209—218. DOI: 10.1023/A:1022955531018.
- Umetani S., Yagiura M., Ibaraki T. One-dimensional cutting stock problem to minimize the number of different patterns, European Journal of Operational Research, 2003, vol. 146, no. 2, pp. 388—402. DOI: 10.1016/s0377-2217(02)00239-4.
- Website of LLC 0 "Opti-Soft". Page Opti-Paper, available at: https://opti-soft.ru/opti/paper. (data of access 10.10.2023).
- Dancig J. B. Linear programming, its applications and generalizations, Moscow, Progress, 1966, pp. 28—33 (in Russian).
