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

摘要

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