A Genetic Algorithm Approach for Minimizing Total Tardiness in Single Machine Scheduling (pp. 163-171)
Gursel A. Suer, Xiaozhe Yang, Omar I. Alhawari, Joel Santos, Ramon Vazquez
Minimizing total tardiness in single machine scheduling is known as NP-hard. In this paper, the problem is extended to include non-zero ready times and the preemption of jobs is not allowed. First, a mathematical model is developed. Due to computational complexities with the mathematical model, a Genetic Algorithm approach is also proposed and later its performance is compared with optimal solutions. The results show that GA can find optimal solution for small problems and near optimal solutions for large problems. The results also show that among Delay-only, Non-delay-only, and Random strategies, Non-delay strategy produced more robust solutions whereas random strategy found the optimal solution in smaller problem categories.