流水调度问题是组合优化领域的经典问题之一,因为与实际生产密切相关,是目前研究较为广泛的一种调度问题。在整个生产过程中,产品的加工与产品的运输是最重要的两个环节,如果将两者结合并提出合理的解决方案,既可以节约生产成本,又可以提高生产效率。本文主要研究考虑运输时间的两台机器和一台运输机的流水调度,根据运输机所处的位置,分为两种模型。模型1:工件先在两台流水机器上加工,然后由运输机运输到目的地;模型2:工件先在一台流水机器上加工,然后由运输机运输到另一台流水机器上继续加工。本文研究了以上两种模型的计算复杂性,设计了模型1在某些特殊情况下的最优调度算法,同时改进了这两种模型近似算法的近似比,具体结果如下:首先,对于模型1,当运输机每次最多运输2个工件时,Yuan等人在2007年只证明该问题是一般NP-难。本文证明了该问题是强NP-难,解决了2007年以来一直未解的问题。对于模型2,目前其复杂性的研究结果如下:2001年Hurink和Lee等人分别证明了当运输机每次运输1个或3个及以上工件时,这两种情况都是强NP-难,而每次最多运输2个工件时,该问题是否是强NP-难十几年来尚未被证明。本文证明了当运输机每次最多运输2个工件时,该问题也是强NP-难的,解决了 18年来一直未解的问题。本文的创新是首次将4-Partition问题归约到以上两种调度模型上。其次,对于模型1,当运输机每次运输常数个工件时,本文提出了三种特殊情况下的最优调度方案:(1)当给定工件在两台机器上的加工顺序时,提出了运输机的最优调度方案;(2)当所有工件在第二台机器上加工时间均相同时,给出时间复杂度为O(n logn)的最优算法;(3)当工件在第二台机器上加工的最短时间大于等于工件在第一台机器上加工的最长时间时,给出时间复杂度为O(n2)的最优算法,这里n是输入的工件个数。最后,针对本文研究的两类流水调度模型,当运输机每次运输常数个工件时,研究这两类模型的近似算法。对于模型1,本文给出了近似比为1+ε的近似算法。对于模型2,2011年Gong和Tang给出了近似比为2的近似算法,本文同样给出了近似比为1+ε多项式时间的近似算法,这里ε为大于0的任意小的数。