机器带故障的两台机排序问题的一个近似算法

• 作者: 叶赛英 沈灏 魏小兰
• 来源期刊: 杭州电子科技大学学报（自然科学版）
• 关键词: 近似算法 最坏情况界 机器中断
• 年，卷（期）: 2008,（2）
• 页码范围: 90-92
• 页数: 3页
• 分类号: O212
• 语种: 中文
• DOI: 10.3969/j.issn.1001-9146.2008.02.023

摘要

讨论机器带故障中断的两台平行机排序问题,目标为极小化误工工件数,在转移时间t=0时的排序问题是问题P2|D=∞,t=0|∑u'ij,该文给出了相应的算法,并利用该算法,考虑了当工件转移时间t＞0时的NP难的排序问题P2|D=∞,t≠0|∑u'ij.该文使用对前一问题的最优序π*当中的工件相交换,使得增加误工工件数尽量少的方法,提出了一个差界为1的多项式时间的近似算法,并给出了证明及算法的计算复杂性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	沈灏	杭州电子科技大学理学院	15	22	3.0	3.0
2	魏小兰	杭州电子科技大学理学院	3	6	1.0	2.0
3	叶赛英	杭州电子科技大学理学院	1	4	1.0	1.0