A study of hybrid evolutionary algorithms for single machine scheduling problem with sequence-dependent setup times

We present a systematic comparison of hybrid evolutionary algorithms (HEAs), which independently use six combinations of three crossover operators and two population updating strategies, for solving the single machine scheduling problem with sequence-dependent setup times. Experiments show the competitive performance of the combination of the linear order crossover operator and the similarity-and-quality based population updating strategy. Applying the selected HEA to solve 120 public benchmark instances of the single machine scheduling problem with sequence-dependent setup times to minimize the total weighted tardiness widely used in the literature, we achieve highly competitive results compared with the exact algorithm and other state-of-the-art metaheuristic algorithms in the literature. Meanwhile, we apply the selected HEA in its original form to deal with the unweighted 64 public benchmark instances. Our HEA is able to improve the previous best known results for one instance and match the optimal or the best known results for the remaining 63 instances in a reasonable time.