Decomposition and hybrid simulated annealing heuristics for the parallel-machine total tardiness problem

A polynomial decomposition heuristic is developed for the parallel-machine tardiness problem (P//nT) by extending the decomposition principle embedded in the single-machine tardiness problem (1//nT) to a parallel-machine setting. The subproblems generated by the decomposition are solved by an effective heuristic that yields solutions such that the schedule on any individual machine satisfies the single-machine decomposition principle. A hybrid simulated annealing heuristic tailored to the P//&Nmacr;T problem is also presented. Computational results decomstrate the efficiency and effectiveness of the decomposition heuristic.