摘要
研究的目的在于解决实践中对多组任务的优化排序问题，即在最短的时间内完成所有给定的任务，由于这类问题往往都是NP完全问题，人们通常寻求其近似算法．文中提出了一种改进的LPT算法，利用。首先空闲”准则，讨论了将n组工件安排在n台速度不同的专用机，m台速度小于专用机的通用机上的C‰。。问题，得到了利用该近似算法所得的解T与最优解T＊的—个估计：T/T＊≤2＋（n-2）/（m＋1）
This paper studies study the Cmax problem on many-group jobs with m general- purpose machinery and n special-purpose machineries that they are the different speed in this paper. This problem is always NP-C problem, so the approximate method is uaually to be found. An improved LPT algorithm and the upper bound performance are given. The ratio of the approximate solution and the bes= way is 2＋（n-2）/（m＋1）
出处
《数学研究》
CSCD
2010年第2期198-205,共8页
Journal of Mathematical Study
基金
国家自然科学基金资助项目(10971234)
关键词
运筹学
排序
启苎目濞法
性能指标
多组工件
通用机与专用机
operations research
scheduling
heuristic approach： performance indexes
many groups of jobs： general-purpose and special-purpose machinery
