Heuristics algorithms for the single machine total tardiness problem. This paper presents approximations algorithms for the single machine total weighted tardiness problems. The algorithms is based on a tabu search technique with a specific neighborhood definition. Results of testing the algorithms on large number of randomly generated examples are also given and analysed.
We consider a strong NP-hard single-machine scheduling problem with deadlines and minimizing the total weight of late jobs on a single machine (). Processing times are deterministic values or random variables having Erlang distributions. For this problem we study the tolerance to random parameter changes for solutions constructed according to tabu search metaheuristics. We also present a measure (called stability) that allows an evaluation of the algorithm based on its resistance to random parameter...
Page 1