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 / Metaheuristics for the parallel machines scheduling problem with resource-assignable sequence dependent setup times

AUTOR(ES)

Edmar Hell Kampke

DATA DE PUBLICAÇÃO

2010

RESUMO

Os problemas de programação de tarefas em máquinas paralelas são importantes na área de otimização combinatória, pois quase sempre envolvem problemas rotineiros em indústrias de pequeno e grande porte. Este trabalho aborda o problema de sequenciamento de tarefas em máquinas paralelas, com tempos de preparação das máquinas dependentes da sequência e do número de recursos utilizados. A característica deste problema é que o tempo de preparação não é determinado apenas pela máquina e pela sequência das tarefas, mas também pela quantidade de recursos associados, que varia entre um valor mínimo e um máximo. Dada a complexidade combinatória do problema, inicialmente propõe-se um algoritmo baseado na metaheurística GRASP, no qual o parâmetro de aleatoriedade utilizado na fase de construção é auto-ajustado de acordo com as soluções previamente encontradas (GRASP Reativo). Em seguida, propõe-se um algoritmo baseado na metaheurística Iterated Local Search (ILS). Esta metaheurística foi proposta recentemente na literatura e está sendo aplicada satisfatoriamente em diversos problemas de otimização combinatória. Em ambos os algoritmos, é utilizada a estratégia de intensificação baseada na técnica de Reconexão de Caminhos, que explora trajetórias que conectam soluções de alta qualidade encontradas pelos algoritmos. Os resultados obtidos pelos algoritmos propostos são comparados entre si e com os melhores resultados disponibilizados na literatura. A análise e a discussão dos resultados mostram que as metaheurísticas aplicadas, apresentaram resultados satisfatórios, sendo possível melhorar, em média, 9,14%, os resultados da literatura, o que comprova a viabilidade do uso destes algoritmos na resolução de problemas práticos existentes nas indústrias.

ASSUNTO(S)

otimização combinatória heurísticas metaheurísticas programação de tarefas máquinas paralelas ciencia da computacao combinatorial optimization heuristics metaheuristics task scheduling parallel machines

Documentos Relacionados

• Evolutionary Algorithms for Parallel Machine Scheduling Problems with Sequence Dependent Setup Times
• Estudo de meta-heuristicas populacionais para a programação de maquinas paralelas com tempos de preparação dependentes da sequencia e datas de entrega
• O PROBLEMA DA PROGRAMAÇÃO DE LOTES ECONÔMICOS DE PRODUÇÃO (ELSP) COM TEMPOS E CUSTOS DE SETUP DEPENDENTES DA SEQÜÊNCIA: UM ESTUDO DE CASO
• Métodos heurísticos para a programação em flow shop permutacional com tempos de setup separados dos tempos de processamento e independentes da seqüência de tarefas
• Um problema de sequenciamento em máquinas paralelas não-relacionadas com tempos de preparação dependentes de máquina e da sequência:: modelos e algoritmos exato.