摘要翻译：
本文研究了如何修改计划的动作顺序，以便根据不同的准则对计划进行优化。其中一个准则是使计划的约束更少，另一个准则是使其并行执行时间最小化。为第一个准则提出了三个候选定义，构成了一系列递增的最优性保证。其中两个是基于去排序计划，这意味着排序关系只能被删除，不能被添加，而第三个使用重新排序，其中允许对排序进行任意修改。结果表明，在这三个判据中，只有最弱的一个判据是易于实现的，其他两个判据是NP困难的，甚至难以近似。同样地，研究了计划的并行执行时间的优化问题，包括计划的排序问题和计划的重排序问题。在一般情况下，这两种计算都是NP难的。然而，对于一类基于生产者、消费者和威胁概念的规划语言，它包含了大多数常用的规划语言，它可以在多项式时间内计算出最优解。计算最优重排序可能会导致更快的并行执行，但即使在相当严格的限制下，这个问题仍然是NP困难的，很难逼近。
---
英文标题：
《Computational Aspects of Reordering Plans》
---
作者：
C. Backstrom
---
最新提交年份：
2011
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Artificial Intelligence        人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--

---
英文摘要：
  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 sequence 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 third one uses reordering, where arbitrary modifications to the ordering are allowed. It is shown that only the weakest one of the three criteria is tractable to achieve, the other two being NP-hard and even difficult to approximate. Similarly, optimising the parallel execution time of a plan is studied both for deordering and reordering of plans. In the general case, both of these computations are NP-hard. However, it is shown that optimal deorderings can be computed in polynomial time for a class of planning languages based on the notions of producers, consumers and threats, which includes most of the commonly used planning languages. Computing optimal reorderings can potentially lead to even faster parallel executions, but this problem remains NP-hard and difficult to approximate even under quite severe restrictions.
---
PDF链接：
https://arxiv.org/pdf/1105.5441