Stochastic Scheduling with Variable Profile and Precedence Constraints.
In this paper, we consider the stochastic profile scheduling problem of a partially ordered set of tasks on uniform processors. The set of available processors varies in time. The running times of the tasks are independent random variables with exponential distributions. We obtain a sufficient condition under which a list policy stochastically minimizes the makespan within the class of preemptive policies. This result allows us to obtain a simple optimal policy when the partial order is an interval order, an in-forest, or an out-forest.
Introduction
Consider the following scheduling problem. We are given a set of tasks to be run in a system
consisting of uniform processors (i.e., processors having different speeds). The executions of
these tasks must satisfy some precedence constraints which are described by a directed acyclic
graph, referred to as the task graph. The processing requirements of the tasks are independent
random variables with a common exponential distribution. The set of processors available to
these tasks varies in time. The availability of the processors is referred to as the profile, and
it can be arbitrary. The goal is to find preemptive schedules that stochastically minimize the
makespan.
Our study of scheduling under variable profile is motivated by situations where processors are
subject to failures and repairs. The failure and repair times are arbitrary. Another motivation
is scheduling of multiprogrammed systems. In such a system, execution of tasks of a program
may be preempted by tasks of higher-priority programs.
When the task graph is an in-forest, and the profile is a constant set of two processors,
Chandy and Reynolds [2] proved that the Highest Level First (HLF) policy minimizes the
expected makespan. Here, the level of a task is simply the distance from it to the root of the
tree in which it appears. Bruno [1] subsequently showed that HLF stochastically minimizes the
makespan when the system has two identical parallel processors. Pinedo and Weiss [14] extended
this last result to the case where tasks at different levels may have different expected task running
times. Frostig [7] further generalized the result of Pinedo and Weiss to include increasing
likelihood ratio distributions for the task running times. Recently, Kulkari and Chimento [9]
extended the result of [1] to the case of variable profile (with two identical parallel processors).
When the number of identical parallel processors in the system is arbitrarily fixed, and the task
running times have a common exponential distribution, Papadimitriou and Tsitsiklis [12] proved
that HLF is asymptotically optimal as the number of tasks tends to infinity.
Coffman and Liu [3] investigated the stochastic scheduling of out-forest on identical parallel
processors with constant profile. For a uniform out-forest where all subtrees are ordered by
an embedding relation (see definition in Section 4.3), they showed that an intuitive priority
scheduling policy induced by the embedding relation, referred to as the Most Successors (MS)
policy in this paper, stochastically minimizes the makespan when there are two processors. If,
in addition, the out-forest satisfies a uniform root-embedding constraint, then the greedy policy
stochastically minimizes the makespan on an arbitrary number of processors.
Papadimitriou and Yannakakis [13] studied the deterministic scheduling of interval-ordered
tasks. Under the assumptions of unit-execution-time and constant profile, they showed that for
an arbitrary number of identical processors, the simple list scheduling induced by the interval
order, still referred to as the MS policy in this paper, minimizes the makespan.
The notion of profile scheduling was first introduced by Ullman [16] and later by Garey et al.
[8] in the complexity analysis of deterministic scheduling algorithms. Dolev and Warmuth [4, 5, 6]
carried out various studies on the deterministic nonpreemptive profile scheduling with parallel
identical processors. In such a case, the profile is simply the number of available processors at
any time. When the tasks have unit-execution-time, Dolev and Warmuth obtained polynomial
algorithms for specific profiles (e.g., zigzag profile, bounded profile, etc.) and specific task graphs
(e.g., in-forest, out-forest, opposing forest, flat graph, etc. Some of their results were extended
to deterministic preemptive profile scheduling by Liu and Sanlaville [11].
In this paper, we investigate the profile scheduling in the stochastic setting with uniform
processors. The scheduling is allowed to be preemptive, the profile is arbitrary and may be
unknown a priori. We obtain a sufficient condition under which a list scheduling policy is
optimal among preemptive policies, such that the makespan is stochastically minimized. This
result allows us to prove the optimality of MS policy when the task graph has an interval order
structure, an in-forest structure or a uniform out-forest structure.
The results concerning interval-ordered tasks are new, even for constant profile and parallel
identical processors. The optimality of the MS policy extends the result of [9] for in-forests to
uniform processors, and the result of [3] for out-forests to variable profile and uniform processors.
Our paper is organized as follows. In Section 2, the scheduling problem is described in detail,
and some preliminaries are presented. In Section 3, a sufficient condition for a list scheduling
policy to stochastically minimize the makespan is established. In Section 4, this result is applied
to MS policies for the stochastic minimization of makespan for interval-order task graphs, in-
forests and uniform out-forests. Concluding remarks are provided in Section 5.
Problem Description and Preliminaries
A task graph E) is a directed acyclic graph, where is the set of vertices
representing the tasks, is the set of edges representing the precedence constraints:
implies that task i must complete execution before task j can start. Denote by p(i)
and s(i) the sets of immediate predecessors and successors of
A task without predecessors will be called initial task. Let S(i) be the set of (not necessarily
immediate) successors of
When necessary, notation SG (i) is used to indicate that S(i) is defined with respect to graph G.
Particular attention will be paid to the following three classes C i:o ; C i:f ; C o:f of task graphs.
interval order G 2 C i:o : Each vertex i corresponds to an interval b i in the real line such that
y.
in-forest Each vertex has at most one immediate successor: js(i)j  1,
vertex is called a leaf of in-forest G if is called a root of
in-forest G if
out-forest Each vertex has at most one immediate predecessor: jp(i)j  1,
vertex is called a leaf of out-forest G if is called a root of
out-forest G if
Four graphs belonging to these classes are illustrated in Figure 1. Graph 1 is an interval
order graph, with the associated collection of real intervals beside it. Graph 2 is an in-forest.
Graphs 3 and 4 are outforests.
Note that these classes of graphs have the following closure property: for all C 2 fC
fvg is the graph
obtained by deleting vertex v and its adjacent edges. This closure property (by deletion) will be
used in establishing our results.
The processing requirements of the tasks are independent and identically distributed (i.i.d.)
random variables with a common exponential distribution of a constant parameter, say 1. The
running time of a task is the processing requirement of the task divided by the speed of the
processor on which the task is running.
There are K  1 uniform processors, indexed by K. The speed of processor k,
denoted by ff k . The running times of tasks on processor k are thus i.i.d.
random variables with exponential distribution of parameter ff k . We assume, by convention,
that ff 1  ff 2  \Delta \Delta \Delta  ff K .
Figure

