Effective heuristics for solving dynamic variant of single processor total tardiness problems

Abstract

This paper considers the dynamic variant of single processor scheduling problem of minimizing total tardiness. In practice, it occurs when minimizing tardiness penalty. The problem is NP-hard; thus two heuristics were proposed. The utility of the proposed models was demonstrated through computational experiments and comparative analyses against existing solution methods and the Branch and Bound (BB) method. The results show that the proposed models yield effi-cient solutions and in most cases perform effectively better than the existing heuristics in the lit-erature.

Keywords

• Heuristics
• Branch and Bound
• Total Tardiness
• Efficient solution
• Effective