Este trabalho aborda o problema de programação da produção em um flexible flow line com tempos de setup. De acordo com a literatura, este ambiente pode ser considerado como um caso especial do Flow Shop com múltiplas máquinas, onde as tarefas podem saltar estágios. Neste estudo, foram analisados dois problemas: o primeiro, com tempos de setup independentes da sequência, e o segundo, com setup dependente da sequência de tarefas. Além disso, o setup das máquinas para as tarefas pode ser antecipado ou não. No primeiro caso, as máquinas de um estágio podem ser preparadas para o processamento de uma tarefa antes do seu término no estágio anterior. Se o setup não pode ser antecipado, a tarefa deve esperar o seu término no estágio de produção anterior. Este ambiente produtivo pode ser encontrado em um vasto número de indústrias tais como química, eletrônica, automotiva e têxtil. A medida de desempenho dos problemas é a duração total da programação (makespan). Este é um critério apropriado para sistemas de produção com grandes cargas de trabalho e em que a utilização dos recursos produtivos em longo prazo deve ser otimizada. O exame da literatura mostrou que há poucos estudos abordando a programação em flexible flow line. Considerando este aspecto, este trabalho apresenta heurísticas construtivas originais para a obtenção de programações apropriadas ao problema mencionado. Uma extensiva experimentação computacional foi executada para avaliar o desempenho relativo das heurísticas. Os resultados experimentais foram analisados e discutidos. / This work addresses the job scheduling on a flexible flow line with separate setup times. According to the literature, this scheduling problem can be considered as a special case of the Flow Shop with multiple machines, where the jobs may skip stages. Two modeled problems have been studied. In the first scheduling problem the setup times are sequence independent, and in the second one these times are sequence dependent. Moreover, the machine setup task can be either anticipatory or non-anticipatory. In the first case, a k-stage machine may be prepared for a job processing before its completion on the k-1 production stage. Otherwise, the setup task must wait for the job completion on the former production stage. This production environment can be found in a number of industries such as chemicals, electronics, automotive, and textiles. The performance measure of the production schedules is the makespan, that is, the total time to complete the schedule. This is an appropriate performance criterion for production systems with large workloads, and where the utilization of productive resources in the long term should be optimized. The literature examination has shown that there is a small number of studies dealing with flexible flow line scheduling. Having this in mind, this work introduces original constructive heuristics in order to obtain suitable schedules for the aforementioned scheduling problem. An extensive computational experience has been carried out in order to evaluate the relative performance of the heuristics. Experimental results are discussed.

Este trabalho aborda o problema de programação da produção em um flexible flow line com tempos de setup. De acordo com a literatura, este ambiente pode ser considerado como um caso especial do Flow Shop com múltiplas máquinas, onde as tarefas podem saltar estágios. Neste estudo, foram analisados dois problemas: o primeiro, com tempos de setup independentes da sequência, e o segundo, com setup dependente da sequência de tarefas. Além disso, o setup das máquinas para as tarefas pode ser antecipado ou não. No primeiro caso, as máquinas de um estágio podem ser preparadas para o processamento de uma tarefa antes do seu término no estágio anterior. Se o setup não pode ser antecipado, a tarefa deve esperar o seu término no estágio de produção anterior. Este ambiente produtivo pode ser encontrado em um vasto número de indústrias tais como química, eletrônica, automotiva e têxtil. A medida de desempenho dos problemas é a duração total da programação (makespan). Este é um critério apropriado para sistemas de produção com grandes cargas de trabalho e em que a utilização dos recursos produtivos em longo prazo deve ser otimizada. O exame da literatura mostrou que há poucos estudos abordando a programação em flexible flow line. Considerando este aspecto, este trabalho apresenta heurísticas construtivas originais para a obtenção de programações apropriadas ao problema mencionado. Uma extensiva experimentação computacional foi executada para avaliar o desempenho relativo das heurísticas. Os resultados experimentais foram analisados e discutidos. / This work addresses the job scheduling on a flexible flow line with separate setup times. According to the literature, this scheduling problem can be considered as a special case of the Flow Shop with multiple machines, where the jobs may skip stages. Two modeled problems have been studied. In the first scheduling problem the setup times are sequence independent, and in the second one these times are sequence dependent. Moreover, the machine setup task can be either anticipatory or non-anticipatory. In the first case, a k-stage machine may be prepared for a job processing before its completion on the k-1 production stage. Otherwise, the setup task must wait for the job completion on the former production stage. This production environment can be found in a number of industries such as chemicals, electronics, automotive, and textiles. The performance measure of the production schedules is the makespan, that is, the total time to complete the schedule. This is an appropriate performance criterion for production systems with large workloads, and where the utilization of productive resources in the long term should be optimized. The literature examination has shown that there is a small number of studies dealing with flexible flow line scheduling. Having this in mind, this work introduces original constructive heuristics in order to obtain suitable schedules for the aforementioned scheduling problem. An extensive computational experience has been carried out in order to evaluate the relative performance of the heuristics. Experimental results are discussed.