Uma propriedade estrutural do problema de programa??o da produ??o flow shop permutacional com tempos de setup

摘要

Neste artigo apresenta-se uma propriedade estrutural do problema de programa??o da produ??o flow shop permutacional com tempos de setup das máquinas separados dos tempos de processamento das tarefas, a qual foi identificada a partir de investiga??es que foram realizadas sobre as características do problema. Tal propriedade fornece um limitante superior do tempo de máquina parada entre a sua prepara??o e o início de execu??o das tarefas. Utilizando a propriedade, o problema original de programa??o da produ??o com minimiza??o do makespan pode ser resolvido de maneira heurística por meio de uma analogia com o problema assimétrico do caixeiro-viajante.