On Minimizing Flow Time on Processors with Variable Unit Processing Time

This paper uses the interchange technique to prove a result of Meilijson and Tamir that the shortest processing time (SPT) schedule minimizes total flow time on parallel identical processors that have unequal starting times and nonincreasing unit processing time. The SPT schedule remains optimal for a special case when the unit processing time is increasing.