Repositório Digital

A- A A+

Applying dynamic programming to assembly line balancing and sequencing problems

.

Applying dynamic programming to assembly line balancing and sequencing problems

Mostrar registro completo

Estatísticas

Título Applying dynamic programming to assembly line balancing and sequencing problems
Autor Daudt, César Garcia
Orientador Ritt, Marcus Rolf Peter
Data 2013
Nível Graduação
Instituição Universidade Federal do Rio Grande do Sul. Instituto de Informática. Curso de Ciência da Computação: Ênfase em Ciência da Computação: Bacharelado.
Assunto Algorítmo
Otimizacao combinatoria
[en] Assembly line problems
[en] BPP-P
[en] Combinatorial optimization
[en] Dynamic programming
[en] Operations research
[en] SALBP-1
[en] Sequencing problems
Resumo Este trabalho apresenta dois algoritmos de Programação Dinâmica que tratam os problemas Simple Assembly Line Balancing Problem (SALBP) e Bin-Packing Problem with Precedence Constraints (BPP-P). Enquanto o primeiro problema já foi longamente explorado, o segundo só foi estudado anteriormente em um único artigo. Para o BPP-P, nossa abordagem é a primeira a utilizar Programação Dinâmica e nós fornecemos uma nova solução ótima que, até a publicação de nosso algoritmo, era desconhecida (duas instâncias do conjunto de testes consagrado pela literatura ainda continuam sem uma resposta ótima). Para ambas variações, nossas implementações conseguem lidar com instâncias pequenas comumente utilizadas na literatura. Em média, tratamos tais instâncias com tempos de execução que vão de milissegundos até poucos minutos. Também apresentamos, para cada algoritmo explicado, uma forma de reduzir o espaço de busca: uma implementação da regra de corte Jackson Dominance Rule e uma aproximação do princípio de utilizar estações preenchidas de maneira ótima proposto por Jackson. Os impactos dessas otimizações são discutidos, medidos e comparados com os algoritmos do estado-da-arte. Observações sobre trabalhos importantes (incluindo trabalhos antigos e algortimos que são o estado-da-arte) e pesquisas são feitas com o intuito de direcionar ao leitor da área mais informações sobre problemas de balanceamento de linhas de montagem (em especial, as variantes SALBP e BPP-P).
Abstract This work presents two dynamic programing algorithms to treat simple assembly line balancing problem (SALBP) and bin-packing problem with precedence constraints (BPPP). While the former has been explored for many years, the latter has been studied only recently. For BPP-P, our approach is the first to use dynamic programming and we provide one new optimal answer that was unknown until our algorithm was proposed (from the instances used in the literature, 2 still remain unsolved). For both variants, our implementations are able to deal with the small instances commonly used in the literature. In average, we treat these instances with execution times from miliseconds to few minutes. We also present, for each algorithm explained, one way to reduce the search space: an implementation of Jackson Dominance Rule and our approximation of Jackson Maximally Loaded station principle. The impact of these optimizations is discussed, measured and compared to the state of the art algorithms. Remarks are made about important works (from the past and current state of the art algorithms) and surveys in order to make the interested reader able to find further information regarding assembly line balancing problems (specially SALBP and BPP-P variants).
Tipo Trabalho de conclusão de graduação
URI http://hdl.handle.net/10183/77290
Arquivos Descrição Formato
000896205.pdf (302.8Kb) Texto completo Adobe PDF Visualizar/abrir

Este item está licenciado na Creative Commons License

Este item aparece na(s) seguinte(s) coleção(ões)


Mostrar registro completo

Percorrer



  • O autor é titular dos direitos autorais dos documentos disponíveis neste repositório e é vedada, nos termos da lei, a comercialização de qualquer espécie sem sua autorização prévia.
    Projeto gráfico elaborado pelo Caixola - Clube de Criação Fabico/UFRGS Powered by DSpace software, Version 1.8.1.