Minimizing Flow Time on Parallel Identical Processors with Variable Unit Processing Time

We show that minimizing total flow time on parallel identical processors with nonincreasing unit processing time is achieved with shortest processing time (SPT) scheduling: Sequence the tasks in an order of nondecreasing lengths. Following this order and starting with the shortest task, process any task by the first processor that becomes available. If the unit processing time is allowed to be increasing, e.g., quadratically, the problem becomes NP-hard.