O presente trabalho aborda o ambiente de produção conhecido como flowshop híbrido. Devido a crescente complexidade dos sistemas de produção, este ambiente é frequentemente encontrado em situações reais de manufatura. No caso estudado existem estágios em série e em cada estágio existe um número de máquinas idênticas em paralelo. Os tempos de processamento em cada estágio são dependentes da tarefa, já a rota através do sistema é a mesma para todas as tarefas. O objetivo é minimizar o atraso total, ou seja, a soma do atraso de todas as tarefas. Um modelo de programação linear inteira mista é apresentado para este problema e, dada a sua complexidade, ele é abordado através de uma meta-heurística relativamente nova e que, conforme revisão da literatura, nunca foi aplicada a este problema. Conhecida por BRKGA (Biased Random-Key Genetic Algorithm), este método codifica as soluções de maneira a obter um melhor desempenho em comparação com algoritmos genéticos tradicionais. Com o objetivo de avaliar a melhor estratégia, são propostas diversas versões de BRKGA para o problema considerado. Estas versões buscam explorar características das melhores heurísticas construtivas da literatura, dentre estas: ordens direta e inversa de programação das tarefas dentro do ambiente produtivo, identificação do estágio gargalo e diferenciação da programação do gargalo dos demais estágios. Experimentos computacionais foram realizados com 432 problemas teste de grande porte. Os métodos apresentados são comparados entre si e os resultados mostraram que uma versão do BRKGA se destaca frente às demais, visto que ela atingiu o melhor resultado em 61% dos problemas. Destaca-se que o método de melhor desempenho da literatura obteve a melhor solução em apenas 15% dos problemas. Devido às dimensões dos problemas teste da literatura, não foi possível encontrar suas soluções ótimas. Deste modo, este trabalho propõe um novo limitante inferior para o mínimo atraso total. Além disso, 576 novos problemas teste de menores dimensões são propostos e seus resultados ótimos são utilizados para aprofundar as comparações. Os resultados deste experimento indicaram que o BRKGA proposto apresentou um bom desempenho visto que, na média, seus resultados estão apenas a 2,4% dos resultados ótimos. / This work addresses a scheduling problem in hybrid flowshops. Due to the increasing complexity of production systems, this production environment is often encountered in real manufacturing situations. In hybrid flowshops, there are stages in series and, in each stage, a number of similar parallel machines. Processing times in each stage are dependent on the job, and the route through the system is the same for all jobs. The objective is to minimize the total tardiness, that is, the sum of all jobs tardiness. A mixed integer linear programming model is presented for the problem considered. Given its complexity, this problem is approached by a relatively new meta-heuristic, known as BRKGA (Biased Random-Key Genetic Algorithm). A literature review showed that BRKGA had never been applied to this problem. The BRKGA codes solutions in order to obtain a better performance compared with traditional genetic algorithms. Several versions of BRKGA were developed in order to evaluate the best strategy to solve the problem considered. These versions aim to exploit features of the best constructive heuristic from the literature, among them: scheduling jobs in direct and inverse order within the production environment, identification of the bottleneck stage and distinction of the bottleneck stage schedule from the others. Computational experiments were conducted with 432 large instances. The methods were compared and the results showed that one of these versions stood out against the others. This version achieved better results in 61% of instances, while the best heuristic from the literature achieved 15%. Due to the size of these instances, optimal solutions were not found. Therefore, this work develops a new lower bound for the minimum total tardiness. Additionally, in order to find optimal results, a set of 576 new instances is proposed. This experiment indicated that the BRKGA proposed performed well since, on average, their results are only 2.4% away from the optimal results.

