Cut and waste optimization algorithms | Construpedia
Navegación
Cut and waste optimization algorithms
Introduction
Guillotine cutting is the process of producing small rectangular shapes of fixed dimensions from a given large rectangular sheet, using guillotine cuts only. A guillotine cut (also called edge-to-edge cut) is a straight bisecting line that runs from one edge of an existing rectangle to the opposite edge, similar to what a guillotine does for paper.
Guillotine cutting is particularly common in the glass industry. Sheets of glass are marked on horizontal and vertical lines and then broken along these lines to obtain smaller panels.[1] The procedure is also useful for cutting steel plates, cutting sheets of wood for making furniture, and for cutting cardboard used in making boxes.[2].
There are several optimization problems related to guillotine cutting, such as maximizing the total area of the pieces produced or their total value; or also minimize the amount of waste (unused parts) of the large sheet, or the total number of sheets. They have been studied in discrete geometry, operations research and industrial engineering.[3].
A related but different problem is "guillotine partitioning").
Terminology and assumptions
The following terms and notations are often used in guillotine cutting literature.
Some problems accept additional input, as explained below. The goal is to cut some smaller rectangles from the rough rectangle that have the desired dimensions. The following assumptions are often made:[2].
Checking a given pattern
In the pattern checking problem, there is a cutting pattern given as a sequence of points (x,y), for i in 1,...,m, where (x,y) is the bottom left coordinate of rectangle i (there is a single rectangle of each target dimension). The goal is to decide if this pattern can be implemented using only guillotine cuts and, if so, find a sequence for such cuts.
An obvious necessary condition is that no two input rectangles overlap in both dimensions. [5] set a stronger condition, which is both necessary and sufficient. The input rectangles are arranged from left to right, so = ... = . There is a permutation on the indices such that, with this permutation, the rectangles would be ordered from bottom to top, that is, = ... = . Given four indices = and = , the set E(,,,) contains the indices of all rectangles whose lower left corner is in the rectangle [,] X [,]. A cutting pattern is a guillotine pattern if and only if, for all quaternas of indices = and = , at least one of the following conditions is met for E(,,,):.
Cut and waste optimization algorithms
Introduction
Guillotine cutting is the process of producing small rectangular shapes of fixed dimensions from a given large rectangular sheet, using guillotine cuts only. A guillotine cut (also called edge-to-edge cut) is a straight bisecting line that runs from one edge of an existing rectangle to the opposite edge, similar to what a guillotine does for paper.
Guillotine cutting is particularly common in the glass industry. Sheets of glass are marked on horizontal and vertical lines and then broken along these lines to obtain smaller panels.[1] The procedure is also useful for cutting steel plates, cutting sheets of wood for making furniture, and for cutting cardboard used in making boxes.[2].
There are several optimization problems related to guillotine cutting, such as maximizing the total area of the pieces produced or their total value; or also minimize the amount of waste (unused parts) of the large sheet, or the total number of sheets. They have been studied in discrete geometry, operations research and industrial engineering.[3].
A related but different problem is "guillotine partitioning").
Terminology and assumptions
The following terms and notations are often used in guillotine cutting literature.
Some problems accept additional input, as explained below. The goal is to cut some smaller rectangles from the rough rectangle that have the desired dimensions. The following assumptions are often made:[2].
Checking a given pattern
In the pattern checking problem, there is a cutting pattern given as a sequence of points (x,y), for i in 1,...,m, where (x,y) is the bottom left coordinate of rectangle (there is a single rectangle of each target dimension). The goal is to decide if this pattern can be implemented using only guillotine cuts and, if so, find a sequence for such cuts.
Ben Messaoud, Chengbin and Espinouse
x
x
p
y
y
i
i
j
j
i
i
j
j
x
x
y
y
i
i
j
j
i
i
j
j
Condition 2 implies that the rectangles in E(i,i,j,j) can be separated by a vertical cut (which goes between the two horizontal intervals). Condition 3 implies that the rectangles in E(i,i,j,j) can be separated by a horizontal cut. All the conditions together imply that if any set of adjacent rectangles contains more than one element, then they can be separated by some guillotine cutting.
This condition can be verified using the following algorithm:.
Finding a guillotine cut for a given pattern is done as follows:.
The sorting steps are done once and the merge step is done m-1 times. Therefore, the execution time of the entire algorithm is O(m).
When the algorithm returns "yes", it also produces a sequence of guillotine cuts; when it returns "no", it also produces specific subsets of rectangles that cannot be separated by guillotine cuts.
The necessary and sufficient condition can be used to present the guillotine strip cutting problem as a mixed integer linear program.[5] Their model has 3n/4 binary variables and 2n constraints, and is not considered useful in practice.
Finding an optimal cutting pattern
Contenido
Estas son variantes de los problemas bidimensionales de corte de material, empaquetado en contenedores") y empaquetado de rectángulos, donde los cortes están obligados a ser cortes con guillotina.[6].
Optimization algorithms
The special case where 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[10] devised a polynomial time algorithm to solve it.
However, when there are two or more types, all optimization problems related to guillotine cutting are NP-hard. Due to its practical importance, several exact algorithms and approximation algorithms have been devised.
guillotine separation
Guillotine separation is a related problem where the input is a collection of n convex shapes separated by pairs in the plane, and the objective is to separate them using a sequence of guillotine cuts. Obviously, it may not be possible to separate them all. Jorge Urrutia Galicia") posed the question of whether it is possible to separate a constant fraction of them,[18] that is, if there exists a constant c such that, in any collection of size n, there is a subset of size cn that is guillotine separable.
Pach and Tardos[19] showed that:.
Abed, Chalermsook, Correa, Karrenbauer, Pérez-Lantero, Soto and Wiese[20] demonstrated that:.
Khan and Pittu[21] demonstrated:
More variants
Some variants of the problem include:
References
[1] ↑
[2] ↑ a b c d Beasley, J. E. (1 de abril de 1985). «Algorithms for Unconstrained Two-Dimensional Guillotine Cutting». Journal of the Operational Research Society 36 (4): 297-306. ISSN 0160-5682. S2CID 58059319. doi:10.1057/jors.1985.51.: https://doi.org/10.1057/jors.1985.51
[4] ↑ a b c Clautiaux, François; Jouglet, Antoine; Moukrim, Aziz (17 de octubre de 2011). «A New Graph-Theoretical Model for the Guillotine-Cutting Problem». INFORMS Journal on Computing 25 (1): 72-86. ISSN 1091-9856. doi:10.1287/ijoc.1110.0478.: https://pubsonline.informs.org/doi/abs/10.1287/ijoc.1110.0478
[5] ↑ a b c Ben Messaoud, Said; Chu, Chengbin; Espinouse, Marie-Laure (16 de noviembre de 2008). «Characterization and modelling of guillotine constraints». European Journal of Operational Research (en inglés) 191 (1): 112-126. ISSN 0377-2217. doi:10.1016/j.ejor.2007.08.029.: http://www.sciencedirect.com/science/article/pii/S0377221707009083
[6] ↑ a b M. Hifi, R. M’Hallah and T. Saadi, Approximate and exact algorithms for the double-constrained two-dimensional guillotine cutting stock problem. Computational Optimization and Applications, Volume 42, Number 2 (2009), 303-326, doi 10.1007/s10589-007-9081-5.: https://dx.doi.org/10.1007/s10589-007-9081-5
[7] ↑ Carlier, Jacques; Clautiaux, François; Moukrim, Aziz (1 de agosto de 2007). «New reduction procedures and lower bounds for the two-dimensional bin packing problem with fixed orientation». Computers & Operations Research (en inglés) 34 (8): 2223-2250. ISSN 0305-0548. doi:10.1016/j.cor.2005.08.012.: http://www.sciencedirect.com/science/article/pii/S0305054805002765
[8] ↑ a b Russo, Mauro; Boccia, Maurizio; Sforza, Antonio; Sterle, Claudio (2020). «Constrained two-dimensional guillotine cutting problem: upper-bound review and categorization». International Transactions in Operational Research (en inglés) 27 (2): 794-834. ISSN 1475-3995. S2CID 195551953. doi:10.1111/itor.12687.: https://onlinelibrary.wiley.com/doi/abs/10.1111/itor.12687
[10] ↑ Tarnowski, A. G.; Terno, J.; Scheithauer, G. (1 de noviembre de 1994). «A Polynomial Time Algorithm For The Guillotine Pallet Loading Problem». INFOR: Information Systems and Operational Research 32 (4): 275-287. ISSN 0315-5986. doi:10.1080/03155986.1994.11732257.: https://doi.org/10.1080/03155986.1994.11732257
[11] ↑ Gilmore, P. C.; Gomory, R. E. (1 de febrero de 1965). «Multistage Cutting Stock Problems of Two and More Dimensions». Operations Research 13 (1): 94-120. ISSN 0030-364X. doi:10.1287/opre.13.1.94.: https://pubsonline.informs.org/doi/abs/10.1287/opre.13.1.94
[12] ↑ Gilmore, P. C.; Gomory, R. E. (1 de diciembre de 1966). «The Theory and Computation of Knapsack Functions». Operations Research 14 (6): 1045-1074. ISSN 0030-364X. doi:10.1287/opre.14.6.1045.: https://pubsonline.informs.org/doi/abs/10.1287/opre.14.6.1045
[13] ↑ a b Herz, J. C. (September 1972). «Recursive Computational Procedure for Two-dimensional Stock Cutting». IBM Journal of Research and Development 16 (5): 462-469. ISSN 0018-8646. doi:10.1147/rd.165.0462.: https://ieeexplore.ieee.org/document/5391454
[14] ↑ Christofides, Nicos; Whitlock, Charles (1 de febrero de 1977). «An Algorithm for Two-Dimensional Cutting Problems». Operations Research 25 (1): 30-44. ISSN 0030-364X. doi:10.1287/opre.25.1.30.: https://pubsonline.informs.org/doi/abs/10.1287/opre.25.1.30
[15] ↑ O. B. G. Masden (1980), IMSOR working paper, Technical university of Denmark, Lyngby.
[16] ↑ Wang, P. Y. (1 de junio de 1983). «Two Algorithms for Constrained Two-Dimensional Cutting Stock Problems». Operations Research 31 (3): 573-586. ISSN 0030-364X. doi:10.1287/opre.31.3.573.: https://pubsonline.informs.org/doi/abs/10.1287/opre.31.3.573
[17] ↑ Michael L. McHale, Roshan P. Shah Cutting the Guillotine Down to Size. PC AI magazine, Volume 13, Number 1 Jan/Feb 99. http://www.amzi.com/articles/papercutter.htm.: http://www.amzi.com/articles/papercutter.htm
[18] ↑ Problem presented at ACCOTA '96, Combinatorial and Computational Aspects of Optimization Topology and Algebra, Taxco, Mexico 1996.
[19] ↑ Pach, J.; Tardos, G. (2000). «Cutting Glass». Discrete and Computational Geometry (en inglés) 24 (2–3): 481-496. ISSN 0179-5376. S2CID 1737527. doi:10.1007/s004540010050.: https://elibrary.ru/item.asp?id=986870
[20] ↑ Abed, Fidaa; Chalermsook, Parinya; Correa, José; Karrenbauer, Andreas; Pérez-Lantero, Pablo; Soto, José A.; Wiese, Andreas (2015). On Guillotine Cutting Sequences. pp. 1-19. ISBN 978-3-939897-89-7. doi:10.4230/LIPIcs.APPROX-RANDOM.2015.1.: https://kops.uni-konstanz.de/handle/123456789/33469
[21] ↑ a b Khan, Arindam; Pittu, Madhusudhan Reddy (2020). «On Guillotine Separability of Squares and Rectangles». En Byrka, Jaros\law; Meka, Raghu, eds. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs) (Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum für Informatik) 176: 47:1-47:22. ISBN 978-3-95977-164-1. doi:10.4230/LIPIcs.APPROX/RANDOM.2020.47.: https://drops.dagstuhl.de/opus/volltexte/2020/12650
[22] ↑ Martin, Mateus; Oliveira, José Fernando; Silva, Elsa; Morabito, Reinaldo; Munari, Pedro (8 de noviembre de 2020). «Three-dimensional guillotine cutting problems with constrained patterns: MILP formulations and a bottom-up algorithm». Expert Systems with Applications (en inglés) 168: 114257. ISSN 0957-4174. S2CID 228839108. doi:10.1016/j.eswa.2020.114257.: http://www.sciencedirect.com/science/article/pii/S0957417420309726
[23] ↑ Baazaoui, M.; Hanafi, S.; Kamoun, H. (1 de noviembre de 2014). «A Mathematical formulation and a lower bound for the three-dimensional multiple-bin-size bin packing problem (MBSBPP): A Tunisian industrial case». 2014 International Conference on Control, Decision and Information Technologies (CoDIT). pp. 219-224. ISBN 978-1-4799-6773-5. S2CID 18598442. doi:10.1109/CoDIT.2014.6996896.: https://ieeexplore.ieee.org/document/6996896
[24] ↑ Martin, Mateus; Hokama, Pedro H. D. B.; Morabito, Reinaldo; Munari, Pedro (2 de mayo de 2020). «The constrained two-dimensional guillotine cutting problem with defects: an ILP formulation, a Benders decomposition and a CP-based algorithm». International Journal of Production Research 58 (9): 2712-2729. ISSN 0020-7543. S2CID 197434029. doi:10.1080/00207543.2019.1630773.: https://doi.org/10.1080/00207543.2019.1630773
i
An obvious necessary condition is that no two input rectangles overlap in both dimensions. Ben Messaoud, Chengbin and Espinouse[5] set a stronger condition, which is both necessary and sufficient. The input rectangles are arranged from left to right, so x = ... = x. There is a permutation p on the indices such that, with this permutation, the rectangles would be ordered from bottom to top, that is, y = ... = y. Given four indices i = i and j = j, the set E(i,i,j,j) contains the indices of all rectangles whose lower left corner is in the rectangle [x,x] X [y,y]. A cutting pattern is a guillotine pattern if and only if, for all quaternas of indices i = i and j = j, at least one of the following conditions is met for E(i,i,j,j):.
Condition 2 implies that the rectangles in E(i,i,j,j) can be separated by a vertical cut (which goes between the two horizontal intervals). Condition 3 implies that the rectangles in E(i,i,j,j) can be separated by a horizontal cut. All the conditions together imply that if any set of adjacent rectangles contains more than one element, then they can be separated by some guillotine cutting.
This condition can be verified using the following algorithm:.
Finding a guillotine cut for a given pattern is done as follows:.
The sorting steps are done once and the merge step is done m-1 times. Therefore, the execution time of the entire algorithm is O(m).
When the algorithm returns "yes", it also produces a sequence of guillotine cuts; when it returns "no", it also produces specific subsets of rectangles that cannot be separated by guillotine cuts.
The necessary and sufficient condition can be used to present the guillotine strip cutting problem as a mixed integer linear program.[5] Their model has 3n/4 binary variables and 2n constraints, and is not considered useful in practice.
Finding an optimal cutting pattern
Contenido
Estas son variantes de los problemas bidimensionales de corte de material, empaquetado en contenedores") y empaquetado de rectángulos, donde los cortes están obligados a ser cortes con guillotina.[6].
Optimization algorithms
The special case where 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[10] devised a polynomial time algorithm to solve it.
However, when there are two or more types, all optimization problems related to guillotine cutting are NP-hard. Due to its practical importance, several exact algorithms and approximation algorithms have been devised.
guillotine separation
Guillotine separation is a related problem where the input is a collection of n convex shapes separated by pairs in the plane, and the objective is to separate them using a sequence of guillotine cuts. Obviously, it may not be possible to separate them all. Jorge Urrutia Galicia") posed the question of whether it is possible to separate a constant fraction of them,[18] that is, if there exists a constant c such that, in any collection of size n, there is a subset of size cn that is guillotine separable.
Pach and Tardos[19] showed that:.
Abed, Chalermsook, Correa, Karrenbauer, Pérez-Lantero, Soto and Wiese[20] demonstrated that:.
Khan and Pittu[21] demonstrated:
More variants
Some variants of the problem include:
References
[1] ↑
[2] ↑ a b c d Beasley, J. E. (1 de abril de 1985). «Algorithms for Unconstrained Two-Dimensional Guillotine Cutting». Journal of the Operational Research Society 36 (4): 297-306. ISSN 0160-5682. S2CID 58059319. doi:10.1057/jors.1985.51.: https://doi.org/10.1057/jors.1985.51
[4] ↑ a b c Clautiaux, François; Jouglet, Antoine; Moukrim, Aziz (17 de octubre de 2011). «A New Graph-Theoretical Model for the Guillotine-Cutting Problem». INFORMS Journal on Computing 25 (1): 72-86. ISSN 1091-9856. doi:10.1287/ijoc.1110.0478.: https://pubsonline.informs.org/doi/abs/10.1287/ijoc.1110.0478
[5] ↑ a b c Ben Messaoud, Said; Chu, Chengbin; Espinouse, Marie-Laure (16 de noviembre de 2008). «Characterization and modelling of guillotine constraints». European Journal of Operational Research (en inglés) 191 (1): 112-126. ISSN 0377-2217. doi:10.1016/j.ejor.2007.08.029.: http://www.sciencedirect.com/science/article/pii/S0377221707009083
[6] ↑ a b M. Hifi, R. M’Hallah and T. Saadi, Approximate and exact algorithms for the double-constrained two-dimensional guillotine cutting stock problem. Computational Optimization and Applications, Volume 42, Number 2 (2009), 303-326, doi 10.1007/s10589-007-9081-5.: https://dx.doi.org/10.1007/s10589-007-9081-5
[7] ↑ Carlier, Jacques; Clautiaux, François; Moukrim, Aziz (1 de agosto de 2007). «New reduction procedures and lower bounds for the two-dimensional bin packing problem with fixed orientation». Computers & Operations Research (en inglés) 34 (8): 2223-2250. ISSN 0305-0548. doi:10.1016/j.cor.2005.08.012.: http://www.sciencedirect.com/science/article/pii/S0305054805002765
[8] ↑ a b Russo, Mauro; Boccia, Maurizio; Sforza, Antonio; Sterle, Claudio (2020). «Constrained two-dimensional guillotine cutting problem: upper-bound review and categorization». International Transactions in Operational Research (en inglés) 27 (2): 794-834. ISSN 1475-3995. S2CID 195551953. doi:10.1111/itor.12687.: https://onlinelibrary.wiley.com/doi/abs/10.1111/itor.12687
[10] ↑ Tarnowski, A. G.; Terno, J.; Scheithauer, G. (1 de noviembre de 1994). «A Polynomial Time Algorithm For The Guillotine Pallet Loading Problem». INFOR: Information Systems and Operational Research 32 (4): 275-287. ISSN 0315-5986. doi:10.1080/03155986.1994.11732257.: https://doi.org/10.1080/03155986.1994.11732257
[11] ↑ Gilmore, P. C.; Gomory, R. E. (1 de febrero de 1965). «Multistage Cutting Stock Problems of Two and More Dimensions». Operations Research 13 (1): 94-120. ISSN 0030-364X. doi:10.1287/opre.13.1.94.: https://pubsonline.informs.org/doi/abs/10.1287/opre.13.1.94
[12] ↑ Gilmore, P. C.; Gomory, R. E. (1 de diciembre de 1966). «The Theory and Computation of Knapsack Functions». Operations Research 14 (6): 1045-1074. ISSN 0030-364X. doi:10.1287/opre.14.6.1045.: https://pubsonline.informs.org/doi/abs/10.1287/opre.14.6.1045
[13] ↑ a b Herz, J. C. (September 1972). «Recursive Computational Procedure for Two-dimensional Stock Cutting». IBM Journal of Research and Development 16 (5): 462-469. ISSN 0018-8646. doi:10.1147/rd.165.0462.: https://ieeexplore.ieee.org/document/5391454
[14] ↑ Christofides, Nicos; Whitlock, Charles (1 de febrero de 1977). «An Algorithm for Two-Dimensional Cutting Problems». Operations Research 25 (1): 30-44. ISSN 0030-364X. doi:10.1287/opre.25.1.30.: https://pubsonline.informs.org/doi/abs/10.1287/opre.25.1.30
[15] ↑ O. B. G. Masden (1980), IMSOR working paper, Technical university of Denmark, Lyngby.
[16] ↑ Wang, P. Y. (1 de junio de 1983). «Two Algorithms for Constrained Two-Dimensional Cutting Stock Problems». Operations Research 31 (3): 573-586. ISSN 0030-364X. doi:10.1287/opre.31.3.573.: https://pubsonline.informs.org/doi/abs/10.1287/opre.31.3.573
[17] ↑ Michael L. McHale, Roshan P. Shah Cutting the Guillotine Down to Size. PC AI magazine, Volume 13, Number 1 Jan/Feb 99. http://www.amzi.com/articles/papercutter.htm.: http://www.amzi.com/articles/papercutter.htm
[18] ↑ Problem presented at ACCOTA '96, Combinatorial and Computational Aspects of Optimization Topology and Algebra, Taxco, Mexico 1996.
[19] ↑ Pach, J.; Tardos, G. (2000). «Cutting Glass». Discrete and Computational Geometry (en inglés) 24 (2–3): 481-496. ISSN 0179-5376. S2CID 1737527. doi:10.1007/s004540010050.: https://elibrary.ru/item.asp?id=986870
[20] ↑ Abed, Fidaa; Chalermsook, Parinya; Correa, José; Karrenbauer, Andreas; Pérez-Lantero, Pablo; Soto, José A.; Wiese, Andreas (2015). On Guillotine Cutting Sequences. pp. 1-19. ISBN 978-3-939897-89-7. doi:10.4230/LIPIcs.APPROX-RANDOM.2015.1.: https://kops.uni-konstanz.de/handle/123456789/33469
[21] ↑ a b Khan, Arindam; Pittu, Madhusudhan Reddy (2020). «On Guillotine Separability of Squares and Rectangles». En Byrka, Jaros\law; Meka, Raghu, eds. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs) (Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum für Informatik) 176: 47:1-47:22. ISBN 978-3-95977-164-1. doi:10.4230/LIPIcs.APPROX/RANDOM.2020.47.: https://drops.dagstuhl.de/opus/volltexte/2020/12650
[22] ↑ Martin, Mateus; Oliveira, José Fernando; Silva, Elsa; Morabito, Reinaldo; Munari, Pedro (8 de noviembre de 2020). «Three-dimensional guillotine cutting problems with constrained patterns: MILP formulations and a bottom-up algorithm». Expert Systems with Applications (en inglés) 168: 114257. ISSN 0957-4174. S2CID 228839108. doi:10.1016/j.eswa.2020.114257.: http://www.sciencedirect.com/science/article/pii/S0957417420309726
[23] ↑ Baazaoui, M.; Hanafi, S.; Kamoun, H. (1 de noviembre de 2014). «A Mathematical formulation and a lower bound for the three-dimensional multiple-bin-size bin packing problem (MBSBPP): A Tunisian industrial case». 2014 International Conference on Control, Decision and Information Technologies (CoDIT). pp. 219-224. ISBN 978-1-4799-6773-5. S2CID 18598442. doi:10.1109/CoDIT.2014.6996896.: https://ieeexplore.ieee.org/document/6996896
[24] ↑ Martin, Mateus; Hokama, Pedro H. D. B.; Morabito, Reinaldo; Munari, Pedro (2 de mayo de 2020). «The constrained two-dimensional guillotine cutting problem with defects: an ILP formulation, a Benders decomposition and a CP-based algorithm». International Journal of Production Research 58 (9): 2712-2729. ISSN 0020-7543. S2CID 197434029. doi:10.1080/00207543.2019.1630773.: https://doi.org/10.1080/00207543.2019.1630773