BAB算法中集成CPT求解job-shop调度问题

• 作者: 冯欣 唐立新 王梦光
• 来源期刊: 管理科学学报
• 学科: 工学
• 关键词: 约束传播技术 分支定界算法 job-shop调度
• 年，卷（期）: 2005,（3）
• 所属期刊栏目: 论文
• 页码范围: 81-89
• 页数: 9页
• 分类号: TP29
• 字数: 5201字
• 语种: 中文
• DOI: 10.3321/j.issn:1007-9807.2005.03.011

摘要

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的优化性能及实际应用能力.实验结果令人满意,证明了算法的有效性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王梦光	东北大学信息科学与工程学院	64	2361	24.0	47.0
2	唐立新	东北大学信息科学与工程学院	106	2154	24.0	41.0
3	冯欣	东北大学信息科学与工程学院	4	15	2.0	3.0