• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Thèse de Doctorat
DOI
https://doi.org/10.11606/T.45.2004.tde-20210729-135851
Document
Auteur
Nom complet
Glauber Ferreira Cintra
Adresse Mail
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Paulo, 2003
Directeur
Titre en portugais
Algoritmos para problemas de corte de guilhotina bidimensional
Mots-clés en portugais
Problemas Combinatórios Clássicos
Resumé en portugais
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
Titre en anglais
not available
Resumé en anglais
not available
 
AVERTISSEMENT - Regarde ce document est soumise à votre acceptation des conditions d'utilisation suivantes:
Ce document est uniquement à des fins privées pour la recherche et l'enseignement. Reproduction à des fins commerciales est interdite. Cette droits couvrent l'ensemble des données sur ce document ainsi que son contenu. Toute utilisation ou de copie de ce document, en totalité ou en partie, doit inclure le nom de l'auteur.
Date de Publication
2021-07-29
 
AVERTISSEMENT: Apprenez ce que sont des œvres dérivées cliquant ici.
Tous droits de la thèse/dissertation appartiennent aux auteurs
CeTI-SC/STI
Bibliothèque Numérique de Thèses et Mémoires de l'USP. Copyright © 2001-2023. Tous droits réservés.