Bounds and asymptotic results for the uniform parallel processor weighted flow time problem (Q1317007)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 527398
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Bounds and asymptotic results for the uniform parallel processor weighted flow time problem |
scientific article; zbMATH DE number 527398 |
Statements
Bounds and asymptotic results for the uniform parallel processor weighted flow time problem (English)
0 references
19 January 1995
0 references
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.
0 references
parallel processors
0 references
weighted flow time
0 references
asymptotic properties
0 references
uniform processor problem
0 references
0 references
0 references
0.8817837834358215
0 references
0.8817837834358215
0 references
0.8596757650375366
0 references
0.8491408228874207
0 references
