Uma abordagem heurística para o problema de escalonamento de tarefas em uma máquina com datas de liberação e tempos de setup dependentes da sequência

Abstract

This work addresses the problem of task sequencing on a single machine, considering release dates and non-anticipatory, sequence-dependent setup times, with the aim of minimizing the makespan. For this purpose, a hybrid heuristic approach combining iterated local search and beam search has been proposed. This approach includes an efficient strategy for evaluating moves in local search, based on concatenating subsequences, enabling constant amortized time evaluation. Computational experiments were conducted on a set of 1800 instances taken from the literature, with sizes ranging from 25 to 150 tasks. The results obtained were compared with those of the best-known heuristics for this problem, demonstrating that the proposed method is capable of generating highly competitive solutions.