In this paper we consider to parallel machines scheduling problems for minimizing mean tardiness that is known NP-complete. This problems is classified into two cases, one of which is the case which processing time are identical and the other, nonidentical. A Tabu Search method is applied to the problems considered in this paper to get an improved solution. To this end, we design move attribute, Tabu attribute and Tabu tenure, and thereafter perform the experiments to the problems.