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