O presente trabalho aborda o ambiente de produção conhecido como flowshop híbrido. Devido a crescente complexidade dos sistemas de produção, este ambiente é frequentemente encontrado em situações reais de manufatura. No caso estudado existem estágios em série e em cada estágio existe um número de máquinas idênticas em paralelo. Os tempos de processamento em cada estágio são dependentes da tarefa, já a rota através do sistema é a mesma para todas as tarefas. O objetivo é minimizar o atraso total, ou seja, a soma do atraso de todas as tarefas. Um modelo de programação linear inteira mista é apresentado para este problema e, dada a sua complexidade, ele é abordado através de uma meta-heurística relativamente nova e que, conforme revisão da literatura, nunca foi aplicada a este problema. Conhecida por BRKGA (Biased Random-Key Genetic Algorithm), este método codifica as soluções de maneira a obter um melhor desempenho em comparação com algoritmos genéticos tradicionais. Com o objetivo de avaliar a melhor estratégia, são propostas diversas versões de BRKGA para o problema considerado. Estas versões buscam explorar características das melhores heurísticas construtivas da literatura, dentre estas: ordens direta e inversa de programação das tarefas dentro do ambiente produtivo, identificação do estágio gargalo e diferenciação da programação do gargalo dos demais estágios. Experimentos computacionais foram realizados com 432 problemas teste de grande porte. Os métodos apresentados são comparados entre si e os resultados mostraram que uma versão do BRKGA se destaca frente às demais, visto que ela atingiu o melhor resultado em 61% dos problemas. Destaca-se que o método de melhor desempenho da literatura obteve a melhor solução em apenas 15% dos problemas. Devido às dimensões dos problemas teste da literatura, não foi possível encontrar suas soluções ótimas. Deste modo, este trabalho propõe um novo limitante inferior para o mínimo atraso total. Além disso, 576 novos problemas teste de menores dimensões são propostos e seus resultados ótimos são utilizados para aprofundar as comparações. Os resultados deste experimento indicaram que o BRKGA proposto apresentou um bom desempenho visto que, na média, seus resultados estão apenas a 2,4% dos resultados ótimos. / This work addresses a scheduling problem in hybrid flowshops. Due to the increasing complexity of production systems, this production environment is often encountered in real manufacturing situations. In hybrid flowshops, there are stages in series and, in each stage, a number of similar parallel machines. Processing times in each stage are dependent on the job, and the route through the system is the same for all jobs. The objective is to minimize the total tardiness, that is, the sum of all jobs tardiness. A mixed integer linear programming model is presented for the problem considered. Given its complexity, this problem is approached by a relatively new meta-heuristic, known as BRKGA (Biased Random-Key Genetic Algorithm). A literature review showed that BRKGA had never been applied to this problem. The BRKGA codes solutions in order to obtain a better performance compared with traditional genetic algorithms. Several versions of BRKGA were developed in order to evaluate the best strategy to solve the problem considered. These versions aim to exploit features of the best constructive heuristic from the literature, among them: scheduling jobs in direct and inverse order within the production environment, identification of the bottleneck stage and distinction of the bottleneck stage schedule from the others. Computational experiments were conducted with 432 large instances. The methods were compared and the results showed that one of these versions stood out against the others. This version achieved better results in 61% of instances, while the best heuristic from the literature achieved 15%. Due to the size of these instances, optimal solutions were not found. Therefore, this work develops a new lower bound for the minimum total tardiness. Additionally, in order to find optimal results, a set of 576 new instances is proposed. This experiment indicated that the BRKGA proposed performed well since, on average, their results are only 2.4% away from the optimal results.

Em um contexto industrial, a programação da produção tem como objetivo alocar recursos para operações de forma a aumentar a eficiência operacional do processo de fabricação. Esta programação pode ser modelada na forma de problemas de sequenciamento de tarefas, que são resolvidos visando minimizar um determinado critério de desempenho. A aplicação de métodos exatos nestes problemas possibilita encontrar a solução ótima, tanto para aplicação direta como para a validação de métodos heurísticos e metaheurísticas. Entretanto, a literatura mostra que os métodos exatos, tanto a resolução do problema pela modelagem em programação linear-inteira mista como o branch-and-bound, têm sua aplicação restrita à problemas de menores tamanhos. O objetivo deste trabalho é propor novas formulações de limitantes inferiores para a aplicação do branch-and-bound em problemas de flowshop permutacional visando aumentar sua eficiência e aplicabilidade. Os limitantes propostos são avaliados em problemas de flowshop permutacional com tempos de setup dependente da sequência, tendo como critérios de desempenho o tempo de fluxo total e o atraso total. A avaliação da aplicabilidade de cada limitante é feita através do número de nós explorados e o tempo computacional gasto pelo branch-and-bound para resolver problemas de diversos tamanhos. / In an industrial context, production sequencing aims at allocating resources for job processing while increasing manufacturing efficiency. This task can be modelled in the form of scheduling problems, which are solved by minimizing a pre-determined performance criterion. The use of exact methods allows the optimal solution to be found, which can be applied directly in the manufacturing shop or used to validate heuristic and metaheuristic methods. However, the literature shows that MILP and branch-and-bound, both exact methods, are restrained to small-sized scheduling problems. The aim of this project is to propose new lower bound formulations to be used in the branch-and-bound method for permutational flowshop probems, in order to extend its efficiency and applicability. The proposed bounds are tested in permutational flowshop problems with sequence dependent setup times, and using as performance criteria the total flow time and the total tardiness. The evaluation of each lower bounds applicability is done considering the number of explored nodes and the required computational time for the branch-and-bound to solve problem instances of different sizes.

