数学研究
數學研究
수학연구
JOURNAL OF MATHEMATICAL STUDY
2010年
2期
198-205
,共8页
运筹学%排序%启发式算法%性能指标%多组工件%通用机与专用机
運籌學%排序%啟髮式算法%性能指標%多組工件%通用機與專用機
운주학%배서%계발식산법%성능지표%다조공건%통용궤여전용궤
研究的目的在于解决实践中对多组任务的优化排序同题,即在最短的时间内完成所有给定的任务,由于这类问题往往都是NP完全同题,人们通常寻求其近似算法.文中提出了一种改进的LPT算法,利用"首先空闲"准则,讨论了将n组工件安排在n台速度不同的专用机,m台速度小于专用机的通用机上的Cmax问题,得到了利用该近似算法所得的解T与最优解T*的-个估计:T/T* ≤2+n-2/m+1.
研究的目的在于解決實踐中對多組任務的優化排序同題,即在最短的時間內完成所有給定的任務,由于這類問題往往都是NP完全同題,人們通常尋求其近似算法.文中提齣瞭一種改進的LPT算法,利用"首先空閒"準則,討論瞭將n組工件安排在n檯速度不同的專用機,m檯速度小于專用機的通用機上的Cmax問題,得到瞭利用該近似算法所得的解T與最優解T*的-箇估計:T/T* ≤2+n-2/m+1.
연구적목적재우해결실천중대다조임무적우화배서동제,즉재최단적시간내완성소유급정적임무,유우저류문제왕왕도시NP완전동제,인문통상심구기근사산법.문중제출료일충개진적LPT산법,이용"수선공한"준칙,토론료장n조공건안배재n태속도불동적전용궤,m태속도소우전용궤적통용궤상적Cmax문제,득도료이용해근사산법소득적해T여최우해T*적-개고계:T/T* ≤2+n-2/m+1.