1: Examples of task graphs
The set of processors available to these tasks varies in time, due to, e.g., failures of the
processors or executions of higher-priority tasks. The availability of the processors is referred
to as the profile, and is specified by the sequence fa where the random variables
are the time epochs where the profile is changed, and M n ,
1, is a random set whose elements are the indices of the processors available during the
time interval [a n ; a n+1 ). The profile fa
n=1 is assumed to be independent of the running
times of the tasks. Without loss of generality, we assume that for all n  1, M n 6= ;. We will
also assume that the profile is not changed infinitely often during any finite time interval: for
there is some finite n  1 such that a n ? x. The profile is said to be bounded by
The scheduling policies decide when an enabled task, i.e., an unfinished task all of whose
predecessors have finished, should be assigned to an available processor. At any time, a task can
be assigned to at most one processor, and a processor can execute at most one task. Throughout
this paper, we assume that the scheduling policies are preemptive. We assume that the scheduler
has no information on the samples of the (remaining) processing requirements of the tasks. Let
\Psi denote the class of such policies. For any  2 \Psi, denote by (G) the makespan of the partially
ordered set of tasks G, i.e., the maximum of the completion times of the tasks in G.
The goal of the paper is to find policies in \Psi that stochastically minimize the makespan of
G. A policy  o is said to be optimal within a class C, if for any policy  2 \Psi,  st (G) for
all G 2 C, where the symbol  st refers to the standard stochastic inequality. Random variable
stochastically smaller than random variable Y 2 IR, denoted by X  st Y , if and only
if for any increasing function f IR, the inequality E[f(X)]  E[f(Y )] holds, provided
the expectations exist.
The proofs of our main results will use a coupling argument based on the following well-known
result due to Strassen, st denotes equality in distribution.
Lemma 2.1 (Strassen) Two random variables X;Y 2 IR satisfy X  st Y if and only if there
exist two random variables "
Y defined on a common probability space such that st "
X,
st
Y , and "
Y almost surely (a.s.
In order to simplify the proofs of the main results in the paper, we make some restrictions
on the class of policies \Psi.
Observe first that due to the memoryless property of exponential distributions, at any time,
the distribution of the remaining running time of a task assigned to processor k is still exponential
with parameter ff k , 1  k  K. If we represent the state of the system by the set of available
processors, the remaining task graph and the distributions of the remaining running times of
the tasks, then the state does not change between the instants of task completions and of
profile modifications. Therefore, we can, without loss of generality, confine ourselves to the
class of policies where preemptions and new task assignments occur only at the instants of
task completions and profile modifications. These instants are referred to as the decision epochs.
Hence, we assume that all the policies in \Psi make their scheduling decisions at these time instants
only.
A policy is idling if it allows a processor to remain idle when there is an initial task waiting for
execution. It is easy to see that an optimal policy should never be idling since the distributions
of the task running times have infinite support and preemptions are allowed. Furthermore, an
optimal policy should always use the fastest available processors (See [10] for a complete proof
of these basic properties). Throughout this paper, we will assume that all the policies in \Psi are
nonidling and use the fastest available processors at all decision epochs.
3 Optimal List Scheduling Policies
We will pay particular attention to a class of simple scheduling policies, referred to as list
schedules. A policy  is called a list schedule if for any task graph list
is defined on the set of tasks
means that task v i has higher priority than v j in the list. At any decision time epoch,
policy  assigns the enabled tasks with the highest priorities to the fastest available processors.
Clearly, all list schedules are in the class \Psi and satisfy the properties mentioned at the end of
last section. Note that the priority list can be changed dynamically, i.e., for a given policy, the
relative priority order between two tasks can be changed when a task is removed from the graph.
Let C be a class of graphs which is closed under deletion. The class C will be said to be
(p)-monotonic for some list schedule  and some p 2 IN+ , if for any G 2 C and any initial
tasks implies that for any profile bounded by p,
st
where recall that (G) denotes the makespan of G under schedule .
Observe that according to the definition, if C is (p)-monotonic then it is (p \Gamma 1)-monotonic.
Trivially, any class of graphs is (1)-monotonic for any list schedule . However, it will be seen
in the next section that few classes are (2)-monotonic for some list schedule .
Theorem 3.1 Let C be a class of graphs closed under deletion and (p)-monotonic for some
list schedule  and some p 2 IN+ . Then for any G 2 C, policy  stochastically minimizes the
makespan of G under any profile fa
n=1 bounded by p:
st (G): (1)
The proof of the theorem needs the following lemma.
Lemma 3.1 Let C be a class of graphs which is closed under deletion and is (p)-monotonic
for some list schedule  and some p 2 IN+ . Let G 2 C be a task graph, ; ae 2 \Psi two policies
of G which follow the priority list of  all the time except at the first decision epoch. At the
first decision epoch, policy  assigns tasks k to the available processors q
respectively, with, by assumption, Whereas policy ae assigns tasks
k to the processors q (1) ; q (2) respectively, where  is the permutation on
st (G):
Proof. If is identical to  so that the assertion trivially holds.
Assume that there are integers 1  such that q i ? q j . Let  1 be the permutation on
defined as follows:
be a policy which follows the priority list of  all the time except at the first
decision epoch. At the first decision epoch, policy ae 1 assigns tasks k to the processors
respectively. We will show that
st (G): (2)
We couple the running times on processors q in such a way that under both policies
and ae 1 , the running time on processor q n starting from time 0 is  n , 1  n  k. In such a
coupled model, the second decision epoch occurs at the same time under both policies. Let this
time epoch be fixed, referred to as d 2 ,
If this decision epoch corresponds to a profile modification, i.e., d st (G).
Assume now that the second decision epoch corresponds to a task completion. It is easy to
see that for any increasing function f
As C is (p)-monotonic, we have that st so that
Thus, the fact that q i ? q j (so that ff q i
implies that
Hence, for any increasing function f
which implies
st
Unconditioning on d 2 in the above relation yields (2).
Consider now policy ae 1 . If  then we are done. Otherwise, there are integers 1
be the permutation on f1; 2; defined as follows:
be a policy which follows the priority list of  all the time except at the first
decision epoch. At the first decision epoch, policy ae 2 assigns tasks k to the processors
respectively. As above, we can show that
st ae 1 (G):
Repeating this procedure for at most k(k \Gamma 1)=2 times yields finally policy ae such that
st st ae 2 (G)  st ae 1 (G)  st (G):
Proof of Theorem 3.1. We prove by induction on n that for any G = (V; E) 2 C such that
st (G) (5)
holds for any profile.
If G is a singleton, i.e., jV then (5) is trivial as both policies  and  assign the task
to the fastest available processor.
Assume that for some n  1, relation (5) holds for all G such that jV j  n. Consider now
the task graphs G 2 C such that jV
Fix the task graph G 2 C, the profile fa
n=1 , and the policy  2 \Psi. Denote by
n=1 the sequence of decision epochs of  for finishing tasks in G, with d
loss of generality, we assume that d 2 corresponds to a task completion. The other case can be
analyzed similarly.
Since all policies of \Psi are nonidling and use the fastest available processors, the numbers of
tasks assigned for execution at the first decision epoch are the same under policies  and . At
the first decision epoch, policy  assigns initial tasks k to the available processors
respectively, where Whereas policy  assigns initial tasks
to the processors q (1) ; q (2) respectively, where
and  is the permutation on f1; 2;
We construct an intermediate policy ae which follows the priority list of  all the time except
at the first decision epoch. At the first decision epoch, policy ae assigns tasks to
the processors q
According to Lemma 3.1, (G)  st ae(G). We show below that
st (G); (6)
which will complete the proof.
Under the assumption that d 2 corresponds to a task completion, we have that for any increasing
The definition of the list schedule  implies that
understood to be antisymmetric. Therefore, the (p)-monotonicity of G implies that
st
which, together with the inductive assumption, imply
st st
Therefore, cf. (7) and (8), E [f readily implies (6).
4 Optimality of Most-Successor Policies
A class of intuitively good list schedules is the Most-Successor (MS) policies, where the priority
of a task is defined by the number of (not necessarily immediate) successors, i.e., jS(u)j ? jS(v)j
implies u OE MS v. The difference between MS policies is the way ties are broken (the ways of
assigning priorities to tasks having the same number of successors). In this section we will show
that these policies are optimal for some special classes of task graphs, i.e., interval-order graphs,
in-forests and uniform out-forests.
In order to prove these optimality properties, we need to compare task graphs, which is done
using the following majorization. Let G be two task graphs,
with the vertices of
being ordered according to the
number of successors:
We say that G 1 is majorized by G 2 , denoted by G 1 OE s G 2 , if
In our proofs, the following equivalent definition will also be used. Let V 1 and V 2 be
partitioned into sets T 1
and T 2
In words, T j
k is the set of vertices having k successors in graph
G j . As an example, for the interval-order graph in Figure 1, T
6g. When the graph is an in-forest, T k is the set of vertices at level k. Now, the
equivalent definition is given as follows. Graph G 1 is majorized by G 2 if
4.1 Stochastic Profile Scheduling of Interval-Order Graphs
E) 2 C i:o be an interval-order graph. Note that except for a possible set of isolated
vertices (i.e. vertices without predecessors and without successors), an interval-order graph is
connected.
An equivalent definition of interval order graphs (cf. [13]) is that for all
immediate consequence of this definition is that if jS(i)j  jS(j)j,
then S(i) ' S(j), and consequently, if subset
contains vertices whose sets of successors are identical (and of
cardinality k).
Theorem 4.1 For any profile fa
n=1 and any set of interval-ordered tasks G 2 C i:o ,
st (G):
Proof. In view of Theorem 3.1, we only need to show that C i:o is MS(p)-monotonic for any
positive integer p, i.e., for any two initial tasks u; v of G, if jS(u)j  jS(v)j, then
st
fvg. We will show that there is a
common probability space such that
Applying further Strassen's Theorem (cf. Lemma 2.1) yields (10).
Owing to the memoryless property of the exponential distributions, we can consider a coupled
processing model where all processors are available, are continually
executing tasks. When a completion occurs, and there is no task assigned to that processor, it
corresponds to the completion of a fictitious task. When a task is assigned to a processor, it is
assigned a running time equal to the remainder of the running time already underway at that
processor. Thus, if tasks u are assigned to the same processor at some time,
they have the same (remaining) running time.
Denote by fc n g 1
n=1 the (increasing) sequence of completion times of the tasks in G 1 and G 2 at
the available processors under the MS policy. Let fd n g 1
n=1 be the superposition of the sequences
of the decision epochs of MS for G 1 and G 2 in such a probability space. More specifically,
n=1 is the superposition of the sequences of profile modification times fa n g 1
n=1 and of the
task completion times fc n g 1 n=1 . Clearly, d
For be the remaining graph of G j at time d n
under MS in the coupled model. Let
g, and n  1. We show that for all n  1,
which immediately implies (11).
Relation (12) is proved by induction on n. For is trivial that
Assume that (12) holds for some n  1.
Let there be m available processors at time d
. Without loss of generality, we assume that
the processors are available. Recall that by convention, these processors are ordered
by their speed: ff 1  ff 2
Under the MS policy, the initial tasks with the largest sets of successors are assigned to the
fastest processors. Let u be the tasks of G 1 (n) that are assigned to the processors
respectively, under the MS policy. Similarly, let m2 be the tasks of G 2 (n)
that are assigned to the processors respectively, under the MS policy. By definition,
If G 1 (n) is empty, then (12) trivially holds for n + 1. If the time epoch d n+1 corresponds to
a profile modification, then
so that relation (12) holds for n + 1. Assume now that G 1 (n) is not empty and that d n+1
corresponds to a completion at some processor, say processor h, 1  h  max(m
if any, belong to T 1
a (n), and v h , if any, belong to T 2
b (n). Tasks u h and/or v h finish at time d n+1 .
There are three cases to be investigated.
In this case, only task u h is finished. It is easy to see that
so that relation (12) holds for
Case 2: h  min(m
In this case, both tasks u h and v h are finished. There are two subcases:
Case 2.1: b  a.
It is simple that
Therefore, relation (12) holds for
Case 2.2: b ? a.
Observe first that
We examine the case a be the integers defined as follows:
Note that i 1 and i 2 are uniquely defined. Under the inductive assumption, one has that
For . Note that
1). According to the definitions, n k (i j ) is the
number of non-initial tasks of T j
k (n) in G j (n), g.
For all i, a so that there are at most h \Gamma 1 initial
tasks
(n). Thus
On the other hand, v implies that the h initial tasks are in T 2
Hence,
The above two inequalities together with the fact that n k (i 1 imply that
Therefore, for all i, a
which completes the proof of (12) for Case 2.2.
Case 3:
In this case, only task v h finishes.
It is clear that for all b
tasks of G 1 (n) are assigned to the available
processors, we obtain that for all i  b,
On the other hand, v implies that the h initial tasks are in T 2
Hence, for all i  b,
Inequalities (13) and (14) imply that
Therefore, for all i  b,
so that (12) holds for Case 3.
Therefore, by induction, relation (12) holds for all n  1. Consequently, MS(G 1 )
a:s: in that probability space.
4.2 Stochastic Profile Scheduling of In-Forest
E) 2 C i:f be an in-forest. A task of in-forest G is an initial task if and only if it is
a leaf of G. For any task, the number of its successors is equal to its level in the in-forest, i.e.
the distance from it to the root of the tree in which it appears (The level of the roots is zero by
convention). Thus, the MS policy coincides with the HLF policy.
Theorem 4.2 For any profile fa
n=1 bounded by 2, and for any in-forest G 2 C i:f ,
st (G): (15)
The proof of the theorem is similar to that of Theorem 4.1, using the fact that C if is MS(2)-
monotonic, and is omitted here. The reader is referred to [10] for a detailed proof.
Note that the above theorem generalizes the result of Kulkari and Chimento [9] to uniform
processors (with a different scheme of proof). Note also that such a result holds only when
2. Simple counterexamples can be found when there are three processors (see [2]).
4.3 Stochastic Profile Scheduling of Out-Forest
E) 2 C o:f be an out-forest. A task of out-forest G is an initial task if and only if it
is a root of G. Vertex v 2 V and all its successors is a subtree of G, denoted by TG (v) or simply
(v) when there is no ambiguity.
In general, MS policies are not optimal within the class of out-forests C o:f . Counterexamples
are provided in [3]. However, we will show that within the classes of uniform and r-uniform
out-forests (introduced in Coffman and Liu [3]), a policy is optimal if and only if it is MS.
be two out-trees. The out-tree T 2 is said to embed the out-tree T 1 , or
T 1 is embedded in is isomorphic to a subgraph of
there exists an injective function f from T 1 into T 2 such that
s(f(u)). The function f is called an embedding function.
Let r 1 and r 2 be the roots of the out-trees T 1 and T 2 , respectively. If T 2  e T 1 and if there
is an embedding function f such that f(r 1 is a root-embedding function, and we
An out-forest G 2 C o:f is said to be uniform (respectively r-uniform) if all its subtrees
can be ordered by the embedding (respectively root-embedding) relation. The
class of uniform (respectively r-uniform) out-forests is denoted by C u:o:f (respectively C r:o:f ).
It is clear that C r:o:f ae C u:o:f ae C o:f . In Figure 1, graph 3 is a uniform out-forest but not a
root-uniform out-forest. Graph 4 is a root-uniform out-forest.
The embedding relation is extended to uniform out-forests as follows. Let G
be two uniform out-forests. Denote by TG (v) the subtree of out-forest G
composed of v and all the successors of v in G. Assume that the vertices of G 1 and G 2 are
indexed in such a way that
Out-forest G 1 is embedded in G 2 , referred to as G 1 OE e G 2 , if and only if
Similarly, G 1 OE r G 2 if and only if
We will show that MS policies are optimal for uniform out-forests and profiles bounded by 2,
as well as for r-uniform out-forests and arbitrary profiles. In order to establish these optimality
properties, we first prove that C u:o:f (resp. C r:o:f ) is MS(2)-monotonic (resp. MS(p)-monotonic
for any positive integer p).
Observe that for any two roots u; v of a uniform out-forest G 2 C u:o:f (resp. r-uniform out-
forest only if jS(u)j  jS(v)j. Thus, for
any two subgraphs G 1 and G 2 of G which are obtained from deleting initial tasks of G, G 1 OE e G 2
only if G 1 OE s G 2 . This last property allows us to use the arguments of
Coffman and Liu [3] for the establishment of the following MS-monotonicities.
Lemma 4.1 Let G 2 C r:o:f be an arbitrary r-uniform forest, and u; v two roots of G such that
jS(u)j  jS(v)j. Then for any profile fa
n=1 bounded by 2,
st MS(G \Gamma fvg):
The proof of the above lemma is analogous to the proof of Theorem 1 of Coffman and Liu
[3]. Although the proof of Theorem 1 in [3] was given for constant profile and parallel identical
processors, the fact that both graphs G \Gamma fug and G \Gamma fvg are scheduled by an MS policy allows
us to use the same argument. The detailed proof is left to the interested reader.
Lemma 4.2 Let G 2 C r:o:f be an arbitrary r-uniform forest, and u; v two roots of G such that
jS(u)j  jS(v)j. Then for any profile fa
st MS(G \Gamma fvg):
The assertion of the lemma can be shown by mimicking the proof of Theorem 2 of Coffman
and Liu [3]. The detailed proof is omitted.
Applying now Theorem 3.1 yields
Theorem 4.3 For any profile fa
n=1 bounded by 2, and for any uniform out-forest G 2
st (G): (16)
Theorem 4.4 For any profile fa any r-uniform out-forest G 2 C r:o:f ,
st (G): (17)
Concluding Remaks
We have considered the scheduling problem for the stochastic minimization of the makespan
of task graphs under a variable profile. Under the assumption that task running times are
independent random variables with exponential distributions, we have established a general
condition for a list scheduling policy to stochastically minimize the makespan. This result has
allowed us to show the optimality of MS policies when the partial order is an interval order, or
an in-forest, or an out-forest.
We can further show that, except in the degenerate case where there is a single available
processor all the time, MS is the only optimal policy for the stochastic minimization of the
makespan. The reader is referred to [10] for details.
All results of the paper hold if the speed of the processors, as well as their availability,
is allowed to vary. The task assignment will change whenever the speed ratio between two
processors is reversed. Such an extension allows one to analyze systems with processor sharing
among different jobs (i.e. sets of tasks).

Acknowledgements

. We would like to thank the referees for various constructive
comments which helped to improve both the contents and the presentation of the paper.



--R

"On Scheduling Tasks with Exponential Service Times and In-Tree Precedence Constraints"
"Scheduling Partially Ordered Tasks with Probabilistic Execution Times"
"On the Optimal Stochastic Scheduling of Out-Forests"
"Scheduling Precedence Graphs of Bounded Height"
"Scheduling Flat Graphs"
"Profile Scheduling of Opposing Forests and Level Orders"
"A Stochastic Scheduling Problem with Intree Precedence Constraints"
"Scheduling Opposite Forests"
"Optimal Scheduling of Exponential Tasks with Intree Precedence Constraints on Two parallel Processors Subject to Failure And Repair"
" Stochastic Scheduling With Variable Profile And Precedence Con- straints"

"On Stochastic Scheduling with In-Tree Precedence Constraints"
"Scheduling Interval-Ordered Tasks"
"Scheduling Jobs with Exponentially Distributed Processing Times and Intree Precedence Constraints on Two Parallel Machines"
"The Existence of Probability Measures with Given Marginals"
"NP-Complete Scheduling Problems"
--TR
stochastic scheduling;profile scheduling;stochastic ordering;makespan;precedence constraint;interval order;uniform processors;out-forest;in-forest