南开大学学报(自然科学版)
南開大學學報(自然科學版)
남개대학학보(자연과학판)
ACTA SCIENTIARUM NATURALIUM UNIVERSITATIS NANKAIENSIS(NATURAL SCIENCE EDITION)
2006年
1期
36-42
,共7页
调度%维护%启发式算法%分枝定界算法
調度%維護%啟髮式算法%分枝定界算法
조도%유호%계발식산법%분지정계산법
讨论了带有可控性维护的单机调度问题,目标是实现工件加权完成时间和的最小化.此问题是强NP难的,因此给出了三个启发式算法和一个分枝定界算法,并通过实验对这些算法进行评价.实验结果表明其中的两个启发式算法(WSPT算法和综合算法)能得到比较好的近似最优解,分枝定界算法对小规模(n≤10)的问题很容易得到最优解.
討論瞭帶有可控性維護的單機調度問題,目標是實現工件加權完成時間和的最小化.此問題是彊NP難的,因此給齣瞭三箇啟髮式算法和一箇分枝定界算法,併通過實驗對這些算法進行評價.實驗結果錶明其中的兩箇啟髮式算法(WSPT算法和綜閤算法)能得到比較好的近似最優解,分枝定界算法對小規模(n≤10)的問題很容易得到最優解.
토론료대유가공성유호적단궤조도문제,목표시실현공건가권완성시간화적최소화.차문제시강NP난적,인차급출료삼개계발식산법화일개분지정계산법,병통과실험대저사산법진행평개.실험결과표명기중적량개계발식산법(WSPT산법화종합산법)능득도비교호적근사최우해,분지정계산법대소규모(n≤10)적문제흔용역득도최우해.