Worst-case analysis of a scheduling algorithm (Q1060946)
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 3910119
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Worst-case analysis of a scheduling algorithm |
scientific article; zbMATH DE number 3910119 |
Statements
Worst-case analysis of a scheduling algorithm (English)
0 references
1985
0 references
A heuristic proposed by \textit{O. Ibarra} and \textit{C. Kim} [J. Assoc. Comput. Mach. 24, 280-289 (1977; Zbl 0382.90048)] for scheduling independent tasks on unrelated processors is analyzed. The heuristic may create a schedule which finishes in time m*OPT, where m is the number of processors, and OPT is the time used in the optimal schedule. This compares unfavorably with the heuristics described by \textit{E. Davis} and \textit{J. Jaffe} [ibid. 28, 721-736 (1981; Zbl 0472.68020)], which have worst-case behavior which is \(O(OPT*m^{0.5})\).
0 references
scheduling algorithm
0 references
heuristic
0 references
independent tasks
0 references
unrelated processors
0 references
worst-case behavior
0 references
0.8595007658004761
0 references
0.8342065811157227
0 references
0.8302362561225891
0 references
0.8167327046394348
0 references
