GPU的计算性能随着半导体工艺的发展得到飞速提升,在某些方面甚至远远超过了通用CPU。GPU被越来越多的应用到天文、医疗等各个领域,成为重要的计算资源。GPU中的数据传输和负载执行过程可以抽象为流水作业模型,因此针对该模型的优化算法研究对GPU性能的提升具有十分积极的作用。本文主要研究了三类流水作业调度问题,针对各类问题的特点设计了不同的优化算法进行求解,并通过数值仿真实验对算法性能进行了验证。本文的主要内容如下:首先,将拉格朗日松弛算法应用于静态流水作业极小化完工时间平方和问题。针对该问题建立了数学规划模型,并对模型进行了调整以适用于拉格朗日松弛算法。通过松弛工件顺序约束、工件分配约束和机器顺序约束,将问题转化成更为简单的完工时间子问题和位置分配子问题。利用求导和枚举的方法分别解决这两个子问题,然后通过次梯度算法来更新拉格朗日乘子,并在解的可行化过程中加入了禁忌搜索算法来改进可行解的质量。通过数值仿真实验验证了拉格朗日松弛算法的有效性。其次,针对动态流水作业极小化完工时间k次方和问题(k=2,3),应用分枝定界算法求解小规模问题。根据问题的特点设计了新的剪枝规则和下界以提高计算效率,针对中等规模问题,通过分枝定界算法提供初始种群,采用离散差分进化算法进行求解,并使用多点插入的交叉方式来加快搜索速度。通过数值仿真验证了分枝定界算法和离散差分进化算法的有效性。然后,研究了带有学习效应的动态流水作业极小化完工时间平和问题。考虑了线性函数、幂函数、指数函数三种形式的学习效应函数,并建立了问题的数学规划模型以便利用CPLEX求解。同样采用分枝定界算法和差分进化算法进行求解,针对带有学习效应的问题设计了剪枝规则和下界。针对分枝定界算法中没被剪枝的节点对应的子序列,用SPTA启发式规则将未排工件进行排序从而得到完整序列,然后将这些完整的序列用作差分进化算法的初始种群。数值仿真验证了分枝定界算法和差分进化算法的有效性。