Minimizing Flow Time on Parallel Identical Processors with Variable Unit Processing Time
Operations Research · 1984 · Volume 32 · Issue 2
Abstract
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.
Keywords
581 processors with variable processing rate
Enable JavaScript for citation tools and additional paper interactions.