A discrete differential evolution algorithm for single machine total weighted tardiness problem with sequence dependent setup times

In this paper, a discrete differential evolution algorithm with the reference local search is presented to solve the single machine total weighted tardiness problem with sequence dependent setup times. In addition, To facilitate the greedy job insertion into a partial solution, newly designed speed-up methods are presented for the insertion move as a further and novel contribution to the single machine tardiness related scheduling with sequence dependent setup times literature. To evaluate its performance, the discrete differential evolution algorithm is tested on a set of benchmark instances from the literature. Through the analyses of experimental results, highly effective performance of the discrete differential evolution algorithm is shown against the best known solutions from the literature, especially, against the very recent newly designed particle swarm optimization algorithm and ant colony algorithm of Anghinolfi & Paolucci [European Journal of Operational Research 2007; don: 10.1016/j.ejor.2007.10.044, Available Online] and Anghinolfi & Paolucci [to appear in the International Journal of Operations Research 2007], respectively. Ultimately, 46 out of 120 aggregated best known solutions so far in the literature are further improved.