| 约束满足混合算法求解提前/拖期Job Shop调度问题 |
| |
| 引用本文： | 李俊芳,李铁克,王伟玲.约束满足混合算法求解提前/拖期Job Shop调度问题[J].计算机工程与应用,2010,46(16):12-15. |
| |
| 作者姓名： | 李俊芳 李铁克 王伟玲 |
| |
| 作者单位： | 北京科技大学 经济管理学院，北京 100083 |
| |
| 摘 要： | 针对提前/拖期Job Shop调度问题，建立其约束满足优化问题模型，提出了一种约束满足与禁忌搜索结合的混合算法。该算法基于约束满足思想，通过约束传播技术和启发式修复算法，得到可行调度作为禁忌搜索算法的初始解；再进行关键路径上的邻域变换，优化当前解；并采用一种全局邻域交换策略，扩大搜索空间，改善优化结果。数据实验表明了该混合算法的可行性和有效性。
|
| 关 键 词： | 约束满足 提前/拖期 Job Shop 禁忌搜索 关键路径 |
| 收稿时间： | 2010-1-26 |
| 修稿时间： | 2010-4-8
|
Hybrid constraint satisfaction algorithm for solving earliness/tardiness Job Shop scheduling problem |
| |
| LI Jun-fang,LI Tie-ke,WANG Wei-ling.Hybrid constraint satisfaction algorithm for solving earliness/tardiness Job Shop scheduling problem[J].Computer Engineering and Applications,2010,46(16):12-15. |
| |
| Authors: | LI Jun-fang LI Tie-ke WANG Wei-ling |
| |
| Affiliation: | School of Economics and Management，University of Science and Technology Beijing，Beijing 100083，China |
| |
| Abstract: | A constraint satisfaction optimization model is established for the problem of earliness/tardiness Job Shop scheduling problem.A hybrid algorithm combined with constraint satisfaction and tabu search is proposed.Based on constraint satisfaction,an entirely feasible scheduling is obtained by constraint propogation technology and heuristic repair method and is regarded as initial solution for tabu search algorithm.Current solution is optimized by neighborhood transformation on a critical path.The final optimizal solution is improved by adopting a global neighborhood swapping strategy.The data experiments show that the hybrid algorithm is feasible and effective. |
| |
| Keywords: | constraint satisfaction earliness/tardiness Job Shop tabu algorithm critical path |
| 本文献已被 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载全文 |
