Tabu search for total tardiness minimization in flowshop scheduling problems

This work addresses the permutation flowshop scheduling problem with the objective of minimizing total tardiness. First, the behavior of solutions for small problems is analyzed for different due date scenarios. Then a tabu search-based heuristic is proposed as a method to explore the solution space. Diversification, intensification, and neighborhood restriction strategies are evaluated. Computational tests are presented and comparisons with the Nawaz–Enscore–Ham algorithm and with a Branch-and-Bound algorithm are made.