Algoritmos híbridos para problemas de corte unidimensional (1998)
- Authors:
- Autor USP: CINTRA, GLAUBER FERREIRA - IME
- Unidade: IME
- Sigla do Departamento: MAP
- DOI: 10.11606/D.45.1998.tde-20210729-021137
- Assunto: PROBLEMAS COMBINATÓRIOS CLÁSSICOS
- Language: Português
- Abstract: Nesta dissertação apresentamos uma visão abrangente dos problemas de corte e empacotamento, analisando suas principais características, a partir das quais introduzimos a classificação proposta por Dickhoff. Discutimos brevemente as principais estratégias utilizandas na resolução destes problemas, citando algumas referências para o leitor interessado neste tópico. Investigamos o problema de corte de estoque unidimensional, formulando-o como um problema de programação linear inteira, e propomos um algoritmo híbrido, baseado no método de geração de colunas e num algoritmo exato. Tal algoritmo exato é adequado para resolver instâncias pequenas do problemade corte unidimensional quando se conhece previamente um limitante inferior para o valor da solução inteira ótima. Mostramos ainda que o algoritmo híbrido proposto encontra uma solução inteira cujo valor objetivo difere do valor objetivo ótimo de no máximo 1, se a conjectura MIRUP (Modified Integer Round-Up Property) for verdadeira. Variações são Propostas no algoritmo híbrido de modo a diminuir o tempo gasto na resolução dos problemas. Adaptamos ainda o algoritmo híbrido para o problema de corte unidimensional no qual a quantidade de itens distintos nos padrões é limitada por uma constante.Os resultados obtidos na resolução de um expressivo número de instâncias práticas e instâncias geradas aleatoriamente são analisados, indicando um desempenho bastante satisfatório do algoritmo híbrido e suas variações
- Imprenta:
- Data da defesa: 27.07.1998
- Status:
- Artigo publicado em periódico de acesso aberto (Gold Open Access)
- Versão do Documento:
- Versão publicada (Published version)
- Acessar versão aberta:
-
ABNT
CINTRA, Glauber Ferreira. Algoritmos híbridos para problemas de corte unidimensional. 1998. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 1998. Disponível em: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-021137/. Acesso em: 14 abr. 2026. -
APA
Cintra, G. F. (1998). Algoritmos híbridos para problemas de corte unidimensional (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-021137/ -
NLM
Cintra GF. Algoritmos híbridos para problemas de corte unidimensional [Internet]. 1998 ;[citado 2026 abr. 14 ] Available from: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-021137/ -
Vancouver
Cintra GF. Algoritmos híbridos para problemas de corte unidimensional [Internet]. 1998 ;[citado 2026 abr. 14 ] Available from: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-021137/
Informações sobre a disponibilidade de versões do artigo em acesso aberto coletadas automaticamente via oaDOI API (Unpaywall).
Por se tratar de integração com serviço externo, podem existir diferentes versões do trabalho (como preprints ou postprints), que podem diferir da versão publicada.
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
