In parallel and distributed computing scheduling low level tasks
on the available hardware is a fundamental problem.
Traditionally, one has assumed that the set of tasks to be executed
is known beforehand.
Then the scheduling constraints are given by a precedence graph.
Nodes represent the elementary tasks and edges the dependencies among
tasks. This static approach is not appropriate in situations
where the set of tasks is not known exactly in advance,
for example, when different options how to continue a program may
be granted.

In this paper a new model for parallel and distributed programs,
the dynamic process graph, will be introduced, which
represents all possible executions of a program in a compact way.
The size of this representation is small -- in many cases
only logarithmically with respect to the size of any execution.
An important feature of our model is that
the encoded executions are directed acyclic graphs
having a "regular" structure that is typical of parallel programs.

Dynamic process graphs embed constructors for parallel programs,
synchronization mechanisms as well as conditional branches.
With respect to such a compact representation we investigate the
complexity of different aspects of the scheduling problem:
the question whether a legal schedule exists at all and how to find
an optimal schedule. Our analysis takes into account communication
delays between processors exchanging data.

Precise characterization of the computational complexity of various
variants of this compact scheduling problem will be given
in this paper. The results range from easy, that is NL-complete,
to very hard, namely NEXPTIME-complete.