Proof of the 4/3 conjecture for preemptive vs. nonpreemptive two-processor scheduling

DOI10.1145/174147.174148zbMath0794.68015OpenAlexW2066045289WikidataQ123265821 ScholiaQ123265821MaRDI QIDQ4285627

Michael R. Garey, Edward G. jun. Coffman

Publication date: 17 April 1994

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/174147.174148

zbMATH Keywords

preemptive schedulingmakespan scheduling

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Parallel algorithms in computer science (68W10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items

The maximum gain of increasing the number of preemptions in multiprocessor scheduling, A model for minimizing active processor time, Algorithms with limited number of preemptions for scheduling on parallel machines, The n-dimensional Stern–Brocot tree, Preemptive scheduling for approximate computing on heterogeneous machines: tradeoff between weighted accuracy and makespan