The authors study the optimality of expected earliest due date sequencing of n jobs on M parallel identical machines, to minimize the total tardiness. The processing times of the jobs are assumed to be identically distributed with distribution function F(x), and the due date of job j, Dj, j=1,...,n is assumed to be distributed with distribution function Gj. The authors give stochastic comparisons of the objective function when the due dates are comparable in different stochastic order relations. For a single processor, the results are extended to the case when the processing times are not identically distributed, but are compatible with the due dates.