The Single Machine Total Weighted Tardiness Problem - Is it (for
  Metaheuristics) a Solved Problem ?
  The article presents a study of rather simple local search heuristics for the
single machine total weighted tardiness problem (SMTWTP), namely hillclimbing
and Variable Neighborhood Search. In particular, we revisit these approaches
for the SMTWTP as there appears to be a lack of appropriate/challenging
benchmark instances in this case. The obtained results are impressive indeed.
Only few instances remain unsolved, and even those are approximated within 1%
of the optimal/best known solutions. Our experiments support the claim that
metaheuristics for the SMTWTP are very likely to lead to good results, and
that, before refining search strategies, more work must be done with regard to
the proposition of benchmark data. Some recommendations for the construction of
such data sets are derived from our investigations.
