skip to main content
Idioma:

Algoritmos para problemas de corte de guilhotina bidimensional

Cintra, Glauber Ferreira

Biblioteca Digital de Teses e Dissertações da USP; Universidade de São Paulo; Instituto de Matemática e Estatística 2004-04-02

Acesso online. A biblioteca também possui exemplares impressos.

  • Título:
    Algoritmos para problemas de corte de guilhotina bidimensional
  • Autor: Cintra, Glauber Ferreira
  • Orientador: Wakabayashi, Yoshiko
  • Assuntos: Problemas Combinatórios Clássicos
  • Notas: Tese (Doutorado)
  • Descrição: Muitas indústrias têm como desafio encontrar soluções mais econômicas possíveis para o problema de cortar objetos grandes visando a produção de objetos menores de dimensões especificadas, ou o problema de empacotar uma coleção de objetos pequenos dentro de objetos grandes. Tais problemas são chamados de problemas de corte de empacotamento e são, em geral, NP-difíceis. Em muitas aplicações, os objetos grandes (placas) e os objetos pequenos (itens) têm apenas duas dimensões relevantes e possuem a forma retangular. Além disso, é comum a restrição de que os cortes em cada objeto sejam de guilhotina, isto é, estes devem ser paralelos a um de seus lados e se estender desde um lado do objeto até o lado oposto, problemas desse tipo são chamados de problemas de corte de guilhotina bidimensional. Algoritmos para tais tipos de problemas constituem o tema central desta tese. Investigamos o problema de corte de estoque bidimensional com demandas (PCED IND. 2) (um caso mais geral em que os cortes não precisam ser de guilhotina) e introduzimos o conceito de padrões semi-homogêneos. Fazendo uso de tais padrões, desenvolvemos um algoritmo polinomial cuja razão de aproximação absoluta é 4, e mostramos que esta razão é justa. Ainda utilizando padrões semi-homogêneos, desenvolvemos um algoritmo que resolve uma variante do 'PCED IND. 2' na qual as placas e os itens são quadrados. Provamos que este algoritmo tem razão de aproximação assintótica entre 2,4166 e 2,6875. Até onde sabemos, estes são os primeiros algoritmos de aproximaçãopropostos para tais problemas. Desenvolvemos ainda um algoritmo para o problema de corte de estoque bidimensional binário com rotações e provamos que esse algoritmo possui razão de aproximação assintótica não maior que 4. Utilizando a fórmula de recorrência proposta por Beasley e os pontos de discretização definidos por Herz, desenvolvemos um algoritmo pseudo-polinomial para o problema de corte de ) de guilhotina bidimensional com valor (PCGV IND. 2) baseado em programação dinâmica. Chamamos tal algoritmo de 'PCGV IND. 2 PD'. Este algoritmo também resolve uma variante do 'PCGV IND. 2' na qual os itens podem sofrer rotações ortogonais. Apresentamos também um algoritmo baseado em enumeração explicíta e em programação dinâmica para calcular os pontos de discretização. Mostramos que, se os itens não são muito pequenos em relação ao tamanho das placas, então o algoritmo 'PCGV IND. 2 P-D' requer tempo polinomial. Implementamos o 'PCGV IND. 2 PD' e resolvemos todas as instâncias do 'PCGV IND. 2' encontradas na OR-LIBRARY. Destacamos que para uma destas instâncias (mencionada há duas décadas) não se conhecia uma solução ótima
  • DOI: 10.11606/T.45.2004.tde-20210729-135851
  • Editor: Biblioteca Digital de Teses e Dissertações da USP; Universidade de São Paulo; Instituto de Matemática e Estatística
  • Data de criação/publicação: 2004-04-02
  • Formato: Adobe PDF
  • Idioma: Português
Links
Voltar para lista de resultados
Resultado  1

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.