First fit decreasing scheduling on uniform multiprocessors (Q1061602)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: First fit decreasing scheduling on uniform multiprocessors |
scientific article; zbMATH DE number 3912082
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | First fit decreasing scheduling on uniform multiprocessors |
scientific article; zbMATH DE number 3912082 |
Statements
First fit decreasing scheduling on uniform multiprocessors (English)
0 references
1985
0 references
Independent tasks are nonpreemptively scheduled on \(m\geq 2\) processors which are assumed to have different speeds. The purpose of this paper is to show that the worst case ratio of the multifit algorithm MF, which is based on the bin-packing method FFD (first fit decreasing), depends on the order of the processors and that the MF has a better worst case behaviour than the well-known LPT algorithm for certain processor configurations.
0 references
uniform multiprocessor systems
0 references
nonpreemptive scheduling
0 references
Independent tasks
0 references
worst case ratio
0 references
