Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!cs.utexas.edu!uunet!mcsun!ukc!edcastle!cs.ed.ac.uk!sam
From: sam@cs.ed.ac.uk (S Manoharan)
Newsgroups: comp.theory
Subject: Re: Polynomial time scheduling algos.
Message-ID: <8911@skye.cs.ed.ac.uk>
Date: 15 Apr 91 20:46:31 GMT
References: <70425@eerie.acsu.Buffalo.EDU>
Sender: nnews@cs.ed.ac.uk
Reply-To: sam@lfcs.ed.ac.uk (S Manoharan)
Organization: Department of Computer Science, University of Edinburgh
Lines: 11

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.