A hybrid population-based heuristic for a single machine scheduling problem with release dates and inventory constraints

This paper proposes a simple yet effective hybrid population-based ruin-and-recreate (HyPRR) heuristic for minimising the makespan on a single-machine scheduling problem with release dates and inventory constraints. In addition to a ruin-and-recreate procedure, the algorithm incorporates a diversification scheme for population management and an intensification phase through local search. A key component of the proposed approach is a novel and highly efficient move evaluation strategy that enables makespan computation and inventory infeasibility to be verified in amortised constant time. Computational experiments on 1044 instances highlight the competitiveness of the proposed algorithm compared to the guess-and-check (GC) method from the literature. For the existing benchmark instances, the developed method found the optimal solution in 99% of the cases with known optima, and produced new best solutions for 21 instances. Furthermore, we introduced a new set of larger benchmark instances designed to be more challenging than those in the literature. The results of the experiments on these instances show that, although both methods perform well, HyPRR outperforms GC in terms of the number of optimal solutions found and the average solution quality. More importantly, for these instances, while HyPRR always finds a feasible solution, GC failed to find one for several instances.