A MIP-CP based approach for two- and three-dimensional cutting problems with staged guillotine cuts |
| |
Authors: | do Nascimento Oliviana Xavier de Queiroz Thiago Alves Junqueira Leonardo |
| |
Affiliation: | 1.Institute of Mathematics and Technology, Federal University of Goiás, Campus Catal?o, Catal?o, GO, 75704-020, Brazil ;2.Department of Production Engineering, Polytechnic School, University of S?o Paulo, S?o Paulo, SP, 05508-010, Brazil ; |
| |
Abstract: | This work presents guillotine constraints for two- and three-dimensional cutting problems. These problems look for a subset of rectangular items of maximum value that can be cut from a single rectangular container. Guillotine constraints seek to ensure that items are arranged in such a way that cuts from one edge of the container to the opposite edge completely separate them. In particular, we consider the possibility of 2, 3, and 4 cutting stages in a predefined sequence. These constraints are considered within a two-level iterative approach that combines the resolution of integer linear programming and constraint programming models. Experiments with instances of the literature are carried out, and the results show that the proposed approach can solve in less than 500 s approximately 60% and 50% of the instances for the two- and three-dimensional cases, respectively. For the two-dimensional case, in comparison with the recent literature, it was possible to improve the upper bound for 16% of the instances. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|