sarnath@sybil.cs.Buffalo.EDU (Ramnath Sarnath) (04/12/91)
I am looking for restricted versions of multi-processor scheduling problems that are known to be solvable in polynomial time. I would appreciate any references to such work. sarnath
sam@cs.ed.ac.uk (S Manoharan) (04/16/91)
In article <70425@eerie.acsu.Buffalo.EDU> sarnath@sybil.cs.Buffalo.EDU (Ramnath Sarnath) writes: >I am looking for restricted versions of multi-processor scheduling >problems that are known to be solvable in polynomial time. >I would appreciate any references to such work. If I remember right, polynomial time algorithms are known only for two cases: when the task graph is a forest, and when there are only two processors available. I presume you meant optimal polynomial algorithms. See Coffman's "Computer & job shop scheduling theory". Manoharan.