Preemptive scheduling of two uniform parallel machines to minimize total tardiness

► Preemptive scheduling of n equal jobs on two uniform machines is considered. ► We suggest an O(n log n) algorithm to minimize total tardiness. ► The algorithm is based on the SPT-rule and uses the partial schedule transformations. ► We prove the theorem that justifies the algorithm.