具有通用机的多组工件的Q//C_(max)问题的近似算法

• 作者: 丁伟
• 来源期刊: 中山大学学报（自然科学版）
• 学科: 数学
• 关键词: 启发式算法 性能指标 LPT算法 通用机 专用机
• 年，卷（期）: 2010,（1）
• 页码范围: 5-8
• 页数: 4页
• 分类号: O223
• 字数: 2390字
• 语种: 中文

摘要

研究的目的在于解决实践中对多组任务的优化排序问题,即在最短的时间内完成所有给定的任务.由于这类问题往往都是NP完全问题,人们通常寻求其近似算法.提出了一种改进的LPT算法,利用"最大相对加工时间"准则和"首先空闲"准则,讨论了将n组工件安排在n台速度不同的专用机,一台速度小于专用机的通用机上的C_(max) 问题,得到了利用该近似算法所得的解T与最优解T~*的一个估计:T/T~*≤1+1/∑_(i∈I)s_i,其中I表示在最后完工的工件完工之前,在通用机上至少安排了一个工件的工件组的下标集合.由此得出采用该近似算法对工件排序,在最差情况下要比最优排序多出1/∑_(i∈I)s_i的时间.

作者信息

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