所谓排序,就是在一定的约束条件下分配时间资源去完成一些任务,使一个或多个目标达到最优.近年来,在线排序是发展比较迅速的排序模型。在线排序是指工件所有信息在其到达之前都是未知的,工件在到来之前不能安排作业,工件到达后也没必要立即安排,但是一旦工件被安排后就不允许再改变。本文中,我们研究了一种在线排序模型:带有优先约束的工件在平行机上的在线排序问题.有n个带有优先约束的工件J1,J2,…,Jn.每个工件都分别有一个到达时间rj,加工时间pj.这些工件需要在m(m≥1)台平行机上进行加工.工件一旦开始加工,中间不能被打断,直到该工件被加工完毕。我们的目标函数是最小化机器完工时间的平方和.用Graham等人[3]提出的三参数表示法,我们的问题可以表示为:(?)本文的主要结果如下: (1)对于排序模型,任意在线算法的竞争比下界不小于5/4. (2)对于排序模型P3|pj=1,intreei released at,任意在线算法的竞争比下界不小于302/281. (3)对于排序模型P2|pj=p,chainsi released at,任意在线算法的竞争比下界不小于106/81. (4)对于排序模型P2|pj=1,preci released at,任意在线算法的竞争比下界不小于65/49,并给出了一个竞争比不大于2的在线算法. (5)给出了排序模型Pm|pj=1,outtreei released at一个竞争比不大于m的在线算法.
展开▼
