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

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

作　　者：丁伟[1] 

机构地区：[1]中山大学数学系//物理系,广东广州510275

出　　处：《中山大学学报（自然科学版）》2008年第3期19-22,共4页Acta Scientiarum Naturalium Universitatis Sunyatseni

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

摘　　要：改进了经典的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 ）.

关 键 词：启发式算法 性能指标 LS算法 LPT算法 通用机与专用机 

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