Release Time:2019-03-11  Hits:

Indexed by: Journal Article

Date of Publication: 2004-10-08

Journal: 应用数学学报

Included Journals: CSCD、ISTIC、PKU

Volume: 27

Issue: 4

Page Number: 599-607

ISSN: 0254-3079

Key Words: 排序问题;同类机;近似算法;半定松弛

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