Decomposition heuristic algorithm for the total tardiness problem

A decomposition heuristic algorithm was developed to solve the single machine total tardiness problem. The algorithm combines the decomposition algorithm proposed by Lawler, the most successful optimizing algorithm to date for this problem, with the very efficient modified due date (MDD) algorithm. At each iteration of the procedure, MDD algorithm is used to estimate the total tardiness corresponding to each decomposition position of the Lawler decomposition algorithm with the job with the longest processing time fixed to the position yielding the minimum total tardiness. The algorithm theoretically proves to be superior to MDD algorithm. Simulation results show that the algorithm generates solutions with an optimal sequence ratio larger than 99%. The algorithm can solve a problem with up to 1000 jobs with an appropriate solution close to the optimal sequence in short time.