• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Conference on Automated Planning and Scheduling(ICAPS 2006); 2006; >Looking for Shortcuts: Infeasible Search Analysis for Oversubscribed Scheduling Problems
【24h】

Looking for Shortcuts: Infeasible Search Analysis for Oversubscribed Scheduling Problems

机译：寻找捷径：对超额预定问题的不可行搜索分析

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Searches that include both feasible and infeasible solutions have proved to be efficient algorithms for solving some scheduling problems. Researchers conjecture that these algorithms yield two primary benefits: 1) they tend to focus on solutions close to the boundary between feasible and infeasible solutions, where active constraints are likely to yield optimal values, and 2) moves that include infeasible solutions may uncover short-cuts in a search space. Researchers have published empirical studies that confirm the value of searching along the feasible-infeasible boundary, but until now there has been little direct evidence that in-feasible search yields short-cuts. We present empirical results in two oversubscribed scheduling domains for which boundary region search in infeasible space appears to offer advantages over search in strictly feasible space. Our results confirm that infeasible search finds shortcuts that may improve search efficiency more than boundary region search alone. However, our results also reveal that inefficient infeasible paths which we call detours may degrade search performance, potentially offsetting efficiency shortcuts may provide.
机译：包含可行和不可行解决方案的搜索已被证明是解决某些调度问题的有效算法。研究人员推测，这些算法可带来两个主要好处：1）他们倾向于将重点放在可行和不可行解决方案之间的边界附近的解决方案上，其中主动约束可能会产生最佳值； 2）包含不可行解决方案的举措可能会发现削减搜索空间。研究人员已经发表了实证研究，证实了沿着可行-不可行边界进行搜索的价值，但是直到现在，几乎没有直接证据表明，不可行搜索会产生捷径。我们在两个超额预定的调度域中给出了实证结果，对于这些域，在不可行空间中进行边界区域搜索似乎比在严格可行空间中进行搜索更具优势。我们的结果证实，不可行的搜索找到的捷径比单独的边界区域搜索更能提高搜索效率。但是，我们的结果还表明，我们称之为绕行的效率低下的不可行路径可能会降低搜索性能，从而可能会抵消效率捷径。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号