Report Number: CS-TR-72-300
Institution: Stanford University, Department of Computer Science
Title: Counterexample to a conjecture of Fujii, Kasami and Ninomiya.
Author: Kaufman, Marc T.
Date: June 1972
Abstract: In a recent paper [1], Fujii, Kasami and Ninomiya presented a procedure for the optimal scheduling of a system of unit length tasks represented as a directed acyclic graph on two identical processors. The authors conjecture that the algorithm can be extended to the case where more than two processors are employed. This note presents a counterexample to that conjecture. [1] Fujii, M., T. Kasami and K. Ninomiya, "Optimal Sequencing of Two Equivalent Processors, SIAM J. Appl. Math., Vol. 17, No.4, July 1969, pp. 784-789.