两台机器及时完工工件数最大化问题的近似算法

• 作者: 杨启帆 沈灏
• 来源期刊: 高校应用数学学报A辑
• 学科: 数学
• 关键词: 平行机排序 NP-难问题 近似算法 绝对性能比 渐近性能比
• 年，卷（期）: 2003,（2）
• 页码范围: 207-212
• 页数: 6页
• 分类号: O212
• 字数: 3525字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-4424.2003.02.012

摘要

平行机排序问题Pm∥∑uj当m≥2时是一个NP-难的问题.本文利用求解1∥∑uj的Moore算法构造了与P2∥∑uj等价的P2∥n-∑uj问题的一个多项式时间近似算法,并证明了该算法的绝对性能比为3/4.此外还研究了机器带有准备时间的问题P2,ri∥n-∑uj,并证明了在这种情况下算法的渐近性能比为2/3.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	杨启帆	浙江大学数学系	15	209	6.0	14.0
2	沈灏	浙江大学数学系	2	9	1.0	2.0