This paper proposes the Tabu Search algorithm to minimize mean tardiness in the parallel machine scheduling problem. The algorithm reduces the computation time by employing restricted neighborhood and produces an efficient solution in this problem.