一类速度不同的具有m台通用机的n组工件的排序问题  

A Type of Scheduling Problem on m General-Purpose Machinery and n Group Tasks with Uniform Processors

作　　者：丁伟[1] 

机构地区：[1]中山大学数学与计算科学学院,广东广州510275

出　　处：《数学研究》2010年第2期198-205,共8页Journal of Mathematical Study

基　　金：国家自然科学基金资助项目(10971234)

摘　　要：研究的目的在于解决实践中对多组任务的优化排序问题，即在最短的时间内完成所有给定的任务，由于这类问题往往都是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）

关 键 词：运筹学 排序 启苎目濞法 性能指标 多组工件 通用机与专用机 

分 类 号：O223[理学—运筹学与控制论]