论文部分内容阅读
本文研究单机继列批实时在线排序的问题.这里批容量分有限和无限,目标函数分别为最小化最大完工时间和最小化最大加工运输时间.工件可以在任意时刻到达并且个数不限,每个工件都有自己的安装时间.批容量为b,批加工时间等于包含在这一批里的所有工件的加工时间之和.批的安装时间等于包含在这一批里的工件的最大安装时间.在最小化最大完工时间问题中,工件的安装时间可能不同；在工件带有运输时间问题中,工件的安装时间都相等.具体的模型如下:
(1)1｜on-line,s-batch,(s,p),b=∞,rj｜Cmax和1｜on-line,s-batch,(s,p),b<∞,rj｜Cmax,其中(s,p)表示工件具有各自的安装时间和加工时间.当b=∞时,我们给出竞争比为(√5+1/2)的最好在线算法；当b<∞时,我们给出竞争比不超过2的在线算法,其中这个问题竞争比的下界仍为(√5+1/2)；
(2)1｜on-line,s-batch,b=∞,rj,qj｜Lmax,此时工件的安装时间都相等并且等于s.我们给出竞争比为2的在线算法,并且这个问题竞争比的下界也为(√5+1/2).当批的安装时间满足一个限制条件时,我们能得到竞争比为(√5+1/2)的最好在线(半在线)算法.