首页 | 本学科首页   官方微博 | 高级检索  
     

同速度的具有m台通用机的n组工件的排序问题
引用本文:丁伟. 同速度的具有m台通用机的n组工件的排序问题[J]. 中山大学学报(自然科学版), 2008, 47(3): 19-22
作者姓名:丁伟
作者单位:中山大学数学系,广东,广州,510275;中山大学物理系,广东,广州,510275
摘    要: 改进了经典的LPT(Longest Processing Time)算法,利用“首先空闲”准则安排机器,而对于工件的安排则按照“长时间任务优先”的原则,讨论了将n组工件安排在n台速度相同的专用机,m台同速度的通用机上的优化排序问题,得到了利用该近似算法所得的解T与最优解T*的一个估计:T/T*≤(2m+1)/(m+1)。

关 键 词:启发式算法性能指    LS算法  LPT算法  通用机与专用机
文章编号:0529-6579(2008)03-0019-04
收稿时间:2007-10-15;
修稿时间:2007-10-15

A Type of Scheduling Problem on m General-Purpose Machinery and n Group Tasks with Uniform Processors
DING Wei. A Type of Scheduling Problem on m General-Purpose Machinery and n Group Tasks with Uniform Processors[J]. Acta Scientiarum Naturalium Universitatis Sunyatseni, 2008, 47(3): 19-22
Authors:DING Wei
Affiliation:(Department of Mathematics ;Department of Physics,Sun Yat sen University,Gaungzhou 510275,China)
Abstract: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).
Keywords:heuristic approach  performance indexes  LS algorithm  LPT algorithm  general purpose and special purpose machinery
本文献已被 维普 万方数据 等数据库收录!
点击此处可从《中山大学学报(自然科学版)》浏览原始摘要信息
点击此处可从《中山大学学报(自然科学版)》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号