Abstract
In this study, a Tabu search
algorithm is presented to solve Single Machine Total Weighted Tardiness problem
(SMTWT), which is an NP-Hard [16] problem and involves scheduling a set of
independent processes on a single machine. To formulate the problem, the
positive processing time (Pj), weight (Wj)
and a distinct due date (Dj) is defined for each process. The
main objective of this algorithm is to find a proper scheduling of processes in
a way that the total weighted tardiness is minimized. The proposed algorithm is
equipped with a three stage optimization procedure to prevent converging to a
local optimum. Comparing the achieved results on 100, 50 and 40-functional
applications with the existing optimum values from OR-library shows that the
proposed method is capable of solving 97.8% of the problems in this library. It
also proves a significant improvement over one of the famous Tabu search algorithms
[15] for these applications.