Corollary 7.12 MINIMUM PARALLEL DEORDERING cannot approximate MINIMUM PAR-
ALLEL REORDERING within | | k for any constant > 0 even when the problems are restricted to GT plans with only positive preconditions and under the assumption of simple concurrency.

It may, thus, appear as though minimum reordering is a preferable, albeit more costly, operation than minimum deordering. However, if the plan modification is to be followed by scheduling, it is no longer obvious that a reordering is to prefer. Since scheduling may take further information and constraints into account, eg upper and lower bounds on the release time and limited resources, a feasible schedule for the original plan may no longer be a feasible schedule for a reordering of the same plan. That is, some or all feasible solutions may be lost when reordering a plan. In contrast to this, deordering a plan is harmless since all previously feasible schedules are preserved in the deordering.  Of course, the de¬
/reordered plan may have new and better schedules than the old plan, which is why the problems studied in this article are interesting at all. However, while minimum deordering is a safe and, usually cheap, operation, minimum reordering is neither and must thus be applied with more care. To find a reordering of a plan with an optimum schedule would require combining minimum reordering and scheduling into one single computation, but it is out of the scope of this article to study such combinations. Suffice it to observe that such a computation is never cheaper than either of its constituent computations.

## 8. Related Work

This section analyses and discusses some algorithms suggested in the literature for generalising the ordering of a plan, in addition to the PRF algorithm already analysed in the preceeding section.  Also some planners that generate plans with some optimality flavour on the ordering are discussed.

Some of the algorithms to be analysed use the common trick of simulating the initial state and the goal of a planning instance by two extra operators, in the following way. Let be a plan and Π =
a PPI, both in the GT language. Introduce two extra actions I, with pre( I ) = 0 and post( I ) = 1 and G, with pre( G ) =
and post( c) = 0.

Define the plan
' where '=
l I G
COLOGICAL
w that is   is ordered before all other actions and   G is ordered after all other actions. The is a representation of both the plan and the PPI Π . Such a combined representation plan will be referred to as a self-contained plan. A self-contained plan is valid iff it is valid wrt.

to the PPI  Ø . It is trivial to convert a plan and a PPI into a corresponding self-contained plan and vice versa. Hence, both ways of representing a plan will be used alternately without further notice.

## 8.1 The Vpc Algorithm

Veloso et al. (1990) have presented an algorithm (here referred to as VPC 5 ) for converting t.o. plans into 'least-constrained' p.o. plans.  They use the algorithm in the following context.

First a total-order planner (NOLIMIT) is used to produce a t.o. plan. VPC converts this plan 5. In the original publication the algorithm was named Build Partial Order.