O ambiente de produção abordado neste trabalho é o Job Shop Flexível (JSF), uma generalização do Job Shop (JS). O problema de programação de tarefas, ou jobs, no ambiente JS é classificado por Garey; Johnson e Sethi (1976) como NP-Difícil e o JSF é, no mínimo, tão difícil quanto o JS. O JSF é composto por um conjunto de jobs, cada qual constituído por operações. Cada operação deve ser processada individualmente, sem interrupção, em uma única máquina de um subconjunto de máquinas habilitadas. O principal critério de desempenho considerado é a minimização dos atrasos dos jobs. São apresentados modelos de Programação Linear Inteira Mista (PLIM) para minimizar o atraso total e o instante de término da última operação, o makespan. São propostas novas regras de prioridade dos jobs, além de adaptações de regras da literatura. Tais regras são utilizadas por heurísticas construtivas e são aliadas a estratégias cujo objetivo é explorar características específicas do JSF. Visando aprimorar as soluções inicialmente obtidas, são propostas buscas locais e outros mecanismos de melhoria utilizados no desenvolvimento de três meta-heurísticas de diferentes categorias. Essas meta-heurísticas são: Iterated Local Search (ILS), classificada como meta-heurística de trajetória; Greedy Randomized Adaptive Search (GRASP), meta-heurística construtiva; e Artificial Bee Colony (ABC), meta-heurística populacional recentemente proposta. Esses métodos foram selecionados por alcançarem bons resultados para diversos problemas de otimização da literatura. São realizados experimentos computacionais com 600 instâncias do JSF, permitindo comparações entre os métodos de resolução. Os resultados mostram que explorar as características do problema permite que uma das regras de prioridade propostas supere a melhor regra da literatura em 81% das instâncias. As meta-heurísticas ILS, GRASP e ABC chegam a conseguir mais de 31% de melhoria sobre as soluções iniciais e a obter atrasos, em média, somente 2,24% superiores aos das soluções ótimas. Também são propostas modificações nas meta-heurísticas que permitem obter melhorias ainda mais expressivas sem aumento do tempo de execução. Adicionalmente é estudada uma versão do JSF com operações de Montagem e Desmontagem (JSFMD) e os experimentos realizados com um conjunto de 150 instâncias também indicam o bom desempenho dos métodos desenvolvidos. / The production environment addressed herein is the Flexible Job Shop (FJS), a generalization of the Job Shop (JS). In the JS environment, the jobs scheduling problem is classified by Garey; Johnson and Sethi (1976) as NP-Hard and the FJS is at least as difficult as the JS. FJS is composed of a set of jobs, each consisting of operations. Each operation must be processed individually, without interruption, in a single machine of a subset of enabled machines. The main performance criterion is minimizing the jobs tardiness. Mixed Integer Linear Programming (MILP) models are presented. These models minimize the total tardiness and the completion time of the last operation, makespan. New priority rules of jobs are proposed, as well as adaptations of rules from the literature. These rules are used by constructive heuristics and are combined with strategies aimed at exploiting specific characteristics of FSJ. In order to improve the solutions initially obtained, local searches and other improvement mechanisms are proposed and used in the development of metaheuristics of three different categories. These metaheuristics are: Iterated Local Search (ILS), classified as trajectory metaheuristic; Greedy Randomized Adaptive Search (GRASP), constructive metaheuristic, and Artificial Bee Colony (ABC), recently proposed population metaheuristic. These methods were selected owing to their good results for various optimization problems in the literature. Computational experiments using 600 FJS instances are carried out to allow comparisons between the resolution methods. The results show that exploiting the characteristics of the problem allows one of the proposed priority rules to exceed the best literature rule in about 81% of instances. Metaheuristics ILS, GRASP and ABC achieve more than 31% improvement over the initial solutions and obtain an average tardiness only 2.24% higher than the optimal solutions. Modifications in metaheuristics are proposed to obtain even more significant improvements without increased execution time. Additionally, a version called Disassembly and Assembly FSJ (DAFJS) is studied and the experiments performed with a set of 150 instances also indicate good performance of the methods developed.

