Métodos de solução para um problema de sequenciamento da produção com sincronismo de execução de tarefas

Abstract

Nesta tese é apresentado o problema de sequenciamento da produção em máquinas paralelas, sem interrupções, sem buffers, com tempos de processamento dependentes da sequência, restrições de capacidade, e sincronismo de execução das tarefas, com o objetivo de minimizar o makespan. Este problema, encontrado no mundo real em processos de fabricação de cilindros de laminação fundidos, possui a particularidade de que pares de tarefas devem ser concluídos ao mesmo tempo, o que torna a solução do problema ainda mais complexa. Inicialmente é proposta uma formulação de programação linear inteira para o problema. A seguir, são desenvolvidos vários métodos de solução que combinam as heurísticas relax-and-fix, iterated local search, variable neighborhood search, e large neighborhood search. Resultados computacionais obtidos a partir de problemas reais mostram que as soluções obtidas pelos métodos propostos superam aqueles obtidos por um software de programação inteira mista padrão executado durante uma hora e meia, sendo que no melhor deles, o gap entre a solução gerada e o melhor limitante inferior conhecido é, em média, de 6%

This paper presents the no-preemptive parallel scheduling problem without buffers,with sequence dependent set-up times,machine eligibility restrictions,and task execution synchronization, with theaim of minimizing themakespan.This problem, found in the real worldin manufacturing processes ofcast rolling mill rolls, has the particularity that pairs of tasks must be completed at the same time, which makes the problemsolution more complex. Initially, a mixed-integerprogramming of the problem isproposed.Following that, several methods thatcombineheuristics relax-and-fix, iterated local search,variable neighborhoodsearch, e large neighborhoodsearch are developed. Computational resultsobtained from real problems showthat the solutions obtained by the proposed methods outperformthose returned by a standardMIP(Mixed Integer Programming) solver after one and ahalf hours. In the best method, the gapbetween the solution andthe best lower bound known isonaverage 6%