Тіктөртбұрыш кесу процесі және оның оптимизациясы

Process of producing small rectangular items of fixed dimensions

Guillotine cutting is the process of producing small rectangular items of fixed dimensions from a given large rectangular sheet, using only guillotine cuts. A guillotine cut (also called an edge to edge cut) is a straight bisecting line going from one edge of an existing rectangle to the opposite edge, similarly to a paper guillotine. Guillotine cutting is particularly common in the glass industry. Glass sheets are scored along horizontal and vertical lines, and then broken along these lines to obtain smaller panels. It is also useful for cutting steel plates, cutting of wood sheets to make furniture, and cutting of cardboard into boxes. There are various optimization problems related to guillotine cutting, such as: maximize the total area of the produced pieces, or their total value; minimize the amount of waste (unused parts) of the large sheet, or the total number of sheets. They have been studied in combinatorial geometry, operations research and industrial engineering. A related but different problem is guillotine partition. In that problem, the dimensions of the small rectangles are not fixed in advance. The challenge comes from the fact that the original sheet might not be rectangular it can be any rectilinear polygon. In particular, it might contain holes (representing defects in the raw material). The optimization goal is usually to minimize the number of small rectangles, or minimize the total length of the cuts.

The special case in which there is only one type (i. e., all target rectangles are identical and in the same orientation) is called the guillotine pallet loading problem. Tarnowski, Terno and Scheithauer present a polynomial time algorithm for solving it. However, when there are two or more types, all optimization problems related to guillotine cutting are NP hard. Due to its practical importance, various exact algorithms and approximation algorithms have been devised. Gilmore and Gomory presented a dynamic programming recursion for both staged and unstaged guillotine cutting. However, it was later shown presented tree search procedures for unstaged guillotine cutting. Masden and Wang presented heuristic algorithms. Hiffi, M'Hallah and Saadi propose an algorithm for the doubly constrained guillotine cutting problem. It is a bottom up branch and bound algorithm using best first search. Clautiaux, Jouglet and Moukrim propose an exact algorithm for the decision problem. Their algorithm uses a compact representation of guillotine cutting pattern classes, using a directed graph that they call the guillotine graph. Each arc in this graph is colored in one of two colors: "horizontal" or "vertical". Each monochromatic directed cycle in this graph corresponds to a build. By repeatedly contracting monochromatic cycles, one can recover a recursive build sequence that represents a cutting pattern class. Every guillotine graph contains between m and 2m 2 arcs. A special kind of guillotine graphs called normal guillotine graphs have the interesting property of containing a unique Hamiltonian circuit. Sorting the vertices according to this circuit makes the graph a well sorted normal guillotine graph; there is a one to one correspondence between such graphs and cutting pattern classes. They then solve the optimization problem using constraint programming on the space of well sorted normal guillotine graphs. Russo, Boccia, Sforza and Sterle review over 90 papers dealing with unstaged constrained guillotine cutting (with quantity upper bounds), both weighted and unweighted. There are two main approaches for exact solutions: dynamic programming and tree search (branch and bound). The tree search approaches are further categorized as bottom up (starting with single rectangles and using builds to construct the entire sheet) or top down. In all approaches, it is important to find good lower and upper bounds in order to trim the search space efficiently. These bounds often come from solutions to related variants, e. g. unconstrained, staged, and non guillotine variants. Abou Msabah, Slimane, and Ahmed Riadh Baba Ali. "A new guillotine placement heuristic combined with an improved genetic algorithm for the orthogonal cutting stock problem." 2011 IEEE International Conference on Industrial Engineering and Engineering Management. IEEE, 2011. Abou Msabah, Slimane, Ahmed Riadh Baba Ali, and Basma Sager. "A Controlled Stability Genetic Algorithm With the New BLF2G Guillotine Placement Heuristic for the Orthogonal Cutting Stock Problem." International Journal of Cognitive Informatics and Natural Intelligence (IJCINI) 13, no. 4 (2019): 91 111.

McHale and Shah wrote a Prolog program implementing an anytime algorithm: it generates approximately optimal solutions in a given amount of time, and then improves it if the user allows more time. The program was used by a specialty paper producer, and has cut the time required for sheet layout while reducing waste.