Worst-case analysis of a scheduling algorithm (Q1060946): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0167-6377(85)90043-4 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2075962074 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Scheduling independent tasks to reduce mean finishing time / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Algorithms for Scheduling Tasks on Unrelated Processors / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4198056 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Exact and Approximate Algorithms for Scheduling Nonidentical Processors / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors / rank | |||
Normal rank |
Latest revision as of 17:24, 14 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Worst-case analysis of a scheduling algorithm |
scientific article |
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