Este trabalho aborda o problema de programação de tarefas, a partir de um caso específico, conhecido como Flow Shop com buffer zero. O problema consiste em programar n tarefas em m máquinas no ambiente Flow Shop permutacional. Com o aumento do nível de exigência dos clientes, pesquisas que buscam o atendimento das datas de entrega têm se tornado de extrema importância em ambientes de manufatura. Este trabalho analisa o problema de minimização do atraso total no ambiente Flow Shop onde não existe a possibilidade de armazenagem das tarefas entre estágios de produção sucessivos (buffer zero), tendo como consequência o bloqueio de máquinas. A Heurística Evolutiva Clustering Search foi proposta e analisada para a obtenção de soluções de altíssima qualidade para o problema. Finalmente, uma extensa experimentação computacional foi realizada. Quando comparado com o melhor método reportado na literatura, o método proposto apresentou qualidade superior. / This work deals with the Flow Shop scheduling problem. The objective is scheduling n jobs on m machines in the Permutation Flow Shop environment. With the increasing customer demand level, researches that aims the attendance of due dates have become extremely important in manufacturing process. This work studies the total tardiness minimization problem in the flow shop environment where there is no buffer storage between machines, resulting in the machine block. The Heuristic Evolutionary Clustering Search was proposed and analyzed to obtain high quality solutions to the problem. Finally, an extensive computational experiment was performed. When compared to the best method reported in the literature, the proposed method showed high quality.

Este trabalho aborda o problema de programação de tarefas, a partir de um caso específico, conhecido como Flow Shop com buffer zero. O problema consiste em programar n tarefas em m máquinas no ambiente Flow Shop permutacional. Com o aumento do nível de exigência dos clientes, pesquisas que buscam o atendimento das datas de entrega têm se tornado de extrema importância em ambientes de manufatura. Este trabalho analisa o problema de minimização do atraso total no ambiente Flow Shop onde não existe a possibilidade de armazenagem das tarefas entre estágios de produção sucessivos (buffer zero), tendo como consequência o bloqueio de máquinas. A Heurística Evolutiva Clustering Search foi proposta e analisada para a obtenção de soluções de altíssima qualidade para o problema. Finalmente, uma extensa experimentação computacional foi realizada. Quando comparado com o melhor método reportado na literatura, o método proposto apresentou qualidade superior. / This work deals with the Flow Shop scheduling problem. The objective is scheduling n jobs on m machines in the Permutation Flow Shop environment. With the increasing customer demand level, researches that aims the attendance of due dates have become extremely important in manufacturing process. This work studies the total tardiness minimization problem in the flow shop environment where there is no buffer storage between machines, resulting in the machine block. The Heuristic Evolutionary Clustering Search was proposed and analyzed to obtain high quality solutions to the problem. Finally, an extensive computational experiment was performed. When compared to the best method reported in the literature, the proposed method showed high quality.

O problema do sequenciamento da produção diz respeito à alocação das tarefas nas máquinas em um ambiente de fabricação, o qual vem sendo amplamente estudado. O sequenciamento pode variar em tamanho e complexidade dependendo do tipo de ambiente onde ele é aplicado, do número e tipos de restrições tecnológicas e da função objetivo do problema. A utilização de métodos de decisão para a solução de problemas de sequenciamento na indústria depende de modelos que sejam capazes de oferecer soluções para os problemas reais, que geralmente envolvem diversas restrições, os quais devem ser considerados simultaneamente. No presente trabalho o problema de sequenciamento da produção em ambientes flow shop permutacionais, com bloqueio com buffer zero, e com tempos de setup dependente da sequência e da máquina, com o objetivo de minimização do makespan é estudado, sendo este considerado um problema NP-Completo. O problema é pouco explorado na literatura. No presente trabalho é apresentado um procedimento de cálculo para o makespan e três métodos de solução para o problema: quatro limitantes inferiores para o procedimento Branch-and-Bound; quatro modelos MILP, sendo dois deles adaptados; e 28 modelos heurísticos construtivos adaptados para o problema. Os métodos desenvolvidos baseiam-se em propriedades matemáticas do problema que são apresentadas neste trabalho como limitante inferior e limitante superior. Dentre todos os modelos MILP, o modelo adaptado RBZBS1 obteve os melhores resultados para os problemas menores e o modelo desenvolvido TNZBS1 obteve os melhores desvios relativos médios do makespan para os problemas maiores, que não foram resolvidos dentro do limite de tempo computacional estipulado. O limitante inferior para o Branch-and-Bound LBTN2 foi melhor que os demais tanto no tempo computacional e no número de nós explorados como também no número de problemas não resolvidos e no desvio relativo médio do makespan. Foi realizado uma comparação entre o melhor modelo MILP e o melhor limitante inferior para o Branch-and-Bound, sendo que o último obteve melhores resultados para os problemas testados. Entre os métodos heurísticos adaptados, o PF foi o que obteve, de uma forma geral, os melhores resultados em todas as fases. / Production scheduling is defined as a problem of allocating jobs in machines in a production environment and it has been largely studied. The scheduling can vary in difficulty and complexity depending on the environment, the variety and types of technological restraints and the objective function of the problem. The use of decision making methods to solve scheduling problems in the industry needs models that are capable to solve real problems, that usually involve a big variety of restraints that have to be simultaneously studied. At the present work the scheduling problem in a permutational flow shop environment, considering blocking with zero buffer, and sequence and machine dependent setup times, with the objective of minimizing makespan is studied, which is considered a NP-Complete problem and little explored in literature. The work presents a calculation procedure for the makespan and three solution methods for the problem: four lower bounds for the Branch-and-Bound procedure; four MILP models, two of which are adapted; and 28 constructive heuristic methods adapted to the problem. The methods developed are based on mathematical properties of the problem that are presented in this work as a lower bound and an upper bound. Among all the MILP models, the adapted model RBZBS1 was the one to obtain the best results for the smaller problems, and the developed model TNZBS1 obtained the smallest mean relative deviation of the makespan for the bigger problems that were not solved within the specified computational time limit. The lower bound for the Branch-and-Bound LBTN2 obtained smaller computational times and number of explored nodes as well as the number of unsolved problems and the mean relative deviation for the makespan than all other lower bounds. Also, a comparison among the best MILP model and the best lower bound for the Branch-and-Bound was performed, being that the last obtained better results for the tested problems. Among the adapted heuristic methods, the PF heuristic was the one that obtained, in general, the better results in all phases.

