It is shown that the Precedence Constrained K-Processor Scheduling pro
blem is hard for the parameterized complexity class W[2]. This means t
hat there does not exist a constant c, such that for all fixed K, the
Precedence Constrained K-Processor Scheduling problem can be solved in
0(n(C)) time, unless an unlikely collapse occurs in the parameterized
complexity hierarchy. That is, if the problem can be solved in polyno
mial time for each fixed K, then it is likely that the degree of the r
unning time polynomial must increase as the number of processors K inc
reases.