摘要
改进了经典的LPT(Longest Processing Time)算法,利用"首先空闲"准则安排机器,而对于工件的安排则按照"长时间任务优先"的原则,讨论了将n组工件安排在n台速度相同的专用机,m台同速度的通用机上的优化排序问题,得到了利用该近似算法所得的解T与最优解T*的一个估计:T/T*≤(2m+1)/(m+1)。
The Cmax problem on many-group jobs with m general-purpose machinery and n special-purpose machineries with the same speed was studied in this paper. This problem is always a NP-Hard problem, and an approximate method need to be found. An improved LPT algorithm and the upper bound performance are given. The ratio of the approximate solution and the best solution is （2m ＋ 1 ）/（m ＋ 1 ）.
出处
《中山大学学报（自然科学版）》
CAS
CSCD
北大核心
2008年第3期19-22,共4页
Acta Scientiarum Naturalium Universitatis Sunyatseni
基金
国家自然科学基金资助项目(10531040)
关键词
启发式算法
性能指标
LS算法
LPT算法
通用机与专用机
heuristic approach
performance indexes
LS algorithm
LPT algorithm
general-purpose and special- purpose machinery
