  This paper addresses the scheduling problem of minimizing the total weighted
tardiness on a single machine with step-deteriorating jobs. With the assumption
of deterioration, the job processing times are modeled by step functions of job
starting times and pre-specified job deteriorating dates. The introduction of
step-deteriorating jobs makes a single machine total weighted tardiness problem
more intractable. The computational complexity of this problem under
consideration was not determined. In this study, it is firstly proved to be
strongly NP-hard. Then a mixed integer programming model is derived for solving
the problem instances optimally. In order to tackle large-sized problems, seven
dispatching heuristic procedures are developed for near-optimal solutions.
Meanwhile, the solutions delivered by the proposed heuristic are further
improved by a pair-wise swap movement. Computational results are presented to
reveal the performance of all proposed approaches.
