Contributions to the two-dimensional guillotine cutting stock problem

Detalhes bibliográficos
Ano de defesa: 2018
Autor(a) principal: Pessoa, Ronaldo Lage
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
Tipo de documento: Dissertação
Tipo de acesso: Acesso aberto
Idioma: eng
Instituição de defesa: Não Informado pela instituição
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: http://www.repositorio.ufc.br/handle/riufc/32792
Resumo: 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.