Made available in DSpace on 2016-06-02T19:53:31Z (GMT). No. of bitstreams: 1 LUGO_Pedro_2013.pdf: 2147400 bytes, checksum: a0c7948826b7f243c447b99fd96c3388 (MD5) Previous issue date: 2013-09-12 / Financiadora de Estudos e Projetos / This research studies the hybrid flowshop scheduling problem. In this production configuration, we have a set of jobs that has to be processed in a set of stages. At every stage we have a set of parallel machines available to process the jobs. All jobs have to be processed following the same production flow, from the first to the last stage. Every job has to be processed on one machine at each stage and each machine can process at most one job at a time. Some constraints commonly found in real production systems as unrelated parallel machines, limited buffers, sequence-dependent setup times (both anticipatory and non-anticipatory), machine eligibility, transportation times and release times for machines are also taken into account. The optimization criterion is the makespan, whose minimization is related to the efficient use of production resources. A mixed integer programming model is proposed and solved by the commercial solver CPLEX. The computational evaluation results indicate that the model is suitable just to solve instances up to nine jobs and five stages. Therefore, to solve larger instances (50-100 jobs), several heuristics and an iterated local search (ILS) algorithm are proposed and evaluated computationally. The results indicate that the ILS is able to obtain good quality solutions in short computation times. / Este trabalho estuda o problema de programação da produção em sistemas Flowshop híbrido. Nesta configuração de produção há um conjunto de tarefas que deve ser processado em um conjunto de estações, nas quais um determinado número de máquinas paralelas encontra-se disponível para o processamento das tarefas. Todas as tarefas devem ser processadas seguindo o mesmo fluxo de produção, desde a primeira até a última estação. Cada tarefa deve ser processada em uma máquina de cada estação e cada máquina pode processar, no máximo, uma tarefa por vez. Algumas restrições comumente encontradas em sistemas de produção reais, como máquinas paralelas não relacionadas, buffers limitados, tempos de preparação dependentes da sequência (antecipatórios e não antecipatórios), elegibilidade de máquinas, tempos de transporte e tempos de liberação das máquinas, também são consideradas. O critério de otimização é o makespan, cuja minimização está diretamente relacionada com a utilização eficiente dos recursos de produção. Um modelo de programação inteira mista é proposto e resolvido através do solver comercial CPLEX. Os resultados da avaliação computacional indicam que o modelo é viável somente para resolver instâncias de até nove tarefas e cinco estações. Desta forma, para resolver instâncias de maior tamanho (50-100 tarefas), várias heurísticas e uma meta-heurística de busca local iterada (ILS, Iterated Local Search) são propostas e avaliadas computacionalmente. Os resultados indicam que o ILS é capaz de obter soluções de boa qualidade em curtos tempos computacionais.