Algoritmos para problemas de corte de guilhotina bidimensional (2004)
- Authors:
- Autor USP: CINTRA, GLAUBER FERREIRA - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Assunto: PROBLEMAS COMBINATÓRIOS CLÁSSICOS
- Language: Português
- Abstract: 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, estessã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
- Imprenta:
- Data da defesa: 02.04.2004
-
ABNT
CINTRA, Glauber Ferreira. Algoritmos para problemas de corte de guilhotina bidimensional. 2004. Tese (Doutorado) – Universidade de São Paulo, São Paulo, 2004. Disponível em: https://teses.usp.br/teses/disponiveis/45/45134/tde-20210729-135851/. Acesso em: 19 jul. 2024. -
APA
Cintra, G. F. (2004). Algoritmos para problemas de corte de guilhotina bidimensional (Tese (Doutorado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45134/tde-20210729-135851/ -
NLM
Cintra GF. Algoritmos para problemas de corte de guilhotina bidimensional [Internet]. 2004 ;[citado 2024 jul. 19 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-20210729-135851/ -
Vancouver
Cintra GF. Algoritmos para problemas de corte de guilhotina bidimensional [Internet]. 2004 ;[citado 2024 jul. 19 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-20210729-135851/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
