点击次数：

论文类型：期刊论文

发表时间：2004-10-08

发表刊物：应用数学学报

收录刊物：PKU、ISTIC、CSCD

卷号：27

期号：4

页面范围：599-607

ISSN号：0254-3079

关键字：排序问题;同类机;近似算法;半定松弛

摘要：我们考虑平行机排序问题中的这样一类:机器两台,类型一样,但效率不同.其中n个工件在第一台机器上的加工时间分别为p1,p2,…,pn,在第二台机器上的加工时间分别为αp1,αp2,…,αpn,其中0＜α≤1.每台机器上的工件总数不受限制.n个工件的权分别为w1,w2,…,wn,我们的目标是如何在这两台机器上安排这n个工件以及如何确定每台机器上工件加工的先后顺序,使得这n个工件的完工时间的总权和∑ j wjCj达到最小.该问题记为Q2||∑wjCj.对于这个问题,我们给出一个1.1755近似算法.