Scheduling series-parallel orders subject to 0/1-communication delays

We consider the problem P infinity\prec, c(ij) is an element of {0, 1}\kapp a of scheduling jobs with arbitrary processing times on sufficiently many p arallel processors subject to series-parallel precedence constraints and 0/ 1-communication delays in order to minimize a regular performance measure k appa. 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 kappa 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(n(3)), respectively. On the o ther hand, both problems an shown to be NP-hard in the same model for 0/1-c ommunication delays. (C) 1999 Elsevier Science B.V. All rights reserved.