Métodos heurísticos para a programação em flow shop permutacional com tempos de setup separados dos tempos de processamento e independentes da seqüência de tarefas / Heuristic methods for the permutation flow shop scheduling problem with separated, non-batch, and sequence-independent setup times

AUTOR(ES)

Thays Josyane Perassoli Boiko

DATA DE PUBLICAÇÃO

2008

RESUMO

Este trabalho dedica-se ao problema de programação em flow shop permutacional com tempos de setup separados dos tempos de processamento e independentes da seqüência de execução das tarefas com o objetivo de minimizar a duração total da programação (Makespan). Por intermédio de investigações realizadas sobre as características estruturais do problema de programação e sua solução, uma propriedade deste problema é apresentada. Esta propriedade, denominada "Propriedade LBY", considerando quaisquer duas tarefas adjacentes Ju e Jv (Ju imediatamente precede Jv) independentemente de suas posições na seqüência de tarefas, fornece, um limitante inferior do tempo de espera para a tarefa Jv entre o fim do seu processamento na máquina Mk e o início do seu processamento na máquina seguinte. Dois novos métodos heurísticos são desenvolvidos, com base na propriedade apresentada e no procedimento de inserção de tarefas dos conhecidos métodos N&M e NEH: um construtivo, denominado BMc; e, um melhorativo, denominado BMm. Os métodos heurísticos propostos são comparados com os métodos heurísticos melhorativos de Cao; Bedworth (1992) e Rajendran; Ziegler (1997), através de um grande número de problemas gerados aleatoriamente. Os tempos de processamento são distribuídos no intervalo [1, 99] e os tempos de setup nos intervalos de [1, 49], [1, 99], [51, 149] e [101, 199]. Os métodos são avaliados quanto à porcentagem de sucesso em obter a melhor solução, ao desvio relativo médio e o tempo médio de computação. Os resultados da experimentação computacional mostram a qualidade do método construtivo BMc e a melhor performance do método melhorativo BMm. Estes resultados são apresentados e discutidos.

ASSUNTO(S)

production scheduling flow shop permutacional programação da produção setup times permutation flow shop tempos de setup

Documentos Relacionados

• Heuristic for flow shop sequencing with separated and sequence independent setup times
• Flexible flow line with setup times: heuristic methods
• Uma propriedade estrutural do problema de programação da produção flow shop permutacional com tempos de setup
• Análise da flutuação do gargalo em flow shop permutacional com tempos de setup assimétricos e dependentes da seqüência
• Métodos heurísticos construtivos para redução do estoque em processo em ambientes de produção flow shop híbridos com tempos de setup dependentes da sequência