  We present computational results with a heuristic algorithm for the parallel
machines total weighted tardiness problem. The algorithm combines generalized
pairwise interchange neighborhoods, dynasearch optimization and a new
machine-based neighborhood whose size is non-polynomial in the number of
machines. The computational results significantly improve over the current
state of the art for this problem.
