最小化时间表长的平行机调度近似算法研究

• 作者: 李洪兴 程贞敏 谷敏强
• 来源期刊: 北京师范大学学报：自然科学版
• 学科: 数学
• 关键词: 平行机调度 周期维护 时间表长 近似算法 最坏误差界
• 年，卷（期）: 2012,（1）
• 页码范围: 11-15
• 分类号: O223
• 语种: 中文

摘要

讨论机器具有固定周期维护t,目标函数为最小化时间表长的m台平行机调度问题.这是一个NP-难的问题.关于该问题主要分析了当维护时间t≤T/3时,利用经典的装箱算法FFD我们可以得到关于该问题的一个近似算法FFPTD.该算法的最坏误差界为2,最后以实例说明2为该算法的紧界.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	谷敏强	汕头大学理学院数学系	10	31	3.0	5.0
2	李洪兴	大连理工大学电子与信息工程学院	45	300	9.0	15.0
3	程贞敏	北京联合大学商务学院	7	29	3.0	5.0