We consider the problem
P}&;| prec},cij&;{0,1}|κ
of scheduling jobs with arbitrary processing times on
sufficiently many parallel processors subject to
series-parallel precedence constraints and 0/1-communication
delays in order to minimize a regular performance measure
κ. Such schedules without processor restrictions are
used for generating approximate solutions for a restricted
number of processors.
For unit time communication delays we derive polynomial
algorithms to construct optimal schedules when the
performance measure κ is the makespan or the average
weighted completion time. For n jobs and r precedence
constraints, the run times of these algorithms are
O(n+r) and O(n3), respectively.
On the other hand, both problems are shown to be NP-hard
in the same model for 0/1-communication delays.
