[comp.theory] Polynomial time scheduling algos.

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.