Worst-case analysis of a scheduling algorithm
type: Item
instance of: scholarly article
title: Worst-case analysis of a scheduling algorithm
zbMATH Open document ID: 0569.90045
DOI: 10.1016/0167-6377(85)90043-4
published in: Operations Research Letters
publication date: 1985-01-01T00:00:00Z
review text: 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})\).
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 65K05
zbMATH DE Number: 3910119
zbMATH Keywords: scheduling algorithm
zbMATH Keywords: heuristic
zbMATH Keywords: independent tasks
zbMATH Keywords: unrelated processors
zbMATH Keywords: worst-case behavior
author: Jeremy P. Spinrad
MaRDI profile type: Publication
full work available at URL: 0167-6377(85)90043-4
OpenAlex ID: W2075962074
cites work: Scheduling independent tasks to reduce mean finishing time
cites work: Algorithms for Scheduling Tasks on Unrelated Processors
cites work: Q4198056
cites work: Exact and Approximate Algorithms for Scheduling Nonidentical Processors
cites work: Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors
description: scientific article; zbMATH DE number 3910119