论文部分内容阅读
在传统排序问题中,总是假设工件信息在排序之初都已经全部知道.这些问题称之为离线(off-line)排序问题.在实际应用中,有些工件的信息在一开始往往是不知道的,而是随着时间的推移而逐个释放.这些问题称之为在线(on-line)排序问题.本文研究带有链约束chains1,chains2,…,chainsn工件的平行机排序问题.链的到达时间为rj,j=1,2,…,n.工件一旦开始加工,就不能被打断,直到该工件被加工完毕。目标函数是最小化机器完工时间的平方和以及最小化最大延误时间.本文的主要结果如下: (1)研究了每一条链的长度都为1的离线排序问题.在0时刻,所有的工件已到达.目标函数是最小化两台机器的完工时间的平方和.用三参数法该问题可表示为P2||chaini|=1|.我们利用修改的LPT算法(Modified-LPTAlgorithm)求解该问题,并证明该算法的执行比不大于1+1/81。 (2)研究了单位长度工件且链在整数时刻到达的2台恒同机上的在线排序问题.目标函数是最小化两台机器的完工时间的平方和.用三参数表示为P2|pj=1,chainsi released at.证明了任一实例在任意算法下竞争比不小于5/4,而任意的稠密算法(Dense Algorithm)的竞争比都渐近地趋于2,并给出该问题的一个最好可能在线稠密算法。 (3)研究了等长工件在链约束下单机在线排序问题.每一个到达时刻ri到达的工件为一组链chainsi,其上面的工件Jj的加工时间pj和工期qj满足条件CD:若在链chainsi上工件Jj(i)为工件Jk(i)的前任,那么满足pj(i)=pk(i)=p≥qj≥qk.目标函数是最小化最大延误时间.用三参数可表示为1|pj=p,chainsi,releasedat ri,CD|Lmax.证明了任一实例在任意算法下竞争比不小于,并给出了一个最好可能在线算法。