摘要翻译：
通过同时求解多个算法问题对实例，可以提高任意时间算法的性能。这些配对可能包括一个问题的不同实例（例如从不同的初始状态开始）、不同的算法（如果存在几个替代方案），或者相同算法的几次运行（对于非确定性算法）。本文提出了一种基于算法统计特性的最优调度策略设计方法。我们形式化地分析了进程共享资源的情况（单处理器模型），并给出了最优调度算法。我们从理论上和实证上分析了我们的调度算法在各种配送类型下的行为。最后，我们给出了将我们的调度算法应用于拉丁平方问题的实证结果。
---
英文标题：
《Optimal Schedules for Parallelizing Anytime Algorithms: The Case of
  Shared Resources》
---
作者：
L. Finkelstein, S. Markovitch, E. Rivlin
---
最新提交年份：
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中的材料。
--

---
英文摘要：
  The performance of anytime algorithms can be improved by simultaneously solving several instances of algorithm-problem pairs. These pairs may include different instances of a problem (such as starting from a different initial state), different algorithms (if several alternatives exist), or several runs of the same algorithm (for non-deterministic algorithms). In this paper we present a methodology for designing an optimal scheduling policy based on the statistical characteristics of the algorithms involved. We formally analyze the case where the processes share resources (a single-processor model), and provide an algorithm for optimal scheduling. We analyze, theoretically and empirically, the behavior of our scheduling algorithm for various distribution types. Finally, we present empirical results of applying our scheduling algorithm to the Latin Square problem.
---
PDF链接：
https://arxiv.org/pdf/1106.5269