论文部分内容阅读
研究带运输时间的流水调度:在该问题中有两台机器A,B和一个运输机V,n个工件,工件需要先在机器A上加工然后在机器B上加工最后被运输机V运往目的地,而且运输机V最初停在机器B旁边.模型的目标是使所有工件都运往目的地的时间最短.文中给出了三种情况下的最优调度算法:i)A,B机器加工工件顺序给定时我们给出了线性时间的最优算法;ii)所有的工件加工时间在机器B上时间相等时我们给出了时间复杂度为O(nlogn)的最优算法;iii)机器B上工件最短加工时间大于等于机器A上工件最长加工时间时给出了时间复杂度为O(n~2)的最优算法.
In this problem we have two machines A and B and a conveyor V and n workpieces. The workpieces need to be machined on machine A first and then machined on machine B and finally transported by conveyor V to the destination. And the transporter V is initially parked next to the machine B. The objective of the model is to minimize the time it takes to transport all the workpieces to the destination.The optimal scheduling algorithm is given in three cases: i) A, B machined workpiece sequence given We give the optimal algorithm for linear time; ii) we give the optimal algorithm with time complexity O (nlogn) when all the workpiece machining times are equal on machine B. iii) the shortest machining time for the workpiece on machine B The optimal algorithm with time complexity O (n ~ 2) is given when the time is greater than or equal to the maximum machining time of the workpiece on machine A.