加工时间成比例的两阶段自由作业排序问题

• 作者: 罗惠 胡觉亮 董建明
• 来源期刊: 浙江大学学报（理学版）
• 学科: 数学
• 关键词: 两阶段自由作业排序问题 近似算法 最坏情况界
• 年，卷（期）: 2015,（1）
• 所属期刊栏目: 数学与计算机科学
• 页码范围: 97-101
• 页数: 5页
• 分类号: O223
• 字数: 4665字
• 语种: 中文
• DOI: 10.3785/j.issn.1008-9497.2015.01.015

摘要

对一类工件加工时间成比例的两阶段自由作业排序问题进行了研究.工件需要分别在包含m1和m2台平行机的两阶段中进行加工,工件在阶段间的加工满足自由作业环境要求,且相同工件在两阶段的加工时间相同,目标是极小化时间表长,即最后完工工件的完工时间.证明了当min{ m1,m2}≥2时该问题是NP-难的,给出了该问题的一个近似算法,并证明了该算法的最坏情况界不大于3/2-3/2(2min{m1,m2}+1).得到了当min{ m1,m2}=1时,该算法为问题的最优算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	胡觉亮	浙江理工大学理学院	81	456	12.0	17.0
2	董建明	浙江理工大学理学院	11	71	4.0	8.0
3	罗惠	浙江理工大学理学院	1	0	0.0	0.0