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

• 作者: 刘民 吴澄 孙元凯
• 来源期刊: 清华大学学报(自然科学版)
• 学科: 工学
• 关键词: Tabu Search方法 Beam Search方法 启发式规则 调度 Job Shop
• 年，卷（期）: 2002,（3）
• 所属期刊栏目: 自动化
• 页码范围: 424-426
• 页数: 3页
• 分类号: TP18|TP301.6
• 字数: 3381字
• 语种: 中文
• DOI: 10.3321/j.issn:1000-0054.2002.03.038

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	吴澄	清华大学自动化系	125	4840	34.0	67.0
2	刘民	清华大学自动化系	54	1195	17.0	33.0
3	孙元凯	清华大学自动化系	4	84	3.0	4.0