摘要
为解决较大规模的最小化完工时间 Job Shop调度问题 ,在 Tabu Search(TS)和 Beam Search(BS)方法基础上 ,提出一种采用基于问题结构信息的搜索树生成方法和搜索策略的调度算法 ,该算法采用通过有选择地对解空间进行分枝和评估相应的分枝实现算法迭代的 Beam Search机理 ,并利用局部搜索能力强的 Tabu Search搜索算法进行各分枝的评估 ,进而确定适合 Beam Search算法迭代的理想分枝 ,以降低 Beam Search算法漏掉好解的可能性。并用 4 0个最小化完工时间 Job Shop调度问题的 Benchm ark实例进行了数值计算。计算结果表明 ,该算法效率高 ,解的性能令人满意 。
A scheduling algorithm using search tree creation and a search policy based on the problem structure information is proposed for solving larger scale Job Shop problems by minimizing the makespan using a tabu search and a beam search. The beam search mechanism for the algorithm iteration selectively divaricates the solution space and selectively evaluaties the corresponding divisions. The tabu search with a strong local search is used to evaluate each division to determine the ideal divisions suitable for the Beam Search iteration to reduce the possibility of the Beam Search cutting off good solutions. Numerical results with 40 benchmark examples of Job Shop problems minimizing the makespan show that the algorithm is efficient and that the solution quality is satisfactory so the algorithm is suitable for large scale scheduling problems.
出处
《清华大学学报（自然科学版）》
EI
CAS
CSCD
北大核心
2002年第3期424-426,共3页
Journal of Tsinghua University(Science and Technology)
基金
国家自然科学基金资助项目 (60 0 0 40 10 )
国家"八六三"高技术项目
