A new filter and fan algorithm with kick strategy for single-machine tardiness scheduling with sequence-dependent setups

In this paper, a filter and fan method is proposed for the single-machine tardiness scheduling problem with sequence-dependent setups, which is a typical NP-hard combinational optimization problem. The method searches the solution space by means of neighborhood search tree and the tree branches are extended by predefined moves. To enhance the algorithm ability of escaping from local optima, kick strategy of iterated local search is embedded into the method. Computational results on benchmark instances show that the method obtains solutions that are comparative to the known solutions.