论文部分内容阅读
讨论目标函数为极小化加权完工时间和的调度问题.对于这类问题,平行机问题是NP-难的.基于对问题的分析,对工件的加工时间相等的恒速平行机问题,给出了多项式最优算法.Open shop问题是强NP-难的.给出了工序的加工时间相等的无等待Open shop问题与工件的加工时间相等的同速平行机问题的联系.根据这种联系,对工序的加工时间相等的无等待Open shop问题,给出了多项式最优算法.算法的复杂性均为O(nlogn+mn).