##
Parallel Processor Scheduling with Delay Constraints

**
Daniel W. Engels, Jon Feldman, David R. Karger and Matthias Ruhl
**
*
ACM-SIAM Symposium on Discrete Algorithms (SODA '01)*

Washington D.C., January 2001

[Postscript, 154KB]

[PDF, 83KB]

### Abstract

We consider the problem of scheduling unit-length jobs on identical
parallel machines such that the makespan of the resulting schedule
is minimized. Precedence constraints impose a partial order on the
jobs, and both communication and precedence delays impose relative
timing constraints on dependent jobs. The combination of these two
types of timing constraints naturally models the instruction
scheduling problem that occurs during software compilation for
state-of-the-art VLIW (Very Long Instruction Word) processors and
multiprocessor parallel machines.

We present the first known polynomial-time algorithm for the case
where the precedence constraint graph is a forest of in-trees (or a
forest of out-trees), the number of machines *m* is fixed, and
the delays (which are a function of both the job pair and the
machines on which they run) are bounded by a constant *D*.

Our algorithm relies on a new structural theorem for scheduling
jobs with arbitrary precedence constraints. Given an instance with
many independent dags, the theorem shows how to convert, in linear
time, a schedule *S* for only the largest dags into a complete
schedule that is either optimal or has the same makespan as
*S*.

Back to publications