A priority rule for minimizing weighted flow time in a class of parallel machine scheduling problems (Q1310018): Difference between revisions
From MaRDI portal
Latest revision as of 11:18, 30 July 2024
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
