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}\kappa 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 kappa. 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 other hand, both problems an shown to be NP-hard in the same model for 0/1-communication delays. (C) 1999 Elsevier Science B.V. All rights reserved.
scheduling series-parallel orders unit communication delays