Bounds and asymptotic results for the uniform parallel processor weighted flow time problem
Scheduling \(n\) jobs with known process times and weights on \(m\) parallel processors of different speed with the objective to minimize weighted flow time is known to be an NP-complete optimization problem. The author derives lower and upper bounds for the uniform processor problem which generalize well-known bounds for the identical processor problem. These bounds are used to show asymptotic properties of the uniform processor problem. Based on this it is shown that the heuristic of scheduling jobs on the first available processor in order of nondecreasing process time to weight ratio is asymptotically relatively optimal for a growing number of jobs. Also, the lower bound is asymptotically relatively optimal.
scientific article; zbMATH DE number 527398
scientific article