Applying metaheuristics to single machine scheduling problems

In this paper, the authors describe some general features of single-machine scheduling problems, and they use some of their structural properties to design local search procedures based on alternative definitions of neighbourhoods. In particular, the traditional idea of ‘pairwise interchanges’ is replaced by the idea of ‘exchanging jobs not apart more than a given number of positions (considered as a parameter of the algorithm)’. For generating initial solutions, the authors have tested some traditional priority rules, with some degree of randomization introducing, in general, a positive effect in the performance of the algorithms. Through a set of computational tests, the authors have evaluated the importance of the different parameters, and the authors have tuned their values for different meta-heuristic procedures (simulated annealing, tabu search, and ‘randomized local search’). Though these tests have been exhaustive only for a given problem (‘weighted tardiness’), the results already available show these approaches are robust and flexible, and that, in general, the authors obtain satisfactory solutions in an efficient way.