Two novel population based algorithms for the single machine scheduling problem with sequence dependent setup times and release times

Abstract This paper presents a heuristic and a metaheuristic algorithm for solving the challenging single machine scheduling problem with release dates and sequence-dependent setup times to minimise the makespan. Notably, the former is a population-based constructive heuristic based on a beam search strategy that evolves through a variable number of partial sequences. The solutions obtained in the last iteration feed the initial pool of the latter proposal consisting of a population-based iterated-greedy procedure. The two proposed approximate algorithms are evaluated considering both anticipatory and non-anticipatory setup times, against the most promising algorithms of the related scheduling problems. The computational experience confirms the effectiveness of the proposed approaches, regardless of the adopted setup strategy.