A MIP-CP based approach for two- and three-dimensional cutting problems with staged guillotine cuts
Autor: | Thiago Alves de Queiroz, Oliviana Xavier do Nascimento, Leonardo Junqueira |
---|---|
Rok vydání: | 2019 |
Předmět: |
Mathematical optimization
Sequence 021103 operations research Computer science 0211 other engineering and technologies General Decision Sciences 02 engineering and technology Management Science and Operations Research Resolution (logic) Edge (geometry) OTIMIZAÇÃO COMBINATÓRIA Container (abstract data type) Theory of computation Constraint programming Integer programming |
Zdroj: | Repositório Institucional da USP (Biblioteca Digital da Produção Intelectual) Universidade de São Paulo (USP) instacron:USP |
ISSN: | 1572-9338 0254-5330 |
Popis: | 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. |
Databáze: | OpenAIRE |
Externí odkaz: |