A HYBRID HEURISTIC APPROACH TO SCHEDULING PROBLEMS WITH RELEASE DATES AND INVENTORY CONSTRAINTS

Scheduling problems are commonly addressed in the literature and have several applications in industry. Among its numerous variants, this work focuses on the problem of minimizing the makespan, considering inventory and release dates constraints. To solve this problem, a hybrid heuristic approach based on population-based search is proposed. The proposed method includes intensification and diversification procedures, where the former conducts a local search with an efficient move evaluation, while the latter comprise a strategy inspired by ruin-and-recreate strategy, along with the implementation of a population diversity control mechanism. Computational experiments on a set of 960 instances demonstrate the competitiveness of the proposed algorithm compared to the guess-and-check (GC) algorithm found in the literature. The HyPRR algorithm obtained better solutions in 21 instances, the same solution in 927 instances, and was outperformed by the GC in 12 instances.