This paper considers scheduling problems with timing constraints
of the forms < (precedence), (no later than),
and (concurrence). Scheduling unittime jobs subject to
< and constraints, and scheduling unittime jobs
subject to constraints, are proved NPcomplete for fixed
k 3 processors. (This contrasts with the case of just
< constraints, which is a famous open problem.) We then show
that a modified version of Gabow's linear time 2processor
scheduling algorithm can optimally handle all three types of
constraints. Linear time and NC algorithms for optimally
scheduling with any subset of {<, , }
constraints are thus obtained for k = 2 processors.
Approximation results for k ≥ 3 processors are also
obtained. Finally, we consider a problem that arises in practice
on the Tera architecture, proving an NPcompleteness result and
providing an approximation algorithm.
