并行多机成组工件调度的禁忌搜索方法

• 作者: 汪定伟 衣杨
• 来源期刊: 系统工程
• 学科: 数学
• 关键词: 生产调度 最优化 启发式算法 成组技术 并行多机 禁忌搜索
• 年，卷（期）: 2000,（6）
• 所属期刊栏目: 运筹学与管理
• 页码范围: 11-17
• 页数: 7页
• 分类号: O22
• 字数: 5208字
• 语种: 中文
• DOI: 10.3969/j.issn.1001-4098.2000.06.003

摘要

本文讨论的是并行多机成组工件的极小化最大通过时间调度问题.在没有GT假设下,它是一个非常复杂的组合优化问题,是NP难题.在本文中,为了解决此类问题,作者尝试采用了两种禁忌搜索的智能优化算法方法:1)利用单机条件下的最优解的性质,提出了禁忌搜索结合启发式的算法(TS-HEU);2)禁忌搜索结合分支定界法的算法(TS-B&B).作者作了大量的仿真实验,将两种方法进行了比较.实验结果证明:虽然两种算法都可以求解本问题,但是TS-HEU方法有更高的可靠性和快速的运算能力;它同时表明,虽然并行多机成组调度问题异常复杂,但禁忌搜索结合启发式的智能优化算法仍然有能力有效地解决大规模实际问题.