Mostrar el registro sencillo del ítem
Problemas de corte guilhotinado e restritos: formulações matemáticas e métodos de solução
dc.contributor.author | Martin, Mateus Pereira | |
dc.date.accessioned | 2020-01-17T19:19:34Z | |
dc.date.available | 2020-01-17T19:19:34Z | |
dc.date.issued | 2019-12-12 | |
dc.identifier.citation | MARTIN, Mateus Pereira. Problemas de corte guilhotinado e restritos: formulações matemáticas e métodos de solução. 2019. Tese (Doutorado em Engenharia de Produção) – Universidade Federal de São Carlos, São Carlos, 2019. Disponível em: https://repositorio.ufscar.br/handle/ufscar/12154. | * |
dc.identifier.uri | https://repositorio.ufscar.br/handle/ufscar/12154 | |
dc.description.abstract | We address the Constrained Guillotine Cutting Problems (CGCP) in this doctoral thesis. The CGCP consist of producing items from objects using guillotine cuts, i.e., cuts that divide the rectangular materials into two rectangular sub-objects without restricting the number of guillotine stages, and with a limitation over the maximum number of copies per item type to be cut from the object. New linear mathematical formulations are proposed for the Constrained Two-dimensional Guillotine Cutting Problem (C2GCP). The first proposed formulation is based on object discretization, which is also extended to deal with 2-staged and 1-group patterns, and a Benders decomposition algorithm is developed from it. Two other formulations are proposed to the C2GCP, based on the concept of successive combination of copies of item types and sub-patterns, i.e., the bottom-up approach; from the proposed additional constraints, these models strictly deal with d-staged cutting patterns, where d is a positive integer scalar. Two extensions of the C2GCP are also addressed in this thesis. The first extension is the Constrained Two-dimensional Guillotine Cutting Problem with Defects (C2GCP-D). The linear model and the Benders decomposition algorithm, both based on object discretization, are extended to deal with this variant, and then a new solution method based on Constraint Programming is developed. The second extension is the Constrained Three-Dimensional Guillotine Cutting Problem (C3GCP), which is addressed by models and by a tree-search algorithm. All these proposed approaches are evaluated through computational experiments, using instances of the literature or randomly generated ones, and compared to another approaches in the literature. Despite the applicability of these problems, the literature took more than three decades to present mathematical formulations to the CGCP. Therefore, this thesis contributes to new formulation paradigms for the CGCP and effective methods to solve them, which are competitive with those known in the literature. | eng |
dc.description.sponsorship | Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) | por |
dc.description.sponsorship | Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) | por |
dc.description.sponsorship | Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) | por |
dc.language.iso | por | por |
dc.publisher | Universidade Federal de São Carlos | por |
dc.rights | Attribution-NonCommercial-NoDerivs 3.0 Brazil | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/3.0/br/ | * |
dc.subject | Corte guilhotinado | por |
dc.subject | Corte 2-estágios | por |
dc.subject | Corte 1-grupo | por |
dc.subject | Defeitos | por |
dc.subject | Corte tridimensional | por |
dc.subject | Programação Linear Inteira Mista | por |
dc.subject | Otimização combinatória | por |
dc.subject | Guillotine cutting | eng |
dc.subject | 2-staged cutting | eng |
dc.subject | 1-group cutting | eng |
dc.subject | Defects | eng |
dc.subject | Three-dimensional cutting | eng |
dc.subject | Mixed Integer Linear Programming | eng |
dc.subject | Combinatorial optimization | eng |
dc.title | Problemas de corte guilhotinado e restritos: formulações matemáticas e métodos de solução | por |
dc.title.alternative | Constrained guillotine cutting problems: mathematical formulations and solution methods | eng |
dc.type | Tese | por |
dc.contributor.advisor1 | Morabito Neto, Reinaldo | |
dc.contributor.advisor1Lattes | http://lattes.cnpq.br/4194801952934254 | por |
dc.contributor.advisor-co1 | Munari Junior, Pedro Augusto | |
dc.contributor.advisor-co1Lattes | http://lattes.cnpq.br/1328868140869976 | por |
dc.description.resumo | Esta tese de doutorado tem como objeto de pesquisa os Problemas de Corte Guilhotinado e Restritos (PCGR). Os PCGR consistem em produzir itens a partir de um objeto, ao se utilizar operações de corte guilhotinado, i.e., operações que repartam os materiais retangulares em dois sub-objetos retangulares adjacentes sem restrição sobre o número de estágios guilhotinados, e que atendam à quantidade máxima de vezes que os itens podem ser cortados a partir do objeto. Novas formulações matemáticas lineares são propostas ao Problema de Corte Bidimensional Guilhotinado e Restrito (PCBGR). A primeira formulação proposta se baseia na discretização do objeto, que também foi estendida para lidar com padrões 2-estágios e 1-grupo, assim como um algoritmo de decomposição de Benders foi desenvolvido a partir dela. Outras duas formulações são propostas ao PCBGR, baseadas no conceito de combinação sucessiva de cópias de tipos de itens e subpadrões, i.e., na abordagem bottom-up; a partir de restrições adicionais propostas, esses modelos estritamente lidam com padrões de corte d-estágios, sendo d um escalar inteiro positivo. Duas extensões do PCBGR são abordadas. A primeira delas é o Problema de Corte Bidimensional Guilhotinado e Restrito de Objeto com Defeitos (PCBGR_D). O modelo linear e algoritmo de Benders, ambos baseados na discretização do objeto, são estendidos para lidar com essa variante, e então um novo método de solução baseado em Programação por Restrições é desenvolvido. A segunda extensão é o Problema de Corte Tridimensional Guilhotinado e Restrito (PCTGR), que é abordado por meio de modelos e por um algoritmo combinatório. As abordagens propostas são avaliadas por experimentos computacionais, usando instâncias da literatura ou geradas aleatoriamente, e comparadas a outras abordagens conhecidas da literatura. Apesar da aplicabilidade desses problemas, a literatura levou mais de três décadas para apresentar formulações matemáticas aos PCGR. Essa tese contribui com novos paradigmas de formulação aos PCGR e métodos efetivos para resolvê-los, que são competitivos com os conhecidos da literatura. | por |
dc.publisher.initials | UFSCar | por |
dc.publisher.program | Programa de Pós-Graduação em Engenharia de Produção - PPGEP | por |
dc.subject.cnpq | ENGENHARIAS::ENGENHARIA DE PRODUCAO::GERENCIA DE PRODUCAO | por |
dc.subject.cnpq | ENGENHARIAS::ENGENHARIA DE PRODUCAO::PESQUISA OPERACIONAL | por |
dc.description.sponsorshipId | FAPESP: 2016/08039-1 | por |
dc.description.sponsorshipId | CNPq: 200745/2018-2 | por |
dc.publisher.address | Câmpus São Carlos | por |
dc.contributor.authorlattes | http://lattes.cnpq.br/9814295914139504 | por |