Heurísticas híbridas para o problema de programação de tarefas em máaquinas paralelas não relacionadas com penalidades por antecipação e atraso / Hybrid heuristics for the problem of scheduling tasks on unrelated parallel machines with penalties for earliness and tardiness

AUTOR(ES)

João Paulo de Castro Martins Nogueira

FONTE

IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia

DATA DE PUBLICAÇÃO

03/08/2011

RESUMO

O presente trabalho trata o problema de sequenciamento de tarefas em máquinas paralelas não relacionadas. No problema abordado, é considerado tanto o tempo de preparação das máquinas, o qual depende da sequência de produção, quanto o tempo de processamento das tarefas, que dependem das máquinas. Cada tarefa possui uma data de entrega que deve ser cumprida, caso contrário uma penalidade é aplicada. O objetivo do problema é minimizar a soma de penalidades por atraso e adiantamento das tarefas. Em termos práticos, as penalidades por adiantamento são consequências de custos gerados pela necessidade de estocagem, enquanto as penalidades por atraso das tarefas são originadas de multas contratuais. Primeiramente é utilizado um modelo matemático de programaçao linear inteira mista (PLIM) para representar o problema. Este modelo é resolvido pelo software de otimização CPLEX 12.0. Em seguida é utilizado um algoritmo baseado no método Greedy Randomized Adaptive Search Procedure (GRASP) com o objetivo de determinar soluções aproximadas de boa qualidade. Após isso, o método GRASP é hibridizado com o procedimento de intensificação Path Relinking (PR) e o método Iterated Local Search (ILS), resultando nas heurísticas híbridas GRASP+ILS, GRASP+PR e GRASP+ILS+PR. As heurísticas foram testadas em conjuntos de instâncias de pequeno, médio e grande porte. Os resultados obtidos pelas heurísticas utilizadas são comparados entre si. A análise dos resultados obtidos mostra que a hibridização da heurísstica GRASP faz com que o desempenho do procedimento melhore.

ASSUNTO(S)

heurísticas sequenciamento de tarefas ciencia da computacao sequencing jobs heuristics combinatorial optimization otimização combinatória

Documentos Relacionados

• Metaheurísticas para o problema de Flowshop flexível com penalidades de adiantamento e atraso
• HYBRID HEURISTICS FOR THE PHYLOGENY PROBLEM
• SINGLE MACHINE SCHEDULING PROBLEM WITH SEQUENCE DEPENDENT SETUP TIMES, WITH EARLINESS AND TARDINESS PENALTIES: A CASE STUDY IN A MACHINING PROCESS
• Metaheurísticas para o problema de programação de tarefas em máquinas paralelas com tempos de preparação dependentes da sequência e de recursos
• Branch-and-bound method application in a single machine earliness/tardiness scheduling problem with a common due date.