点击次数：

论文类型：期刊论文

发表时间：2017-03-15

发表刊物：系统科学与数学

收录刊物：CSCD

卷号：37

期号：3

页面范围：828-837

ISSN号：1000-0577

关键字：流水车间;完工时间;运输时间

摘要：研究带运输时间的流水调度:在该问题中有两台机器A,B和一个运输机V,n个工件,工件需要先在机器A上加工然后在机器B上加工最后被运输机V运往目的地,而且运输机V最初停在机器B旁边.模型的目标是使所有工件都运往目的地的时间最短.文中给出了三种情况下的最优调度算法:i)A,B机器加工工件顺序给定时我们给出了线性时间的最优算法;ii)所有的工件加工时间在机器B上时间相等时我们给出了时间复杂度为O(nlogn)的最优算法;iii)机器B上工件最短加工时间大于等于机器A上工件最长加工时间时给出了时间复杂度为O(n2)的最优算法.