Worst-case analysis of a scheduling algorithm

DOI10.1016/0167-6377(85)90043-4MaRDI QIDQ1060946zbMATH OpenOpenAlexFDO

Authors Jeremy P. Spinrad

Publication date 1985

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-6377(85)90043-4

zbMATH Keywords

heuristicindependent tasksscheduling algorithmunrelated processorsworst-case behavior

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Deterministic scheduling theory in operations research (90B35)

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})\).

Recommendations

• Scheduling Independent Tasks on Uniform Processors
• scientific article; zbMATH DE number 3898232
• On the worst-case ratio of a compound multiprocessor scheduling algorithm
• APPROXIMATE AND EXACT ALGORITHMS FOR SCHEDULING INDEPENDENT TASKS ON UNRELATED PROCESSORS
• Evaluation of a MULTIFIT-based scheduling algorithm

Cites work

• Algorithms for Scheduling Tasks on Unrelated Processors
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Scheduling independent tasks to reduce mean finishing time

Cited in

(6)

• Worst-case analysis of heuristics for the local microcode optimization problem
• Worst-case analysis of scheduling heuristics of parallel systems
• Unrelated parallel machine scheduling using local search
• Heuristic methods and applications: A categorized survey
• Heuristics for scheduling unrelated parallel machines
• Scheduling Independent Tasks on Uniform Processors

This page was built for publication: Worst-case analysis of a scheduling algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1060946)