Metaheuristics for the flexible Flowshop problem with earliness and tardiness penalties

Este trabalho aborda o problema da programação de tarefas num sistema flowshop flexível, com o objetivo de minimizar penalidades por adiantamentos e atrasos em relação às datas de entrega das tarefas. Considera-se que todas as tarefas estão disponíveis para processamento em diferentes instantes, conforme suas datas de liberação (release time), além disso, existem tempos de preparação (setup times) dependentes da sequência e dos estágios. O problema abordado pertence ao ambiente de programação da produção JIT (just-in-time). Neste ambiente, o processamento de uma tarefa deve ser finalizado o mais próximo possível da sua data de entrega. Quando ocorre o adiantamento no processamento da tarefa, a produção é finalizada antes da data de entrega, devendo então ser armazenada, o que gera custos de estocagem. Já com o atraso na cadeia produtiva, ocorre o custo de atraso da tarefa e consequen te atraso das demais produções, ocasionando um efeito em cadeia, além da perda de confiança por parte do consumidor, fator este de custo inestimável, além do pagamento de multas contratuais, o que prejudica a imagem de uma empresa. Neste trabalho foi desenvolvido um modelo de programação inteira mista (PLIM) para o problema. Devido à complexidade computacional do problema, são utilizadas heurísticas e metaheurísticas para a obtenção de soluções aproximadas de boa qualidade. As metaheurísticas aplicadas são Iterated Local Search (ILS) e Algoritmo Genético (AG): Algoritmo Genético básico (AG-B) e Algoritmo Genético com busca local (AG-BL). O AG-BL é uma adaptação do algoritmo genético básico com busca local, aplicada para melhorar soluções determinadas pelos operadores genéticos. O modelo de PLIM, para problemas de pequeno porte, é resolvido utilizando o software de otimização CPLEX. Os resultados das metaheurísticas propostas ILS, AG-B e AG-BL são comparados e analisados entre si e também com as soluções determinadas por duas heurísticas construtivas, MST e NEH-MST. Após os ajustes dos parâmetros necessários e diversos testes, observou-se que a metaheurística ILS foi à técnica mais eficiente para obter soluções de boa qualidade para o problema estudado.This work deals with the problem of job scheduling in flexible flowshop system with the objective of minimizing the penalties for tardiness and earliness in terms of the job due date. It is considered that all jobs are available for processing in different moments, according to them release times, besides that, there are setup times depending on the sequence and stages. The problem addressed belongs to the production programming environment JIT (just-in-time). In this environment, each job has a processing time and due date within which it should preferably be completed, therefore the processing a job should end as closer as possible to its due date. When a job finishes processing earlyth, production is finalized before due date, hence it must be stored, which generates storage costs. When the job is tardy is the job and consequent delay on further productions, causing a chain effect, causing loss of trust from consumer, which has unestimated cost, besides contract fines, which harms the image of an enterprise. In this work it was developed an PLIM for the problem. Due to the problem computational complexity, heuristics and metaheuristic are used for obtaining good quality approximate solutions. Metaheuristics applied are Iterated Local Search (ILS) and Genetic Algorithm (GA): basic genetic algorithm (GA-B) and Genetic Algorithm with local search (GA-LS). The GA-LS is an adaptation of the GA-B with local search, applied for improving a solutions determined by the genetic operators. PLIM model, for of problems smaller size, is solved by using the optimization software CPLEX. Results obtained from the proposed heuristics ILS, AG-B and AG-BL are compared and analyzed among themselves and also with solutions determined by constructive heuristics, MST and NEH-MST, computational tests have shown that metaheuristic ILS obtains solutions of good quality. After adjusting the required parameters and several tests showed that the ILS was the most effective technique for obtaining good quality solutions to the problem studied