Single machine early-tardy scheduling with distinct due dates

In this paper we study the problem of schedule n jobs on a single machine with the objective of minimizing total earliness and tardiness when each job has its own distinct due date. The problem is known to be NP hard. A new Tabu search based algorithm for solving the problem is developed and its parameters are optimized. Several versions of the algorithm are considered for performance testing against the performance of a greedy algorithm. A comprehensive experimental work in which a large number of problems are generated with different sizes and different characteristics for testing the performance under different shop condition environment. The experimental work shows significant improvement over the greedy algorithm.