Scatter search is a heuristic method of generating nonrandom solutions. It systematically explores the solution space by constructing new trial solutions from reference solutions using context knowledge. A standard template of the process consists of five methods, namely diversification generation, improvement, reference set update, subset generation, and solution combination.

Given a set of jobs that are assigned nonnegative weights (according to their importance), along with the processing time and due date of each job, the scheduling problem consists of finding a linear processing order for the jobs on a single machine such that the total weighted tardiness is minimized. The solution of the problem has wide industrial applications in manufacturing and service sectors.

The formulation of the scheduling problem used by the authors here also takes into account the variable amount of setup time between jobs. A new algorithm, scatter search with path relinking (SSPR), is proposed. SSPR maintains and evolves a population of solutions balancing between diversification and intensification of the search. Path relinking is used as the solution combination method.

The paper is self-contained and provides the necessary background, the problem formulation, and a nice review of the state of the art, along with adequate references. Descriptions given are somewhat long, but can be helpful for readers new to the domain. A major portion of the paper is allotted to a discussion of the experimental results. The authors also propose a new benchmark with larger instances, and that will be of interest to researchers.