A Cluster-based Evolutionary Algorithm for the Single Machine Total Weighted Tardiness-scheduling Problem

Abstract

In this paper a new evolutionary algorithm is described
for the single machine total weighted tardiness problem.
The operation of this method can be divided in three
stages: a cluster forming and two local search stages.
In the first stage it approaches some locally optimal
solutions by grouping based on similarity. In the second
stage it improves the accuracy of the approximation of
the solutions with a local search procedure while periodically
generating new solutions. In the third stage the
algorithm continues the application of the local search
procedure. We tested our algorithm on all the benchmark
problems of ORLIB. The algorithm managed to find,
within an acceptable time limit, the best-known solution
for the problems, or found solutions within 1% of the
best-known solutions in 99 % of the tasks.