Uma abordagem heurística híbrida para o problema de sequenciamento de tarefas com datas de liberação e restrições de inventário

Abstract

Scheduling problems are commonly addressed in the literature and have several ap-plications in industry. Among its numerous variants, this work focuses on the pro-blem of minimizing the makespan on a single-machine scheduling problem with release dates and inventory constraints. To solve this problem, a simple yet effective hy-brid population-based ruin-and-recreate (HyPRR) heuristic is proposed. In addition to a simple ruin-and-recreate procedure, the algorithm incorporates a diversification scheme for population management and an intensification phase through local search. To enhance performance, we introduced a move evaluation strategy capable of efficien-tly computing both the makespan and assessing infeasibility with respect to inventory constraints in amortized constant time. Computational experiments on a set of 960 instances highlight the competitiveness of the proposed algorithm when compared to the guess-and-check (GC) found in the literature. The developed method found the optimal solution in 99% of the instances with known optima, and produced new best solutions for 21 instances.