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.

This paper deals with the single-machine scheduling problem with earliness and tardiness penalties. Sequence dependent setup times and distinct due windows are considered. In order to solve this problem, a three-phase heuristic approach, the so-called GTSPR, was developed. The first phase is based on GRASP and Variable Neighborhood Descent to generate an initial solution; the second phase is based on Tabu Search for solution refining, finally, Path Relinking is used as a mechanism of post-optimization. For each job sequence generated by the heuristic, an optimal timing algorithm is used to determine the completion time for each job in the job sequence. Computational experiments carried out show that GTSPR outperforms the previous algorithms found in the related literature, regarding the quality of the final solution and the average gap.