A note on LPT scheduling (Q5903677)
From MaRDI portal
scientific article; zbMATH DE number 4057267
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A note on LPT scheduling |
scientific article; zbMATH DE number 4057267 |
Statements
A note on LPT scheduling (English)
0 references
1988
0 references
The problem to be analyzed is one of scheduling independent tasks on a set of parallel, uniform processors. Tasks are assumed to be scheduled nonpreemptively. The algorithm to be analyzed is LPT (longest processing time-first). The worst case bound for this algorithm was proved to be: \[ C_{LPT}/C\quad *\leq \max \{s_ m/2;2\}, \] where \(s_ m\) is the processing speed of the fastest processor.
0 references
LPT-algortihm
0 references
independent tasks
0 references
parallel, uniform processors
0 references
longest processing time-first
0 references
worst case bound
0 references
