针对工件加工需要额外资源且额外资源有两个单位可用的平行机调度问题，目标是极小化最大完工时间，给出了一个近似算法。首先，说明了该问题是NP-难的，并给出了该问题的整数规划模型和最优解的下界；然后，设计了该问题的一个近似算法，通过分析算法的性质，证明了该算法的最坏情况界不大于3-2/m;最后，通过大量的数值实验验证算法在平均情况下的性能。数值实验结果表明，该算法在工件数、额外资源数和机器数等因素扰动下都体现了较好的性能。该算法可为需要额外资源调度问题的高效算法设计提供参考。
科研之友
微信
新浪微博
Facebook
分享链接
