Making a plan least constrained is clearly useful if certain actions can be executed in parallel. However, even in the case where no parallel execution is possible, it may still be worth making a plan least constrained. Although the partial order of this least constrained plan must again be strengthened into a total order for execution purposes, this need not be the same total order as in the original plan. Suppose the actions have temporal constaints like deadlines and earliest release times and that a scheduler will post-process the plan to try finding a feasible schedule. It may then be the case that the original plan has no feasible schedule, but a less constrained version of it can be sequenced into a feasible schedule. The idea of a least constrained plan is that the scheduler will have as many alternative execution sequences as possible to choose from.

The most important reason for modifying the action ordering of a plan, however, is to execute the plan faster by executing actions in parallel whenever possible. For this purpose it is better to use the length of the optimal schedule for a plan as a measure, rather than some measure on the ordering itself. Suppose the following car-assembly plan is given 2 If the actions are executed sequentially in the given order, the minimum execution time is the sum of the durations of the actions, that is 29 time units. However, just as in the previous example this plan is over-constrained, since several of the actions could be executed in either order, or in parallel.

It is possible to remove orderings as far as shown in Figure 4a, but no further, and still have a valid plan (the implicit transitive orderings are not shown in the figure). This deordered version of the original assembly plan can be scheduled to execute in 25 time units by exploiting parallelism whenever possible. An example of such a schedule is shown in Figure 3b. However, no faster execution is possible, since the plan contains a subsequence of actions which cannot be parallelized and which has a total execution time of 25 time units.

It is obvious from the schedule in Figure 4b that not many actions can be executed in parallel, and that the gain of deordering the plan is quite small.  A much better performance is possible if arbitrary modifications to the action ordering are allowed, that is, if also reorderings are considered. For instance, in the assembly plan there is no particular reason why the wheels should be mounted before the top is mounted, and it will be seen shortly that much time can be saved by reversing the order of these two operations. A deordering cannot do this, however, since removing the ordering between the wheel-mounting action
(MtW) and the top-mounting action (MtT) would make these unordered. This would be interpreted as if the two actions could be executed in parallel, which is not possible. This is also the reason why these actions must be ordered in the original plan. However, when allowing arbitrary modifications, the order between these two actions can be reversed, and Figure 5a shows such a reordering of the original plan.  This plan can be scheduled to execute in only 16 time units, which is a considerable improvement over both the original plan and the optimal deordered version of it.  An example of an optimal schedule is shown in Figure 5b. In fact, this plan is an optimal reordering in the sense that no other ordering of the actions results in a valid plan that can be scheduled to execute faster. The problems of finding optimal deorderings and reorderings of plan with respect to parallel execution is the main topic of this article, and are studied in Sections 5 to 7.