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.