论文部分内容阅读
在制造系统和半导体流水线上经常需要考虑的是在线继列分批问题.本文所考虑的问题中,每个工件具有各自的安装时间和加工时间（s,p）,属于同一组的工件才能在同一批中加工,每一批最多可以加工b个工件,批的安装时间和加工时间分别为这一批中工件的最大安装时间和加工时间之和,目标函数是最小化工件的最大完工时间.利用对手法证明了任何一个在线算法的竞争比都不小于max{2b b＋1,1＋α},且给出了一个渐近意义下最好的竞争比是2的在线算法.