This paper first considers the problem of sequencing n jobs on one machine to minimize total tardiness. It proves theorems that establish the relative order in which pairs of jobs are processed in an optimal schedule; frequently they permit the jobs to be completely ordered, thus solving the problem without any searching. In particular, corollaries establish more general conditions than are currently recognized under which sequencing in order of nondecreasing processing times and sequencing in order of nondecreasing due dates are optimal. In general, even large problems may be at least partially ordered to the point that very few schedules remain to be searched. These results are then partly extended to the more general criterion of minimizing a sum of identical, convex, nondecreasing functions of job tardiness, and an efficient algorithm is proposed.