may have fewer parameters, in which case it may be much more efficient to solve them in isolation.  On the other hand, solving the whole problem at once may make it easier to do global optimisation. Which is the better will depend both on which methods are used and on various properties of the actual application, and it seems unlikely that one of the methods should always be the better.

As has been shown in this article, minimum reordering is a much better optimality criterion than minimum deordering, if only considering the overall parallel execution time. However, this is not necessarily true if also considering further metric constraints for subsequent scheduling. Deordering a plan can only add to the number of feasible schedules, while reordering may also remove some or, in the worst case, all feasible schedules. On the other hand, reordering may also lead to new and better schedules not reachable via deordering. Deordering can thus be viewed as a safe and, sometimes, cheap way to allow for better schedules, while reordering is an expensive method which has a potential for generating considerably better plans, but which may also make things worse. If using reordering in practice in cases where also metric scheduling constraints are involved, it seems necessary to use feedback from the scheduler to control the reordering process, or to try other reorderings.  One could imagine a reordering algorithm which uses either heuristic search or randomized local-search methods à la GSAT (Selman, Levesque, & Mitchell, 1992) to find reorderings and then use the seduler as evaluation function for the proposed reorderings.

While the plan modifications studied in this article may add considerably to the optimizations that are possible with traditional scheduling only, there is still a further potential of optimization left to study modifying not only the action order, but also the set of actions. Such modification is already done in plan adaptation, but then only for generating a new plan from old cases, and optimizations in the sense of this article are not considered.

Some preliminary studies of action-set modifications appear in the literature, though. Fink and Yang (1992) study the problem of removing redundant actions from total-order plans, defining a spectrum of redundancy criteria and analysing the complexity of achieving these.

It is less clear that it is interesting to study action addition; adding actions to a plan could obviously not improve the execution time of it if it is to be executed sequentially. However, in the case of parallel execution of plans it has been shown that adding actions to a plan can ssentimes allow for faster execution (Backstrom, 1994). Finally, if allowing both removal and addition of actions, an even greater potential for optimising plans seems available, but this problems seems not yet studied in the literature.

## 10. Conclusions

This article studies the problem of modifying the action ordering of a plan in order to optimise the plan according to various criteria.  One of these criteria is to make a plan less constrained and the other is to minimize its parallel execution time. Three candidate definitions are proposed for the first of these criteria, constituting a spectrum of increasing optimality guarantees. Two of these are based on deordering plans, which means that ordering relations may only be removed, not added, while the last one builds on reordering, where arbitrary modifications to the ordering are allowed. The first of the three candidates, ssssssssss