A priority rule for minimizing weighted flow time in a class of parallel machine scheduling problems (Q1310018)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A priority rule for minimizing weighted flow time in a class of parallel machine scheduling problems |
scientific article |
Statements
A priority rule for minimizing weighted flow time in a class of parallel machine scheduling problems (English)
0 references
31 August 1994
0 references
Scheduling \(n\) jobs with known processing times and weights on \(m\) identical machines with the objective to minimize weighted flow time is known to be an NP-complete optimization problem. The author identifies an interesting subclass of problem instances for which an optimal schedule can be derived efficiently by using the simple heuristic of scheduling jobs on the first available machine in order of nondecreasing processing time/weight relation.
0 references
priority rule
0 references
identical machines
0 references
weighted flow time
0 references
NP-complete
0 references
0 references
