有分离调整和移走时问的两机器流水作业总延误问题的近似算法 (2005年)

讨论了一类两机器流水作业的总延误问题，其中每个工件的操作由“调整”步、“加工”步及“移走”步组成，而工件的调整时间和移走时间均独立于加工时间，同一工件的“调整”步及“移走”步在2台机器上可重叠进行，但“加工”步不能重叠，并且第一台机器上没有空闲时间，工件一旦开始加工就不允许中断．给出了该问题的解中工件排列应满足的条件，并根据这些条件构建了几个近似算法．在构建分支定界算法时，利用问题目标函数的下界及近似算法的结果给出了剪支法则，由此说明所给近似算法对某些例子是很有效的．