This paper considers scheduling problems with timing constraints of the forms < (precedence), (no later than), and (concurrence). Scheduling unit-time jobs subject to < and constraints, and scheduling unit-time jobs subject to constraints, are proved NP-complete 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 2-processor 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 NP-completeness result and providing an approximation algorithm.