平行机上一种带拒绝费用的排序问题研究

作者：武光华

来源：青岛大学学报(自然科学版), 2014, 27(02): 14-16.

• 近似算法
• 可拒绝排序
• 动态规划
• FPTAS

主要研究了一种平行机上的排序问题。目标函数是使总完工时间最小但不能超过总拒绝费用的阀值。提出了该问题是NP-难的证明。针对该排序问题给出了伪多项式时间的动态规划算法且设计出了FPTAS。

• 单位
  潍坊科技学院