摘要：CSP(constraint satisfactory problem)的优势在于能够处理复杂约束,获得一个满足约束的解,但难以保证解的质量.OR(operation research)的优点是获得最优解或近优解,但它求解复杂约束的优化问题非常困难.CPT(constraint propagation technique)是CSP的主要搜索技术,BAB(branch-and-bound)是OR常用的优化算法.提出了一种将CPT集成于BAB中的混合算法,从一个新的角度解决具有一般性与挑战性的job-shop调度问题.其主要特点是,通过在BAB算法中嵌入动态可调的时间窗口约束和加强一致性CPT搜索方法,融合BAB的优化能力和CPT处理复杂约束的能力,提高BAB的优化性能及实际应用能力.实验结果令人满意,证明了算法的有效性.

关键词：约束传播技术 分支定界算法 

单位：东北大学信息科学与工程学院; 沈阳; 110004