  In this article, we study a single-machine scheduling problem of minimizing
the total tardiness for a set of independent jobs. The processing time of a job
is modeled as a step function of its starting time and a specific deteriorating
date. A mixed integer programming model was applied to the problem and
validated. Since the problem is known to be NP-hard, we proposed a heuristic
named simple weighted search procedure (SWSP) and a general variable
neighborhood search algorithm (GVNS).
  A perturbation procedure with 3-opt is embedded within the GVNS process in
order to explore broader spaces. Extensive numerical experiments are carried
out on some randomly generated test instances so as to investigate the
performance of the proposed algorithms. By comparing to the results of the
CPLEX optimization solver, the heuristic SWSP and the standard variable
neighborhood search, it is shown that the proposed GVNS algorithm can provide
better solutions within a reasonable running time.
