带运输机的流水车间调度的最优算法

Optimal Algorithms for Flow Shop Schedule with Transporter

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

In this paper, we study a flow shop problem in which there are two machines A, B and a transporter V. There are jobs needed to be processed on A, then on B and transported to the destination by transporter V which is initially located on machine B. The objective is to minimize the makespan when all the jobs are carried to the destination. We study three special cases of the problem and give related optimal algorithms： i） When the processing order on machines A, B is fixcd, we propose a linear time optimal algorithm; ii） when the processing time on machine B of jobs is identical, we give an O（n log n） optimal algorithm; iii） when the shortest processing time of the jobs on machine B is no less than the longest processing time on machine A, we give an O（n2） optimal algorithm,