

![0_image_0.png](0_image_0.png)

$$\begin{array}{l l l l l l l}{{1.}}&{{i f}}&{{}}&{{}}&{{,\;t h e n}}&{{\left(\begin{array}{l}{{}}\end{array}\right)+}}&{{\left(\begin{array}{l}{{}}\end{array}\right)}}&{{}}&{{\left(\begin{array}{l}{{}}\end{array}\right)\;\;a n d}}\end{array}$$
 $\textit{2.if}\ \ \#\ \text{,}\ then\ \textit{either}$  $\begin{array}{cccccc}&(a)&(&)+&(&)&&(&)\ or\\ &(b)&(&)+&(&)&&(&).\end{array}$  . 
The length of the parallel execution is defined as maxaEA ( ) + ( ) , ie, the latest finishing time of any action.  A minimum parallel execution of plan is a parallel execution with minimum length among all parallel executions of the plan.  The length of a parallel plan denoted length(  ), is the length of the minimum parallel execution(s) for Obviously, every parallel plan has a parallel execution of length ∑ α∈ A  ( ) (which is the trivial case of sequential execution). Furthermore, in certain cases, hardness results will be strengthened by restricting the duration function.

Definition 5.5 The special case where  ( ) = 1 for all   E
is referred to as the unit time assumption.

Deciding whether a release-time function is a parallel execution is tractable.

Theorem 5.6  Given a parallel plan    =
\# , a duration function  :
→ N and a release-time function   : 
is a parallel execution for and, in the case it is, what the length of this execution is.

Proof:  Trivial.

口 Consider the plan in Figure 8 and three release-time functions 1, 2 and 3, defined as follows

= 2 2 ( ) = 1 ) = 2 3 ) = 1 3 3 ) = 2
Both 1 and 2 are parallel executions of the plan, while 3 is not. Furthermore, 2 is a minimum parallel execution for the plan, having length 2.  However, computing the minimum parallel execution of a parallel plan is difficult in the general case.