O ambiente de produção abordado neste trabalho é o Job Shop Flexível (JSF), uma generalização do Job Shop (JS). O problema de programação de tarefas, ou jobs, no ambiente JS é classificado por Garey; Johnson e Sethi (1976) como NP-Difícil e o JSF é, no mínimo, tão difícil quanto o JS. O JSF é composto por um conjunto de jobs, cada qual constituído por operações. Cada operação deve ser processada individualmente, sem interrupção, em uma única máquina de um subconjunto de máquinas habilitadas. O principal critério de desempenho considerado é a minimização dos atrasos dos jobs. São apresentados modelos de Programação Linear Inteira Mista (PLIM) para minimizar o atraso total e o instante de término da última operação, o makespan. São propostas novas regras de prioridade dos jobs, além de adaptações de regras da literatura. Tais regras são utilizadas por heurísticas construtivas e são aliadas a estratégias cujo objetivo é explorar características específicas do JSF. Visando aprimorar as soluções inicialmente obtidas, são propostas buscas locais e outros mecanismos de melhoria utilizados no desenvolvimento de três meta-heurísticas de diferentes categorias. Essas meta-heurísticas são: Iterated Local Search (ILS), classificada como meta-heurística de trajetória; Greedy Randomized Adaptive Search (GRASP), meta-heurística construtiva; e Artificial Bee Colony (ABC), meta-heurística populacional recentemente proposta. Esses métodos foram selecionados por alcançarem bons resultados para diversos problemas de otimização da literatura. São realizados experimentos computacionais com 600 instâncias do JSF, permitindo comparações entre os métodos de resolução. Os resultados mostram que explorar as características do problema permite que uma das regras de prioridade propostas supere a melhor regra da literatura em 81% das instâncias. As meta-heurísticas ILS, GRASP e ABC chegam a conseguir mais de 31% de melhoria sobre as soluções iniciais e a obter atrasos, em média, somente 2,24% superiores aos das soluções ótimas. Também são propostas modificações nas meta-heurísticas que permitem obter melhorias ainda mais expressivas sem aumento do tempo de execução. Adicionalmente é estudada uma versão do JSF com operações de Montagem e Desmontagem (JSFMD) e os experimentos realizados com um conjunto de 150 instâncias também indicam o bom desempenho dos métodos desenvolvidos. / The production environment addressed herein is the Flexible Job Shop (FJS), a generalization of the Job Shop (JS). In the JS environment, the jobs scheduling problem is classified by Garey; Johnson and Sethi (1976) as NP-Hard and the FJS is at least as difficult as the JS. FJS is composed of a set of jobs, each consisting of operations. Each operation must be processed individually, without interruption, in a single machine of a subset of enabled machines. The main performance criterion is minimizing the jobs tardiness. Mixed Integer Linear Programming (MILP) models are presented. These models minimize the total tardiness and the completion time of the last operation, makespan. New priority rules of jobs are proposed, as well as adaptations of rules from the literature. These rules are used by constructive heuristics and are combined with strategies aimed at exploiting specific characteristics of FSJ. In order to improve the solutions initially obtained, local searches and other improvement mechanisms are proposed and used in the development of metaheuristics of three different categories. These metaheuristics are: Iterated Local Search (ILS), classified as trajectory metaheuristic; Greedy Randomized Adaptive Search (GRASP), constructive metaheuristic, and Artificial Bee Colony (ABC), recently proposed population metaheuristic. These methods were selected owing to their good results for various optimization problems in the literature. Computational experiments using 600 FJS instances are carried out to allow comparisons between the resolution methods. The results show that exploiting the characteristics of the problem allows one of the proposed priority rules to exceed the best literature rule in about 81% of instances. Metaheuristics ILS, GRASP and ABC achieve more than 31% improvement over the initial solutions and obtain an average tardiness only 2.24% higher than the optimal solutions. Modifications in metaheuristics are proposed to obtain even more significant improvements without increased execution time. Additionally, a version called Disassembly and Assembly FSJ (DAFJS) is studied and the experiments performed with a set of 150 instances also indicate good performance of the methods developed.