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

摘要：

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

关键词：平行机排序、NP-难问题、近似算法、绝对性能比、渐近性能比

所属期刊栏目：18

分类号：O212(概率论与数理统计)

资助基金：国家自然科学基金19971078,10271110;电子工业部电子科研院军事预研项目57.7.3.7

在线出版日期：2003-11-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：207-212