Scheduling seriesparallel orders subject to 0/1-communication delays1
We consider the problem P?|prec,cij?{0,1}|? of scheduling jobs with arbitrary processing times on sufficiently many parallel processors subject to seriesparallel 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 and , respectively. On the other hand, both problems are shown to be NP-hard in the same model for 0/1-communication delays.
scheduling seriesparallel orders unit communication delays