论文部分内容阅读
研究了带服务器的流水作业排序问题的复杂性和启发式算法．每个工件在机器上加工之前，必须由服务器先进行安装，在任何时刻服务器只能在1台机器上安装工件，目标是使最大加工时间达到最小．在只有3台机器的情况下，利用3-划分到该问题的一个归约来证明该流水作业排序问题仍然是强一困难的．为此，引入一个新的启发式算法，并证明该启发式算法的紧界为2．