| BAB算法中集成CPT求解job-shop调度问题 |
| |
| 引用本文： | 冯欣,唐立新,王梦光.BAB算法中集成CPT求解job-shop调度问题[J].管理科学,2005,8(3):81-89. |
| |
| 作者姓名： | 冯欣 唐立新 王梦光 |
| |
| 作者单位： | 东北大学信息科学与工程学院,沈阳,110004 |
| |
| 基金项目： | 国家自然科学基金资助项目(70171030;60274049);高等学校优秀青年教师教学科研奖励计划资助项目(教人司[002]383);霍英东青年教师基金资助项目(81073). |
| |
| 摘 要： | CSP(constraintsatisfactoryproblem)的优势在于能够处理复杂约束,获得一个满足约束的解,但难以保证解的质量.OR(operationresearch)的优点是获得最优解或近优解,但它求解复杂约束的优化问题非常困难.CPT(constraintpropagationtechnique)是CSP的主要搜索技术,BAB(branch_and_bound)是OR常用的优化算法.提出了一种将CPT集成于BAB中的混合算法,从一个新的角度解决具有一般性与挑战性的job shop调度问题.其主要特点是,通过在BAB算法中嵌入动态可调的时间窗口约束和加强一致性CPT搜索方法,融合BAB的优化能力和CPT处理复杂约束的能力,提高BAB的优化性能及实际应用能力.实验结果令人满意,证明了算法的有效性.
|
| 关 键 词： | 约束传播技术 分支定界算法 jobshop调度 |
| 文章编号： | 1007-9807(2005)03-0081-09 |
| 修稿时间： | 2003年5月9日 |
Integrating CPT into BAB algorithm for job shop scheduling |
| |
| FENG Xin,TANG Li-xin,WANG Meng-guang.Integrating CPT into BAB algorithm for job shop scheduling[J].Management Sciences in China,2005,8(3):81-89. |
| |
| Authors: | FENG Xin TANG Li-xin WANG Meng-guang |
| |
| Abstract: | CSP (constraint satisfactory problem) has the advantage of solving complicated constraints to obtain satisfying solutions, but does not guarantee the quality of the solution. In contrast, OR (operation research) has the advantage of obtaining optimization solution or near optimization solution. But it is very difficult to solve the optimization problems with complicated constraints. CPT (constraint propagation technique) is the main search approach of CSP. BAB (branch_and_bound) is one of the optimization a... |
| |
| Keywords: | constraint propagation techniques branch_and_bound job_shop scheduling |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《管理科学》浏览原始摘要信息 |
| 点击此处可从《管理科学》下载免费的PDF全文 |
|
