Applying dynamic programming to assembly line balancing and sequencing problems

Abstract

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).

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).