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

• 作者: 丁伟
• 来源期刊: 中山大学学报（自然科学版）
• 学科: 数学
• 关键词: 启发式算法 性能指标 LS算法 LPT算法 通用机与专用机
• 年，卷（期）: 2008,（3）
• 页码范围: 19-22
• 页数: 4页
• 分类号: O223
• 字数: 4430字
• 语种: 中文
• DOI: 10.3321/j.issn:0529-6579.2008.03.005

摘要

改进了经典的LPT(Longest Processing Time)算法,利用"首先空闲"准则安排机器,而对于工件的安排则按照"长时间任务优先"的原则,讨论了将n组工件安排在n台速度相同的专用机,m台同速度的通用机上的优化排序问题,得到了利用该近似算法所得的解T与最优解T*的一个估计:T/T*≤(2m+1)/(m+1).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	丁伟	中山大学数学系	11	34	4.0	5.0