清华大学学报(自然科学版)
清華大學學報(自然科學版)
청화대학학보(자연과학판)
Journal of Tsinghua University
2002年
3期
424-426
,共3页
Tabu Search方法%Beam Search方法%启发式规则%调度%Job Shop
Tabu Search方法%Beam Search方法%啟髮式規則%調度%Job Shop
Tabu Search방법%Beam Search방법%계발식규칙%조도%Job Shop
为解决较大规模的最小化完工时间Job Shop调度问题,在Tabu Search (TS)和Beam Search (BS)方法基础上,提出一种采用基于问题结构信息的搜索树生成方法和搜索策略的调度算法,该算法采用通过有选择地对解空间进行分枝和评估相应的分枝实现算法迭代的Beam Search机理,并利用局部搜索能力强的Tabu Search搜索算法进行各分枝的评估,进而确定适合Beam Search算法迭代的理想分枝,以降低Beam Search算法漏掉好解的可能性.并用40个最小化完工时间Job Shop调度问题的Benchmark实例进行了数值计算.计算结果表明,该算法效率高,解的性能令人满意,并适应于较大规模的调度问题.
為解決較大規模的最小化完工時間Job Shop調度問題,在Tabu Search (TS)和Beam Search (BS)方法基礎上,提齣一種採用基于問題結構信息的搜索樹生成方法和搜索策略的調度算法,該算法採用通過有選擇地對解空間進行分枝和評估相應的分枝實現算法迭代的Beam Search機理,併利用跼部搜索能力彊的Tabu Search搜索算法進行各分枝的評估,進而確定適閤Beam Search算法迭代的理想分枝,以降低Beam Search算法漏掉好解的可能性.併用40箇最小化完工時間Job Shop調度問題的Benchmark實例進行瞭數值計算.計算結果錶明,該算法效率高,解的性能令人滿意,併適應于較大規模的調度問題.
위해결교대규모적최소화완공시간Job Shop조도문제,재Tabu Search (TS)화Beam Search (BS)방법기출상,제출일충채용기우문제결구신식적수색수생성방법화수색책략적조도산법,해산법채용통과유선택지대해공간진행분지화평고상응적분지실현산법질대적Beam Search궤리,병이용국부수색능력강적Tabu Search수색산법진행각분지적평고,진이학정괄합Beam Search산법질대적이상분지,이강저Beam Search산법루도호해적가능성.병용40개최소화완공시간Job Shop조도문제적Benchmark실례진행료수치계산.계산결과표명,해산법효솔고,해적성능령인만의,병괄응우교대규모적조도문제.
