Heuristica

Produção, v. 22, n. 4, p. 766-777, set./dez. 2012 http://dx.doi.org/10.1590/S0103-65132012005000020

Uma heurística híbrida para minimizar custos com antecipação e atraso do sequenciamento da produção em uma máquina
Puca Huachi Vaz Pennaa*, Marcone Jamilson Freitas Souzab, Frederico Augusto de Cezar Almeida Gonçalvesc, Luiz Satoru Ochid
*[e-mail], UFOP, Brasil [e-mail], UFF, Brasil c [e-mail], CEFET-MG, Brasil d [e-mail], UFF, Brasil a b

Resumo
Este trabalho tem seu foco no problema de sequenciamento em uma máquina com penalidades por antecipação e atraso da produção. São considerados tempos de preparação da máquina dependentes da sequência de produção, bem como a existência de janelas de entrega distintas. Para resolução do problema, desenvolveu-se um algoritmo heurístico de 3 fases, nomeado GTSPR. A primeira fase baseada em GRASP é descida em vizinhança variável para a geração da solução inicial, a segunda fase baseada em busca tabu para refinamento da solução, e por fim a reconexão por caminhos como estratégia de pós-otimização, na terceira fase. Para cada sequência gerada pela heurística é utilizado um algoritmo de tempo polinomial para determinar a data ótima de início de processamento de cada tarefa. Os resultados computacionais mostraram que o algoritmo GTSPR supera outros algoritmos da literatura, tanto com relação à qualidade da solução final quanto em relação à variabilidade dessas soluções.

Palavras-chave
Sequenciamento em uma máquina. GRASP. Busca tabu. Descida em vizinhança variável. Reconexão por caminhos.

1. Introdução
De acordo com França Filho (2007), o estudo de problemas de programação de tarefas envolvendo penalizações pela antecipação e pelo atraso é mais recente que aquele voltado para problemas em que o objetivo envolve uma função não decrescente do instante de conclusão do processamento da tarefa, tais como tempo médio de fluxo, soma ponderada de atrasos e makespan (momento em que termina