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 NEH algorithm and with a Branch-and-Bound algorithm are made. Scope and purpose Surveys of production scheduling show that meeting customer due dates is a critical concern for many manufacturing systems. While there is considerable research to minimize the makespan, very little work is reported on minimizing the total tardiness for scheduling jobs on a permutation flowshop. In this paper, we investigate the application of tabu search to this problem in order to obtain better solutions in a reasonable time. Special strategies are included to improve the performance of the method.