The problem of scheduling n nonpreemptive jobs having a common due date d on m, m ≥ 2, parallel identical machines to minimize total tardiness is studied. Approximability issues are discussed and two families of algorithms {A ε} and {B ε} are presented such that (T 0 − T*)/(T* + d) ≤ ε holds for any problem instance and any given ε > 0, where T* is the optimal solution value and T 0 is the value of the solution delivered by A ε or B ε. Algorithms A ε and B ε run in O(n 2m /ε m−1) and O(n m+1/ε m ) time, respectively, if m is a constant. For m = 2, algorithm A ε can be improved to run in O(n 3/ε) time.