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

• 作者: 丁伟
• 来源期刊: 数学研究
• 学科: 数学
• 关键词: 运筹学 排序 启发式算法 性能指标 多组工件 通用机与专用机
• 年，卷（期）: 2010,（2）
• 页码范围: 198-205
• 分类号: O223
• 字数: 5247字
• 语种: 中文
• DOI: 10.3969/j.issn.1006-6837.2010.02.014

摘要

研究的目的在于解决实践中对多组任务的优化排序同题,即在最短的时间内完成所有给定的任务,由于这类问题往往都是NP完全同题,人们通常寻求其近似算法.文中提出了一种改进的LPT算法,利用"首先空闲"准则,讨论了将n组工件安排在n台速度不同的专用机,m台速度小于专用机的通用机上的Cmax问题,得到了利用该近似算法所得的解T与最优解T*的-个估计:T/T* ≤2+n-2/m+1.

作者信息

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