论文部分内容阅读
研究带单服务器且服务时间相等的流水作业排序问题,该流水作业排序问题的目标函数是使总完工时间达到最小.利用目标和的数字匹配这个强NP-困难问题到带单服务器且服务时间相等的流水作业排序问题的归约,证明带单服务器且服务时间相等的流水作业排序问题问题也是强NP-困难的.引入加工顺序为最小加工时间优先的新启发式算法,并证明该启发式算法的上界是6/5,且该上界是紧的.