L. V. KANTOROVICH AND CUTTING-PACKING PROBLEMS: NEW APPROACHES TO COMBINATORIAL PROBLEMS OF LINEAR CUTTING AND RECTANGULAR PACKING

摘要

In the middle of the XXth century, L. V. Kantorovich and V. A. Zalgaller suggested to solve problems of economical use of material at the cutting stage with the help of linear programming. This led to the continuous relaxation of the problem of rational cutting and, in fact, settled the problem in mass production. The paper briefly describes ways of realization of the method for the one-dimensional cutting. The problem is extended to the integer case, which is typical for any cutting problem. For two-dimensional cutting-packing problems, the block structure technology was developed. This technology reduces to solving a certain special planning problem of one-dimensional cutting that can be solved by linear programming using simple heuristics. We present some computing circuits and results of numerical experiments with wasteless packings. The comparison with other algorithms confirms the efficiency of the block method.