O problema do sequenciamento da produção diz respeito à alocação das tarefas nas máquinas em um ambiente de fabricação, o qual vem sendo amplamente estudado. O sequenciamento pode variar em tamanho e complexidade dependendo do tipo de ambiente onde ele é aplicado, do número e tipos de restrições tecnológicas e da função objetivo do problema. A utilização de métodos de decisão para a solução de problemas de sequenciamento na indústria depende de modelos que sejam capazes de oferecer soluções para os problemas reais, que geralmente envolvem diversas restrições, os quais devem ser considerados simultaneamente. No presente trabalho o problema de sequenciamento da produção em ambientes flow shop permutacionais, com bloqueio com buffer zero, e com tempos de setup dependente da sequência e da máquina, com o objetivo de minimização do makespan é estudado, sendo este considerado um problema NP-Completo. O problema é pouco explorado na literatura. No presente trabalho é apresentado um procedimento de cálculo para o makespan e três métodos de solução para o problema: quatro limitantes inferiores para o procedimento Branch-and-Bound; quatro modelos MILP, sendo dois deles adaptados; e 28 modelos heurísticos construtivos adaptados para o problema. Os métodos desenvolvidos baseiam-se em propriedades matemáticas do problema que são apresentadas neste trabalho como limitante inferior e limitante superior. Dentre todos os modelos MILP, o modelo adaptado RBZBS1 obteve os melhores resultados para os problemas menores e o modelo desenvolvido TNZBS1 obteve os melhores desvios relativos médios do makespan para os problemas maiores, que não foram resolvidos dentro do limite de tempo computacional estipulado. O limitante inferior para o Branch-and-Bound LBTN2 foi melhor que os demais tanto no tempo computacional e no número de nós explorados como também no número de problemas não resolvidos e no desvio relativo médio do makespan. Foi realizado uma comparação entre o melhor modelo MILP e o melhor limitante inferior para o Branch-and-Bound, sendo que o último obteve melhores resultados para os problemas testados. Entre os métodos heurísticos adaptados, o PF foi o que obteve, de uma forma geral, os melhores resultados em todas as fases. / Production scheduling is defined as a problem of allocating jobs in machines in a production environment and it has been largely studied. The scheduling can vary in difficulty and complexity depending on the environment, the variety and types of technological restraints and the objective function of the problem. The use of decision making methods to solve scheduling problems in the industry needs models that are capable to solve real problems, that usually involve a big variety of restraints that have to be simultaneously studied. At the present work the scheduling problem in a permutational flow shop environment, considering blocking with zero buffer, and sequence and machine dependent setup times, with the objective of minimizing makespan is studied, which is considered a NP-Complete problem and little explored in literature. The work presents a calculation procedure for the makespan and three solution methods for the problem: four lower bounds for the Branch-and-Bound procedure; four MILP models, two of which are adapted; and 28 constructive heuristic methods adapted to the problem. The methods developed are based on mathematical properties of the problem that are presented in this work as a lower bound and an upper bound. Among all the MILP models, the adapted model RBZBS1 was the one to obtain the best results for the smaller problems, and the developed model TNZBS1 obtained the smallest mean relative deviation of the makespan for the bigger problems that were not solved within the specified computational time limit. The lower bound for the Branch-and-Bound LBTN2 obtained smaller computational times and number of explored nodes as well as the number of unsolved problems and the mean relative deviation for the makespan than all other lower bounds. Also, a comparison among the best MILP model and the best lower bound for the Branch-and-Bound was performed, being that the last obtained better results for the tested problems. Among the adapted heuristic methods, the PF heuristic was the one that obtained, in general, the better results in all phases.