TS+BS混合算法及在Job Shop调度问题上的应用

摘要：

为解决较大规模的最小化完工时间Job Shop调度问题,在Tabu Search (TS)和Beam Search (BS)方法基础上,提出一种采用基于问题结构信息的搜索树生成方法和搜索策略的调度算法,该算法采用通过有选择地对解空间进行分枝和评估相应的分枝实现算法迭代的Beam Search机理,并利用局部搜索能力强的Tabu Search搜索算法进行各分枝的评估,进而确定适合Beam Search算法迭代的理想分枝,以降低Beam Search算法漏掉好解的可能性.并用40个最小化完工时间Job Shop调度问题的Benchmark实例进行了数值计算.计算结果表明,该算法效率高,解的性能令人满意,并适应于较大规模的调度问题.

关键词：Tabu Search方法、Beam Search方法、启发式规则、调度、Job Shop

所属期刊栏目：42

分类号：TP18;TP301.6(自动化基础理论)

资助基金：国家自然科学基金60004010;国家高技术研究发展计划863计划

在线出版日期：2004-01-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：424-426