Thumbnail Image

Scheduling Series-Parallel Orders Subject to 0/1-Communication Delays

Möhring, Rolf H.; Schäffter, Markus W.

Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin

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.