Counterexample to a conjecture of Fujii, Kasami and Ninomiya.

[摘要] 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.

[学科分类] 计算机科学（综合）