Use este identificador para citar ou linkar para este item: http://repositorio.ufc.br/handle/riufc/32792
Tipo: Dissertação
Título: Contributions to the two-dimensional guillotine cutting stock problem
Título em inglês: Contributions to the two-dimensional guillotine cutting stock problem
Autor(es): Pessoa, Ronaldo Lage
Orientador: Prata, Bruno de Athayde
Coorientador: Rodrigues, Carlos Diego
Palavras-chave: Problemas de corte e empacotamento;Itens idênticos;Setup;Corte em estágios;Programação matemática
Data do documento: 2018
Citação: PESSOA, Ronaldo Lage. Contributions to the two-dimensional guillotine cutting stock problem. 2018. 57 f. Dissertação (Mestrado em Modelagem e Métodos Quantitativos)- Universidade Federal do Ceará, Fortaleza, 2018.
Resumo: No presente trabalho são apresentadas duas novas variantes do problema de corte guilhotinado bi-dimensional. São propostas formulações matemáticas e métodos de solução para lidar com os problemas apresentados. Primeiramente, é apresentado o problema de corte guilhotinado bi-dimensional de dois-estágios no qual os itens são idênticos, as placas têm tamanhos diferentes e o objetivo é determinar o tamanho ótimo dos itens idênticos. Dois procedimentos de solução são apresentados para resolver o caso no qual a orientação dos itens é fixa e o caso no qual a rotação ortogonal dos itens é permitida. Os dois procedimentos lidam com o problema resolvendo iterativamente um problema da mochila para cada tamanho possível de item e retornando a melhor solução encontrada. Experimentos numéricos são conduzidos para avaliar a escalabilidade das abordagens. Por último, é apresentado o problema de corte bi-dimensional guilhotinado de k-estágios no qual o custo de setup associado aos estágios de corte é considerado relevante. Uma formulação matemática com O(n²pN) variáveis e O(npN) restrições é apresentada, onde, n, p e k são o número de itens, placas e estágios, respectivamente. Experimentos computacionais foram conduzidos em vinte instâncias de pequena escala geradas aleatoriamente para avaliar a qualidade da abordagem.
Abstract: In this work we present two new variants of the two-dimensional guillotine cutting stock problem. We propose mathematical formulations and solution methods to deal with such problems. Firstly, we deal with the two-stage two-dimensional guillotine cutting stock problem in which items are identical, bins are different in size and the objective is to determine the optimal size of the identical items. Two solution procedures are presented to solve the case in which the orientation of the items is fixed and the case in which orthogonal rotation of items is allowed. The two procedures deal with the problem iteratively solving a knapsack problem for each possible item size and returning the best solution found. Numerical experiments are conducted on two- hundred randomly generated instances to evaluate the scalability of the approaches. Lastly, we deal with the k-stage two-dimensional guillotine cutting stock problem in which setup cost associated with stages of cut are considered relevant. A mathematical programming formulation with O(n²pk) variables and O(npk) constraints is present, in which n, p and k are the number of items, bins and stages, respectively. Numerical experiments are conducted on twenty small-scale randomly generated instances to evaluate the quality of the approach.
URI: http://www.repositorio.ufc.br/handle/riufc/32792
Aparece nas coleções:DEMA - Dissertações defendidas na UFC

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
2018_dis_rlpessoa.pdf732,25 kBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.