管理科学学报
管理科學學報
관이과학학보
JOURNAL OF MANAGEMENT SCIENCES IN CHINA
2005年
3期
81-89
,共9页
约束传播技术%分支定界算法%job-shop调度
約束傳播技術%分支定界算法%job-shop調度
약속전파기술%분지정계산법%job-shop조도
CSP(constraint satisfactory problem)的优势在于能够处理复杂约束,获得一个满足约束的解,但难以保证解的质量.OR(operation research)的优点是获得最优解或近优解,但它求解复杂约束的优化问题非常困难.CPT(constraint propagation technique)是CSP的主要搜索技术,BAB(branch-and-bound)是OR常用的优化算法.提出了一种将CPT集成于BAB中的混合算法,从一个新的角度解决具有一般性与挑战性的job-shop调度问题.其主要特点是,通过在BAB算法中嵌入动态可调的时间窗口约束和加强一致性CPT搜索方法,融合BAB的优化能力和CPT处理复杂约束的能力,提高BAB的优化性能及实际应用能力.实验结果令人满意,证明了算法的有效性.
CSP(constraint satisfactory problem)的優勢在于能夠處理複雜約束,穫得一箇滿足約束的解,但難以保證解的質量.OR(operation research)的優點是穫得最優解或近優解,但它求解複雜約束的優化問題非常睏難.CPT(constraint propagation technique)是CSP的主要搜索技術,BAB(branch-and-bound)是OR常用的優化算法.提齣瞭一種將CPT集成于BAB中的混閤算法,從一箇新的角度解決具有一般性與挑戰性的job-shop調度問題.其主要特點是,通過在BAB算法中嵌入動態可調的時間窗口約束和加彊一緻性CPT搜索方法,融閤BAB的優化能力和CPT處理複雜約束的能力,提高BAB的優化性能及實際應用能力.實驗結果令人滿意,證明瞭算法的有效性.
CSP(constraint satisfactory problem)적우세재우능구처리복잡약속,획득일개만족약속적해,단난이보증해적질량.OR(operation research)적우점시획득최우해혹근우해,단타구해복잡약속적우화문제비상곤난.CPT(constraint propagation technique)시CSP적주요수색기술,BAB(branch-and-bound)시OR상용적우화산법.제출료일충장CPT집성우BAB중적혼합산법,종일개신적각도해결구유일반성여도전성적job-shop조도문제.기주요특점시,통과재BAB산법중감입동태가조적시간창구약속화가강일치성CPT수색방법,융합BAB적우화능력화CPT처리복잡약속적능력,제고BAB적우화성능급실제응용능력.실험결과령인만의,증명료산법적유효성.
