• 主题
高级搜索  >
历史搜索 清空历史
首页> 美国政府科技报告 >Variable and Value Ordering Heuristics for Hard Constraint Satisfaction Problems:An Application to Job Shop Scheduling
【24h】

Variable and Value Ordering Heuristics for Hard Constraint Satisfaction Problems:An Application to Job Shop Scheduling

机译：硬约束满足问题的变量和值排序启发式算法：在作业车间调度中的应用

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Hard Constraint Satisfaction Problems (HCSPs) are Constraint SatisfactionProblems (CSPs) with very large search spaces and very few solutions. Real-life problems such as design or factory scheduling are examples of HCSPs. These problems typically involve several hundred (or even several thousand) variables, each with up to several hundred possible values, only a very tiny fraction of which ultimately allows for a satisfying solution. This paper addresses the issue of how to generate advice to decide which variable to instantiate next (i.e. variable ordering heuristics), and which value to assign to that variable (i.e. value ordering heuristics) in order to reduce search for a solution. Our investigation is conducted in the domain of job shop scheduling. It is shown that, in this domain, generic CSP heuristics are usually not sufficient to guide the search for a feasible solution. This is because these these heuristics fail to properly account for the tightness of constrain and/or the connectivity of the constraint graph.Instead, a probabilistic model of the search space is used to define new heuristics, which better account for these problem characteristics. Experimental results indicate that these new heuristics yield important improvements in both search efficiency and search time.

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号