求解Job-Shop约束满足问题的变量排序算法比较研究  

Variable Ordering for Job-shop Constraint Satisfaction Problems

作　　者：尹静[1] 李铁克[1] 

机构地区：[1]北京科技大学经济管理学院,北京100083

出　　处：《工业工程》2008年第4期113-117,共5页Industrial Engineering Journal

基　　金：国家自然科学基金资助项目(70771008)

摘　　要：针对约束满足求解技术中的变量排序,提出了量化Job-Shop调度问题特征的5项指标和相关参数。分别从约束连通度、变量约束偏差、约束紧度、规模及资源利用率偏差等角度设计异构算例对现有典型变量排序算法进行比较分析,实验结果明确了算法效果与问题特征之间的相对适应度,可为构造更有效的搜索策略提供参考。In order to employ variable ordering of constraint satisfaction technology, this paper presents five indexes as well as related parameters to describe the features of Job-shop scheduling problems. Several cases are designed to test typical kinds of variable ordering taking into account of problem sizes, constraint tightness, connectivity of constraint graphs, deviation of variable constraint quantity and resource utilization, which demonstrates the correlation of variable ordering to the features of problems.

关 键 词：JOB-SHOP问题 约束满足 变量排序 问题结构 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]